[C code] 22ms -> 12ms, by simply moving variables definition to function top, why?


  • 1
    S

    My original code: Runtime - 22 ms

    #include <stddef.h>
    
    struct ListNode* removeElements(struct ListNode* head, int val) {
        while (head != NULL && head->val == val) {
            head = head->next;
        }
        if (head == NULL)
            return NULL;
    
        struct ListNode *p = head, *q = head->next;
        while (q != NULL) {
            if (q->val == val) {
                q = q->next;
                p->next = q;
            }
            else {
                p = q;
                q = q->next;
            }
        }
        return head;
    }
    

    Compared with this one by a clever guy: My step by step 12 ms C solution

    As you see, our code are identical, except for the position of two variable definitions. (you say "and variables' name"? oh, come on, don't be so picky)
    Then, I moved the definition instructions to function top:

    #include <stddef.h>
    
    struct ListNode* removeElements(struct ListNode* head, int val) {
        struct ListNode *p = NULL, *q = NULL;
        
        while (head != NULL && head->val == val) {
            head = head->next;
        }
        if (head == NULL)
            return NULL;
    
        p = head, q = head->next;
        while (q != NULL) {
            if (q->val == val) {
                q = q->next;
                p->next = q;
            }
            else {
                p = q;
                q = q->next;
            }
        }
        return head;
    }
    

    Runtime reduced to 12 ms. Why?

    P.S. I compiled both code on my PC(64bit, ubuntu, gcc) and disassembled them, only to find the faster (12ms) version, on the contrary, has two more instructions to set the variables zero. All other parts of the disassembled code are the same.


  • 0
    V

    I think the time that LC OJ gives is just an indication of how much it has taken to run your code for all the test cases. It's not the actual measure of your algorithm performance which usually analyzed differently.

    You give a try submitting more than once, I expect the time changes and is not constant.

    Not related to variable names and their location, so be cool :)


  • 0
    S

    I agree with you. Anyway, I tried and the faster version became 14ms, the slower version became 25ms. The difference is still obvious. :)


  • 0
    V

    :) ok. I had a similar situation recently..

    In one of the program, I haven't free'd up memory which took around 42 ms to execute. After I add 'free', it came down to 24ms.
    Logically with an extra statement and extra work to do, it should have taken more than 42ms but it took less than that.


  • 0
    S

    So weird, maybe we have to check out how OJ works to figure it out, but that beyond our concerns.

    By the way, in your case, I guess it might because call to 'free' enabled the program to reuse memory, led to less 'low level memory allocation', which typically allocates memory in blocks and is time-consuming.


  • 0
    J

    it's not necessary to use additional while-loop.

        NodePtr dummyhead = (NodePtr)malloc(sizeof(Node));
        dummyhead->next = head;
        head = dummyhead;
        while(head && head->next) {
                if (val == head->next->val ) {
                        NodePtr p = head->next;
                        head->next = head->next->next;
                        free(p);
                } else
                head = head->next;
        }
        return dummyhead->next;
    

  • 0
    J

    my solution is 6ms.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.