1

C++11 といくつかの標準アルゴリズムを使用した簡単な例で遊んでいますが、 または を使用するかどうかはわかりませstd::accumulateんstd::for_each。問題は、単語の文字数を数えることです。たとえば、「abracadabra」と入力すると、次のようになります。

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

私の最初のカットは を使用することでしたstd::accumulate。これが自然に見える理由は、値 (一連の周波数) を実際に累積しているためです。また、私は最近関数型プログラミングを行っていて、リストを折りたたむaccumulateことの自然な翻訳のように思えました。

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)。

これらの例で、どちらか一方を優先する正当な理由はありますか? これまでのコメントと回答から、私が蓄積している値が自明ではない場合、たとえば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;
}
4

1 に答える 1

2

個人的には、そのような蓄積を書かなかったでしょう：

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: @Davestd::map のルックアップ時間は O(ln(n)) ですが、ベクトルは O(1) です。したがって、パフォーマンスの考慮事項があります。マップの固定コストはベクターよりも高くなることにも注意してください。これは小さいですが、注目に値します。

From: @Davestd::vector の固定サイズは約 256*4 (1024) ですが、map のサイズは約 12* 一意の文字数 (最小 12 最大 3072) です。そのため、最新のマシンでは実際のスペースを考慮していません。ただし、電話などで最適化する価値があるかもしれません。

From: @POW3 番目のポイントは、 std::map を使用すると、空の値をチェックする必要がないため、結果の出力がはるかに簡単になることです。

ベクトル印刷

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

地図印刷

for(auto loop: charCounts) {
    std::cout << "'" << loop.first << "' => " << loop.second << "\n";
}
于 2013-09-15T17:38:14.533 に答える