c++ - 为什么 std::pair 的分配和排序比 std::vector 快?

今天我只是试图解决编程中的一个问题。我注意到 vector<vector> 的分配和排序比 vector<pair<int, pair<int, int>> 慢得多.我进行了一些基准测试,发现对于给定的输入(https://pastebin.com/izWGNEZ7),嵌套 vector 代码比嵌套对代码慢 4 倍。

下面是我用于基准测试的代码。

auto t_start = std::chrono::high_resolution_clock::now();
    vector<pair<int, pair<int, int>>> edges;
    for (int i = 0; i < points.size(); i++)
        for (int j = i + 1; j < points.size(); j++)
            edges.push_back({abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), {i, j}});
    sort(edges.begin(), edges.end());
    auto t_end = std::chrono::high_resolution_clock::now();
    double elapsed_time_ms = std::chrono::duration<double, std::milli>(t_end - t_start).count();
    cout << elapsed_time_ms << endl;

    auto t_start1 = std::chrono::high_resolution_clock::now();
    vector<vector<int>> edges1;
    for (int i = 0; i < points.size(); i++)
        for (int j = i + 1; j < points.size(); j++)
            edges1.push_back({abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j});
    sort(edges1.begin(), edges1.end());
    auto t_end1 = std::chrono::high_resolution_clock::now();
    double elapsed_time_ms1 = std::chrono::duration<double, std::milli>(t_end1 - t_start1).count();
    cout << elapsed_time_ms1 << endl;

输出:

241.917
1188.11

有谁知道为什么 performance 有很大的不同?

回答1

std::pairstd::array 具有在编译时已知的固定大小,并将直接将对象包含在类本身中。另一方面,std::vector 必须处理动态大小,并且需要在堆上分配一块内存来保存对象。

对于小对象,std::pairstd::array 会更好,因为分配和释放内存的开销会占用你的 performance。这就是你所看到的。例如,指针所涉及的额外间接也会使您付出代价。比较元素以及必须在运行时检查大小。

另一方面,对于大型对象,std::vector 应该更好,因为它支持移动语义。交换 2 vectors 只会交换指向数据的指针,而 std::pairstd:array 将不得不移动/复制每个元素,这对于大型对象来说代价高昂。

因此,您看到的不是该对比 vector 快,而是在该用例中该对比 vector 快。

相似文章

最新文章