Leetcode148, why my unsafe code so slow

help
1 
pub fn sort_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        if head.is_none() || head.as_ref().unwrap().next.is_none() {
            return head;
        }

        let mut dummy = Box::new(ListNode::new(0));
        let mut current = &mut dummy;
        let mut fast = head.as_deref().unwrap() as *const ListNode;
        let mut slow = &mut head;

        while !fast.is_null()
            && unsafe { (*fast).next.is_some() }
            && unsafe { (*fast).next.as_ref().unwrap().next.is_some() }
        {
            fast = unsafe {
                (*fast)
                    .next
                    .as_ref()
                    .unwrap()
                    .next
                    .as_ref()
                    .map_or(std::ptr::null(), |node| node.as_ref() as *const _)
            };

            slow = &mut slow.as_mut().unwrap().next;
        }

        let mut head_1 = Self::sort_list(slow.as_mut().unwrap().next.take());
        let mut head_2 = Self::sort_list(head);

        while let (Some(node1), Some(node2)) = (head_1.as_mut(), head_2.as_mut()) {
            if node1.val < node2.val {
                current.next = head_1.take();
                current = current.next.as_mut().unwrap();
                head_1 = current.next.take();
            } else {
                current.next = head_2.take();
                current = current.next.as_mut().unwrap();
                head_2 = current.next.take();
            }
        }

        current.next = head_1.or(head_2);

        dummy.next
    }

too slow, realy too slow, I've seen a better solution, but I still want to find out the reason. I skipped the safe check, won't it be faster?

2

I didn't read the code, but these kind of competitive problems usually don't need unsafe for the (marginally) extra performance. if you get time out, it's usually you are using an algorithm that is not suitable for the problem.

7 Likes
3

so you are doing merge sort, right? if I read your code correctly, you split the list by fast-slow-pointer-chasing, which should have quadratic complexity.

try to use a length parameter, which should reduce the splitting to linear complexity, and total complexity of O(n log n). here's a sketch:

EDIT

now I think about it, spitting the list by double pointer chasing is O(nlogn), not quadratic. using an explicit length parameter may (or may not) improve the performance a little bit, but it's the same complexity nevertheless.

so the sketch below probably won't improve the performance much, but I'll leave it unedited anyway.

END OF EDIT

// merge two non-empty sorted list
fn merge(head1: Box<ListNode>, head2: Box<ListNode>) -> Box<ListNode> {
    todo!();
}
// split the list of given length into two, if `len` is odd, first list is shorter
// `len` must be >= 2, otherwise panic
fn split(head: Box<ListNode>, len: usize) -> (Box<ListNode>, Box<ListNode>) {
    todo!()
}
// recursive merge sort a non-empty list of given length
fn merge_sort(head: Box<ListNode>, len: usize) -> Box<ListNode> {
    if len == 1 {
        return head;
    }
    let (head1, head2) = split(head, len);
    let head1 = merge_sort(head1, len / 2);
    let head2 = merge_sort(head2, len - len / 2);
    merge(head1, head2)
}

pub fn sort_list(head: Option<Box<ListNode>>) -> Option<BoxList<Node>> {
    head.map(|head| {
        let len = todo!();
        merge_sort(head, len)
    })
}
1 Like
4

Where? unsafe isn't the magic "make no checks" wand. It doesn't change your program in any way. All I see is a mountain of code with lots of panics.

3 Likes
5

Here, Box::new would dynamic allocate memory. You can just remove Box::new.

6

Also, unsafe code != quick code.

2 Likes
7

FWIW the unsafe pointer chasing can be cleaned up a bit:

        let mut slow = &raw mut head;
        let mut fast = &head;

        while let Some(node) = fast.as_ref().and_then(|node| node.next.as_ref()) {
            fast = &node.next;
            slow = &raw mut unsafe { &mut *slow }.as_mut().unwrap().next;
        }

        let mut head_1 = Self::sort_list(unsafe { &mut *slow }.take());
        let mut head_2 = Self::sort_list(head);
1 Like
8

it's very greatful, I will use fewer unsafe code and make it faster.