3

我意外地惊讶地发现，插入排序的键std::set比插入随机键快得多。这有点违反直觉，因为作为自平衡二叉搜索树的红黑树（我验证它std::set在我的系统上实现为红黑树）需要执行大量重新平衡操作来插入排序的序列键，因此插入排序的键应该比插入随机键花费更多的时间。

但事实是，插入排序的键可以比插入随机键快 15 倍！这是我的测试代码和一些结果：

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <set>
#include <vector>
using namespace std;

int64_t insertion_time(const vector<int> &keys) {    
        auto start = chrono::system_clock::now();
        set<int>(keys.begin(), keys.end());
        auto stop = chrono::system_clock::now();
        auto elapsed = chrono::duration_cast<chrono::milliseconds>(stop - start);
        return elapsed.count(); 
}

int main() {
    size_t test_size;
    cout << "test size: ";
    cin >> test_size;
    vector<int> keys(test_size);
    for (int i = 0; i < test_size; ++i) {
        keys[i] = i;
    }
    
    // whether shuffled case or sorted case took first was irrelevant and results were similar
    auto rng = std::default_random_engine {};
    shuffle(keys.begin(), keys.end(), rng);
    cout << "shuffled: " << insertion_time(keys) << endl;

    sort(keys.begin(), keys.end());
    cout << "sorted: " << insertion_time(keys) << endl;

    return 0;
}

// i7 8700, 32 GB RAM, WIN10 2004, g++ -O3 main.cpp
// An interesting observation is that the difference becomes larger as test_size being larger.
// Similar results showed up for my handwritten red-black tree and other
// machines( or other compilers, operating systems etc)

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 1000000
shuffled: 585
sorted: 96

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 3000000
shuffled: 2480
sorted: 296

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 5000000
shuffled: 4805
sorted: 484

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 10000000
shuffled: 11537
sorted: 977

C:\Users\Leon\Desktop\testSetInsertion>a
test size: 30000000
shuffled: 46239
sorted: 3076

有人解释一下吗？我猜这与缓存局部性有关，因为在插入排序键时，重新平衡通常涉及最近插入的那些节点。但以上只是我的猜测，我对缓存局部性知之甚少。

4

1 回答 1

5

如果您查看https://en.cppreference.com/w/cpp/container/set/set

你可以看到：

复杂性
[..]
2)通常，N log(N)如果范围已按 value_comp() 排序，则为线性。N = std::distance(first, last)N

我们可以insert在循环中使用end()带有正确提示的摊销常量作为提示。

于 2021-02-23T11:31:46.933 回答