整数的直方图，不需要循环

Question

我想知道是否有任何STL算法可以产生与以下代码相同的结果：

std::vector<int> data;
std::vector<int> counter(N); //I know in advance that all values in data
                             //are between 0 and N-1

for(int i=0; i<data.size(); ++i)
    counter[data[i]]++;

这段代码输出了我的整型数据的直方图，预定义的箱子大小为1。

我知道应该尽可能避免使用循环，因为STL算法的效率比大多数C ++程序员能想出来的要好得多。

有什么建议吗？

提前感谢您，Giuseppe

- Giuseppe

---

那不应该是 counter[data[... 吗？ - Pradhan

是的，应该的，谢谢。已经更正了... - Giuseppe

Answer 1

好的，您至少可以简化一下循环：

for (auto i : data) 
    ++count[i];

你可以（例如）使用std :: for_each代替：

std::for_each(data.begin(), data.end(), [&count](int i) { ++count[i]; });

...但这对我来说并没有太大（甚至没有）改进。

- Jerry Coffin

Answer 2

我认为没有更有效的方法来完成这个任务。你关于避免循环和大多数情况下使用STL的做法是正确的，但是这只适用于更大且过于复杂的循环，这些循环更难编写和维护，因此可能不是最优的。

从汇编级别来看，计算这个问题的唯一方法就是你在示例中展示的方式。由于C/C++循环可以非常高效地转换为汇编语言，而且没有任何不必要的开销，这让我相信没有任何STL函数能比你的算法更快执行。

有一个名叫count的STL函数，但它的复杂度是线性（O(n)），与您的解决方案相同。

如果你真的想挤出每个CPU周期的最大价值，那么考虑使用C风格的数组和一个单独的计数器变量。向量引入的开销几乎无法测量，但如果有的话，那就是我在这里看到的唯一优化机会。虽然我不建议这样做，但恐怕这是你能从中获得更多速度的唯一方法。

- notadam

Answer 3

您可以使用 for_each 和一个 lambda 函数。请查看以下示例：

#include <algorithm>
#include <vector>
#include <ctime>
#include <iostream>
const int N = 10;
using namespace std;

int main()
{
    srand(time(0));
    std::vector<int> counter(N);
    std::vector<int> data(N);

    generate(data.begin(),data.end(),[]{return rand()%N;});

    for (int i = 0;i<N;i++)
        cout<<data[i]<<endl;

    cout<<endl;

    for_each(data.begin(),data.end(),[&counter](int i){++counter[i];});

    for (int i = 0;i<N;i++)
        cout<<counter[i]<<endl;
}

- amchacon

Answer 4

如果你想要计算向量中元素的出现次数，每个元素至少需要被“访问”一次，这是无法避免的。

像这样的简单循环已经是最有效率的了。你可以尝试展开它，但那可能是你能做到的最好的了。无论使用STL与否，我都怀疑是否有更好的算法。

- Chin

---

嗨！确实，您必须访问向量数据的所有元素。我在考虑类似于EIGEN的LAPAK中实现的优化。例如，他们计算矩阵乘法的算法比使用普通循环获得的速度快得多。 - Giuseppe