主页 / 问题 / 698129
Accepted
Glazgo Cronwerk
Asked:2020-07-27 00:21:36 +0000 UTC2020-07-27 00:21:36 +0000 UTC

哪个更快：向量遍历还是列表遍历？

  • 772

面试的时候，他们问：向量遍历和列表遍历哪个更快，输出值到控制台？我们如何绕过，没有具体说明。我回答说没有区别。我说得对吗？说明：有一个向量容器，我们可以在其上运行，例如，使用迭代器：

std::vector<int> vector{1, 2, 3};
for (auto it = vector.begin(); it != vector.end(); ++it)
{
    qDebug() << *it;
}

有一个容器列表，我们还在其上运行一个迭代器：

std::list<int> values{1, 2, 3};
for (auto it = values.begin(); it != values.end(); ++it)
{
    qDebug() << *it;
}

哪个循环会运行得更快，为什么？使用其他绕过这些容器的方法，哪个循环会运行得更快？这些周期不在采访中，为了清楚起见，我添加了它们。

PS 在这个问题被问到之后：什么是缓存？也许第二个问题与第一个问题有某种关系？如果不缓存整个vector或list，容器遍历时间会不会增加？

c++

4 个回答

  1. Best Answer

    向量稍微快一些 - 由于两个因素：

    1. 没有指针转换，没有不必要的取消引用

    2. 其中没有指针转换——一切都在一个堆中，这意味着具有高度的局部性，因此向量的全部内容很可能会被放置在处理器缓存中（如果不是全部，因为一个非常大的向量，然后是大块），即 以比列表的一般情况快得多的速度，在列表的一般情况下，元素可以分散在整个内存中......

    PS 由于这个问题再次浮出水面:) - 我们将对其进行测量。

    百万列表和向量。排序 - 以便有更多的随机转换到列表中的不同内存位置。

    list<int> L;
vector<int> V;

int main(int argc, const char * argv[])
{
    for(int i = 0; i < 1000000; ++i)
    {
        int r = rand();
        V.push_back(r);
        L.push_back(r);
    }
    L.sort();
    sort(V.begin(),V.end());

    {
        muTimer mu;
        long long int sum = 0;
        for(int i: V) sum += i;
        mu.stop();
        cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
    }
    {
        muTimer mu;
        long long int sum = 0;
        for(int i: L) sum += i;
        mu.stop();
        cout << "Sum " << sum << " for " << mu.duration() << " mks\n";
    }

}

    完整代码在这里。如您所见，差异几乎是向量的 200 倍......所以“稍微快一点” - 我低估了它:)

    • 18

  2. 对于“遍历向量或遍历列表并将值输出到控制台”的问题——正确答案是“相同，因为遍历时间与写入控制台的时间相比可以忽略不计”。

    至于元素的迭代和读取时间，如果列表的元素以任意顺序位于内存中，则列表的遍历会明显变慢。

    与处理列表元素所需的时间相比，取消引用指向列表下一个元素的指针的开销可以忽略不计。

    • 11

  3. 这是一个棘手的分层问题。一旦你得到它，你就可以聪明了。

    1. 从数学的角度来看，渐近地，速度是：O(N)。这两种情况的区别是由N前面的系数决定的，它取决于具体操作的速度：解引用、读取、输出等等。常数可以忽略不计，但实际上它也是存在的。

    2. 从硬件感知元素访问的角度来看，向量会更快，因为处理器缓存针对访问顺序内存块进行了优化，而不是可能分散在整个内存中的小元素。

    3. 从实际的角度来看，访问控制台相对于所有其他操作来说是一个非常慢的操作，因此速度将由它决定。因此，向量和列表之间的差异可以忽略不计。

    4. 作为一个特别的展示，我们讨论了为 STL 集合使用自定义分配器的可能性，这使得关于速度的推理无效，因为我们可以使用不利于顺序访问的数据存储设备。假设我们使用没有缓存的文件系统将内存映射到一个文件......

    此时，对话者失去了自言自语的欲望。

    • 6

  4. 如果你看得更深一点，就会发现 vector 的所有元素都存储在内存的一个连续区域中，并且可以放入缓存中。同时，遍历操作本身对于vector来说可以快一点，因为 只有一个转变。但是，如果您真的感兴趣，可以在 10,000,000 个元素上进行测试。

    • 3

相关问题