c++ - 使用 for_each 或 accumulate 来计算频率

Question

我一直在玩一个使用 C++11 和一些标准算法的简单示例，我不确定是使用 std::accumulate 还是 std::for_each 。问题是计算单词中的字母数，例如，对于“abracadabra”的输入，您会得到

'a' => 5
'b' => 2
'c' => 1
'd' => 1
'r' => 2

我的第一步是使用 std::accumulate。这看起来很自然的原因是我们确实在积累一个值(一组频率)。另外，我最近一直在做一些函数式编程，accumulate 似乎是 folding 的自然翻译一个列表。

vector<int> charsInWord(const string& text)
{
    return 
        std::accumulate(text.begin(), text.end(), vector<int>(256),
            [] (const vector<int>&v, char c)
            { 
                vector<int> v2(v);
                v2[c]++;
                return v2;
            } );
}

然而，这个解决方案似乎相当麻烦，需要一些时间才能正确解决。此外，即使使用新的 move 语义，我也无法完全说服自己不会有任何不必要的复制。

所以我改为使用 for_each。

vector<int> charsInWord2(const string& text)
{
    vector<int> charCounts(256);
    std::for_each(text.begin(), text.end(),
        [&] (char c)
        {
            charCounts[c]++;
        } );
    return charCounts;
}

这可能更容易编写和理解，我当然对它的效率感到高兴(尽管我怀念 accumulate 的声明式函数式风格)。

在这样的例子中，是否有充分的理由偏爱其中一个？从目前的评论和答案来看，如果我积累的值(value)是不平凡的，比如 STL 容器而不是 int，我应该总是更喜欢 for_each，即使我真的在“积累”。

---

为了完整起见，下面是编译和测试的其余代码

#include <string>
#include <vector>
#include <numeric> // accumulate
#include <algorithm> // for_each 

using std::string;
using std::vector;

#include <iostream>

// ... insert code above ...

int main(int argc, char* argv[])
{
    const vector<int> charCounts = charsInWord("abracadabra");
    for(size_t c=0; c<charCounts.size(); ++c) {
        const int count = charCounts[c];
        if (count > 0) {
            std::cout << "'" << static_cast<char>(c) << "'" << " => " << count << "\n";
        }
    }
    return 0;
}

Answer 1

就我个人而言，我不会这样写 accumulate:

vector<int> charsInWord(const string& text)
{
    std::vector<int> result(256); // One version never copied.

    int count = std::accumulate(text.begin(), text.end(), 0,
            [&result] (int count, char c)
         // ^^^^^^^^^ capture
            { 
                result[c]++;
                return count+1;
            } );
    // Might use count in the log file.
    return result;
}

但如果我这样做，使用 for_each() 似乎同样容易

vector<int> charsInWord2(const string& text)
{
    vector<int> result(256);
    std::for_each(text.begin(), text.end(),
        [&result] (char c)
        {
            result[c]++;
        } );
    return result;
}

我没有发现 for_each 版本有任何问题。

但为什么不用简单的 for()循环？

vector<int> charsInWord2(const string& text)
{
    vector<int> result(256);
    for(char c : text) {result[c]++;}
    return result;
}

在评论中有一些关于使用 std::map 的讨论(然后在一些已删除的问题中)。只是为了在此处捕获并扩展。

我们本可以使用 std::map<char,int>而不是 vector<int> .区别在于:

From: @Dave std::map 的查找时间为 O(ln(n))，而 vector 为 O(1)。所以有性能方面的考虑。另请注意， map 的固定成本将高于 vector 。这虽小但值得注意。

From: @Dave std::vector 的固定大小约为 256*4 (1024)，而 map 的大小约为 12*唯一字符数(最小 12 最大 3072)。所以在现代机器中没有真正的空间考虑。但可能值得在手机等设备上进行优化。

From: @POW第三点是 std::map 使打印结果变得更加容易，因为您不需要检查空值。

vector 打印

for(size_t c=0; c<charCounts.size(); ++c) {
    if (count > 0) {
        std::cout << "'" << static_cast<char>(c) << "' => " << charCounts[c] << "\n";
    }
}

map 打印

for(auto loop: charCounts) {
    std::cout << "'" << loop.first << "' => " << loop.second << "\n";
}