了解时间复杂度和内存使用情况

Question

我有这个编程问题-

给定一个链表，交换每两个相邻的节点并返回它的头。您必须在不修改列表节点中的值的情况下解决问题（即，只能更改节点本身。）

我写了这两个程序，在一个程序中，我只更改值，在另一个程序中，我正在更改连接本身。

第一个节目

/**
 * 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;
    }
};

第二期节目

/**
 * 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;
    }
};

当我提交这段代码时，我发现第二个代码的运行时间更短并且使用的内存更少。但在第一个中我只是交换值并使用一个额外的指针和一个额外的整数变量，但在第二个中我使用了 3 个额外的指针。第二个如何更有效率？

Answer 1

关于性能的问题，重要的是要准确指定测量条件，包括但不限于代码、编译器、操作系统和硬件，因为这些都是重要因素。现代硬件的性能通常是反直觉的，并且对测试条件极其敏感，因此尽可能在真实场景中测试代码非常重要。

我假设您通常对

swap

的两种不同实现可能如何执行以及影响因素感兴趣。我已经包含了一些示例代码，描述了我将如何对这两个函数进行性能测量，假设要解决的实际问题是在缓存在内存中的

1M

节点列表上交换对。我也包含了我自己对这两个函数的实现。对于其他场景，您将不得不以不同的方式设置测试。

值交换比指针交换稍快，你的实现比我的稍快。我认为这归结为价值交换每对花费 1 次交换，而指针交换需要三指针旋转或每对两次交换。我不确定为什么我的实现速度较慢，这显示了现代硬件性能的违反直觉的本质。

示例代码

#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;
}

输出

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