Understanding time complexity and memory usage

Question

I have this programming question -

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

And I wrote these two programs, in one I am changing just the values and in other I am changing connections itself.

FIRST program

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* p = head;
        int temp = 0;
        while(p!= NULL && p->next!=NULL)
        {
            temp = p->val;
            p->val = p->next->val;
            p->next->val = temp;
            p = p->next->next;
        }
        return head;
    }
};

SECOND Program

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* p = head;
        ListNode* q = head;
        ListNode* r = head;
        int flag = 0;
        while(p!= NULL && p->next!=NULL)
        {
            if(flag == 0)
            {
                flag = 1;
                q = p->next;
                p->next = q->next;
                q->next = p;
                head = q;
                p = q->next->next;
                r = q->next;
                continue;
            }
            q = p->next;
            p->next = q->next;
            q->next = p;
            r->next = q;
            p = q->next->next;
            r = q->next;
        }
        return head;
    }
};

When I submitted this code, I found the second is having lesser runtime and is using lesser memory. But in the first one I am just swapping values and using an extra pointer and an extra integer variable, but in second one I am using 3 extra pointers. How can second one be more efficient?

Answer 1

For questions about performance, it is important to specify the measurement conditions precisely including but not limited to the code, compiler, os and hardware because these can all be important factors. Performance on modern hardware is often counter-intuitive and extremely sensitive to test conditions so it is important to test the code in as a real world scenario as possible.

I will presume that you are generally interesting in how the the two different implementation of swap might perform and the influencing factors. I have included some sample code that describes how I would go about making performance measurements for these two functions assuming that the actual problem to solve was swapping pairs on lists of 1M nodes that are cached in memory. I included my own implementations of these two functions as well. For other scenarios, you would have to set the tests up differently.

The value swapping was slightly faster than the pointer swapping and your implementation was slightly faster than mine. I think that comes down to the value swapping costing 1 swap per pair while the pointer swapping requires a three pointer rotation or two swaps per pair. I'm not sure why my implementation is slower, which shows the counterintuitive nature of performance on modern hardware.

Sample Code

#include "core/util/tool.h"
#include "core/chrono/stopwatch.h"

struct ListNode {
    ListNode() : val(0), next(nullptr) { }
    ListNode(int x) : val(x), next(nullptr) { }
    ListNode(int x, ListNode *n) : val(x), next(n) { }
    int val;
    ListNode *next;
};

ListNode *swap_vals(ListNode *head) {
    auto curr = head;
    while (curr and curr->next) {
        std::swap(curr->val, curr->next->val);
        curr = curr->next->next;
    }
    return head;
}

ListNode *swap_ptrs(ListNode *head) {
    auto ptr = &head;
    while (ptr and *ptr and (*ptr)->next) {
        auto& p = *ptr;
        auto& q = p->next;
        auto& r = q->next;
        std::swap(p, q);
        std::swap(q, r);
        ptr = q ? &q : nullptr;
    }
    return head;
}

ListNode* swap_vals_sharma(ListNode* head) {
    ListNode* p = head;
    int temp = 0;
    while(p!= NULL && p->next!=NULL)
    {
        temp = p->val;
        p->val = p->next->val;
        p->next->val = temp;
        p = p->next->next;
    }
    return head;
}

ListNode* swap_ptrs_sharma(ListNode* head) {
    ListNode* p = head;
    ListNode* q = head;
    ListNode* r = head;
    int flag = 0;
    while(p!= NULL && p->next!=NULL)
    {
        if(flag == 0)
        {
            flag = 1;
            q = p->next;
            p->next = q->next;
            q->next = p;
            head = q;
            p = q->next->next;
            r = q->next;
            continue;
        }
        q = p->next;
        p->next = q->next;
        q->next = p;
        r->next = q;
        p = q->next->next;
        r = q->next;
    }
    return head;
}

auto create_list(int size) {
    ListNode *head = new ListNode(0);
    ListNode *curr = head;
    for (auto i = 1; i < 10; ++i) {
        auto node = new ListNode(i);
        curr->next = node;
        curr = node;
    }
    return head;
}

void print_list(ListNode *lst) {
    for (auto node = lst; node; node = node->next)
        cout << node->val << " ";
    cout << endl;
}

template<class Work>
void measure(std::string_view desc, size_t n, Work&& work) {
    auto lst = create_list(n);
    chron::StopWatch timer;
    size_t ns{};
    for (auto i = 0; i < 10; ++i) {
        timer.mark();
        lst = work(lst);
        ns += timer.elapsed_duration<std::chrono::nanoseconds>().count();
    }
    cout << fmt::format("{} {} ns", desc, ns / 10) << endl;
}

int tool_main(int argc, const char *argv[]) {
    {
        auto lst = create_list(10);
        lst = swap_vals(lst);
        print_list(lst);
    }

    {
        auto lst = create_list(10);
        lst = swap_ptrs(lst);
        print_list(lst);
    }

    {
        auto lst = create_list(10);
        lst = swap_vals_sharma(lst);
        print_list(lst);
    }

    {
        auto lst = create_list(10);
        lst = swap_ptrs_sharma(lst);
        print_list(lst);
    }

    measure("swap_vals-sharma     ", 1'000'000, [](auto head) { return swap_vals_sharma(head); });
    measure("swap_ptrs-sharma     ", 1'000'000, [](auto head) { return swap_ptrs_sharma(head); });
    measure("swap_vals-random-bits", 1'000'000, [](auto head) { return swap_vals(head); });
    measure("swap_ptrs-random-bits", 1'000'000, [](auto head) { return swap_ptrs(head); });
    return 0;
}

Output

1 0 3 2 5 4 7 6 9 8
1 0 3 2 5 4 7 6 9 8
1 0 3 2 5 4 7 6 9 8
1 0 3 2 5 4 7 6 9 8
swap_vals-sharma      50 ns
swap_ptrs-sharma      54 ns
swap_vals-random-bits 50 ns
swap_ptrs-random-bits 79 ns