C列表。sort（）vs将列表复制到向量，将值排序并复制回列表（Primer C Prata第16章，第9次练习）

Question

我目前正在学习Prata的“C Primer Plus”一书。关于第16章的练习问题，我遇到了以下练习：

与数组相比，链表具有更容易添加和删除元素的功能，但排序速度较慢。这就提出了一种可能性：也许将列表复制到数组，对数组进行排序，然后将排序后的结果复制回列表可能比简单地使用列表算法进行排序更快。（但它也可能使用更多的内存。使用以下方法检验速度假设：a。创建一个大型矢量对象 vi0，使用 rand（） 提供初始值。b.创建第二个矢量对象 vi 和一个与原始对象大小相同的列表对象 li，并将它们初始化为原始矢量中的值。c. 使用 STL sort（） 算法对 vi 进行排序的程序需要多长时间，然后使用列表 sort（） 方法对 li 进行排序需要多长时间。d. 将 li 重置为 vi0 的未排序内容。将 li 复制到 vi、排序 vi 和将结果复制回 li 的组合操作计时。要对这些操作进行计时，可以使用 ctime 库中的时钟（）。如清单 5.14 所示，您可以使用以下语句启动第一个定时：clock_t start = clock（）;然后在操作结束时使用以下命令来获取经过的时间：clock_t end = clock（）;断续器

我的实现是这样的：

#include <iostream>
#include <vector>
#include <list>
#include <ctime>
#include <cstdlib>
#include <algorithm>

using namespace std;

const int MAX = 10'000'000;

int main()
{
    // Make real random
    srand(time(0));

    vector<int> vi0(MAX);
    for( int i=0; i<MAX; ++i )
    {
        int r = rand();
        vi0[i] = r;
    }


    vector<int> vi(MAX);
    list<int> li;

    for( int i=0; i<MAX; ++i )
    {
        int r = vi0[i];
        vi[i] = r;
        li.push_back(r);
    }

    clock_t start = clock();

    sort( vi.begin(), vi.end() );

    clock_t end = clock();
    cout << "Time to sort vector 'vi': '" << (double)(end-start)/CLOCKS_PER_SEC << "'\n";

    start = clock();

    li.sort();

    end = clock();
    cout << "Time to sort list 'li': '" << (double)(end-start)/CLOCKS_PER_SEC << "'\n";

    // Reset values
    li.clear();
    for( int i=0; i<MAX; ++i )
    {
        li.push_back(vi0[i]);
    }

    // Get time to copy values to 'vi', sort them & copy back to 'li'
    start = clock();

    auto x = vi.begin();
    auto i = li.begin();
    while( i != li.end() )
    {
        *x = *i;
        ++x;
        ++i;
    }
    sort( vi.begin(), vi.end() );

    x = vi.begin();
    i = li.begin();
    while( x != vi.end() )
    {
        *i = *x;
        ++i;
        ++x;
    }

    end = clock();
    cout << "Time to copy 'li' to 'vi'. Sort 'vi' and copy values to 'li': '" <<
            (double)(end-start)/CLOCKS_PER_SEC << "'\n";

    return 0;
}

编译代码为：g-O3 CompareListAndArraySorting.cc

输出：

排序向量“vi”的时间：“1.02916”排序列表“li”的时间：“7.87467”将“li”复制到“vi”的时间。对“vi”进行排序并将值复制到“li”：“3.73348”

我想知道，对我来说，这看起来令人费解，列表排序比复制值到向量，向量排序和复制值慢。我想知道你是否知道:

• 这是由于特定的机器加工吗？
• list.sort（）的主要原因是为了节省将值复制到向量的额外空间吗？如果软件没有额外空间分配的问题，会将变量复制到向量，排序

我是否遗漏了练习中的一些要点？

Answer 1

这是由于特定的机器处理吗？

这个问题的一般答案几乎总是肯定的。例如，如果处理器提供SIMD指令来帮助排序，那么对向量进行排序可能比不连续存储在内存中的链表要快得多。内存层次结构的速度也起着巨大的作用，更不用说乱序执行和指令级并行性了。话虽如此，如今主流处理器非常相似，因此性能行为通常不会从一个处理器到另一个处理器发生剧烈变化（至少只要它们是主流x86/ARM桌面/服务器处理器）。

链表速度很慢，因为这是一个不连续的数据结构，执行许多不可预测的内存访问。因此，这会导致执行期间大量管道停滞，从而减慢程序速度。在不久的将来，对向量进行排序的速度肯定会更好，因为最近的SIMD指令集可以加快一些算法的速度，如快速排序或合并排序的变体（例如。比顿排序），经常用于对数据进行有效排序（STL之一应该是主要基于快速排序的导入排序）。更准确地说，AVX-512 （x86-64） 和 SVE （ARM） 将能够加快分区步骤，前提是编译器可以自动矢量化这部分算法，或者实现使用 SIMD 友好代码（通常还不是这种情况）。AFAIK，英特尔 TBB 库能够对此类排序进行矢量化。链接列表不会明显更快，因为硬件供应商几乎无法优化间接内存负载链（无论如何，每次访问都不能超过1个周期）。

list.sort（） 的主要原因是为了节省将值复制到向量的额外空间吗？如果软件在额外空间分配方面没有问题，请将 vals 复制到向量，排序

不仅如此。复制的速度取决于复制的内容。虽然复制int非常便宜，但复制/移动大型复杂对象的成本可能要高得多。如此大的物体仍然可以快速比较。此外，像int这样的基本类型可以引用一个句柄或一种指针，指向一个比较缓慢的大型复杂对象（例如，使用lambda）。因此，这一切都是为了在拷贝成本与比较运算符成本之间找到一个阈值。

在您的例子中，使用向量比使用链接列表要好得多。事实上，链表很少用于高性能算法（几乎总是有更好的数据结构）。