3

指定された文字列に各文字が何回出現するかを計算する必要があります。C または C++ で実行する必要があり、任意のライブラリを使用できます。問題は、私は C/C++ 開発者ではないため、自分のコードが最適かどうか確信が持てないことです。最高のパフォーマンスのアルゴリズムを取得したいのですが、それがこの質問の主な理由です。

現在、次のコードを使用しています。

using namespace std;
...

char* text;        // some text, may be very long
int text_length;   // I know this value, if it can help

map<char,int> table;
map<char,int>::iterator it;

for(int i = 0; c = text[i]; i++) {
    it = table.find(c);
    if (it2 == table.end()) {
        table[c] = 1;
    } else {
        table[c]++;
    }
}

std::map 以外の構造を使用することもできますが、どの構造が優れているかわかりません。

ご協力いただきありがとうございます！

4

4 に答える 4

6

バケットソートを使用して正しく実行しています。有限宇宙の要素 (文字など) をカウントするためのより高速な (非並列) アルゴリズムは存在しません。

ASCII 文字のみを使用する場合は、単純な配列を使用してint table[256]C++ コンテナーのオーバーヘッドを回避できます。

Duff のデバイスを使用する(最近の一部の CPU では実際には遅い):

int table[256];
memset(table, 0, sizeof(table));
int iterations = (text_length+7) / 8;
switch(count % 8){
    case 0:      do {    table[ *(text++) ]++;
    case 7:              table[ *(text++) ]++;
    case 6:              table[ *(text++) ]++;
    case 5:              table[ *(text++) ]++;
    case 4:              table[ *(text++) ]++;
    case 3:              table[ *(text++) ]++;
    case 2:              table[ *(text++) ]++;
    case 1:              table[ *(text++) ]++;
                 } while(--iterations > 0);
}

更新: MRAB が指摘したように、テキスト チャンクを並列処理すると、パフォーマンスが向上する可能性があります。ただし、スレッドの作成には非常にコストがかかることに注意してください。そのため、スレッドの作成時間を正当化する最小の文字数を測定する必要があります。

于 2011-07-31T19:46:19.753 に答える
5

256 int の配列を作成できます。各キャラクターに1つ。

それらをすべて 0 に初期化してから、表示される文字ごとに、表のセルをその ascii 値で増やします。

于 2011-07-31T19:47:58.070 に答える
1

256 エントリのテーブルを使用し、文字値でテーブルにインデックスを付けるだけです。

int table[256];
// Wrong, if int table: memset(table, 0, 256);
memset(table, 0, sizeof(table));  // Right
for (int i = 0; i < text_length; i++) {
    table[text[i]]++;
}
于 2011-07-31T19:49:07.303 に答える
1

O(1) 挿入とルックアップにハッシュ マップを使用できます。これにより、O(n log n) ではなく O(n) ランタイムが得られます。Boost、TR1、または C++0x で見つけることができます。

于 2011-07-31T19:49:50.313 に答える