1

最近，我一直在思考可以遍历数组的所有方法，并想知道其中哪种方法效率最高（和最低）。我写了一个假设问题和五个可能的解决方案。

问题

给定一个包含多个元素的int数组，为每个元素分配任意数字的最有效方法是什么？arrlen42

解决方案 0：显而易见

for (unsigned i = 0; i < len; ++i)
    arr[i] = 42;

解决方案 1：相反的明显

for (unsigned i = len - 1; i >= 0; --i)
    arr[i] = 42;

解决方案 2：地址和迭代器

for (unsigned i = 0; i < len; ++i)
{   *arr = 42;
    ++arr;
}

解决方案3：反向地址和迭代器

for (unsigned i = len; i; --i)
{    *arr = 42;
     ++arr;
}

解决方案 4：解决疯狂问题

int* end = arr + len;
for (; arr < end; ++arr)
    *arr = 42;

推测

显而易见的解决方案几乎总是被使用，但我想知道下标运算符是否会导致乘法指令，就好像它被写成*(arr + i * sizeof(int)) = 42.

反向解决方案试图利用如何比较而i不是0可能len减轻减法运算。因此，我更喜欢解决方案 3而不是解决方案 2。另外，我读到数组被优化为可以向前访问，因为它们是如何存储在缓存中的，这可能会给解决方案 1带来问题。

我不明白为什么解决方案 4会比解决方案 2效率低。解决方案 2增加了地址和迭代器，而解决方案 4只增加了地址。

最后，我不确定我更喜欢这些解决方案中的哪一个。我认为答案也因编译器的目标架构和优化设置而异。

如果有的话，你更喜欢哪一个？

4

4 回答 4

10

只需使用std::fill.

std::fill(arr, arr + len, 42);

在您提出的解决方案中，在一个好的编译器上，两者都不应该比其他的更快。

于 2013-09-16T08:08:11.777 回答
6

ISO 标准并没有强制要求在代码中做事的不同方式的效率（除了某些收集算法的某些 big-O 类型的东西），它只是强制要求它的功能。

除非您的数组大小有数十亿个元素，或者您希望每分钟设置数百万次，否则使用哪种方法通常不会产生丝毫差异。

如果您真的想知道（我仍然认为这几乎肯定是不必要的），您应该在目标环境中对各种方法进行基准测试。测量，不要猜测！

至于我更喜欢​​哪个，我的第一个倾向是优化可读性。只有当存在特定的性能问题时，我才会考虑其他可能性。那将是简单的：

for (size_t idx = 0; idx < len; idx++)
    arr[idx] = 42;
于 2013-09-16T08:11:40.637 回答
1

我不认为这里的性能是一个问题——如果有的话（我可以想象编译器为它们中的大多数生成相同的程序集），微优化几乎没有必要。

选择最易读的解决方案；标准库为您提供std::fill，或更复杂的分配

for(unsigned k = 0; k < len; ++k)
{
    // whatever
}

因此，对于查看您的代码的其他人来说，您在做什么是显而易见的。使用 C++11，您还可以

for(auto & elem : arr)
{
    // whatever
}

只是不要试图在没有任何必要的情况下混淆你的代码。

于 2013-09-16T08:12:26.027 回答
0

对于几乎所有有意义的情况，编译器会将所有建议的情况优化为同一件事，而且不太可能产生任何影响。

曾经有一个技巧，如果你向后运行循环，你可以避免自动预取数据，这在一些奇怪的情况下实际上使它更有效。我不记得确切的情况，但我希望现代处理器无论如何都会识别向后循环和向前循环以进行自动预取。

如果您的应用程序在大量元素上执行此操作非常重要，那么查看阻塞访问和使用非临时存储将是最有效的。但在您这样做之前，请确保您已将数组的填充确定为一个重要的性能点，然后对当前代码和改进后的代码进行测量。

我可能会回来一些实际的基准测试来证明“它没有什么不同”，但我有一个差事要在一天中为时已晚之前运行......

于 2013-09-16T10:23:35.083 回答