6

私はコードを書きましたが、データは次のとおりです。

unsigned char buf[4096]; // data in chunks of size 4k
unsigned counter[256];

連続する 3 バイトごとに i/p データを合計し、ans を格納しています。例: 温度[4096]; temp[0] = buf[0] + buf[1] + buf[2]; ... 4096年まで

次に、次のコードを使用して、temp の結果からヒストグラムが生成されます。

for(i = 0; i < 4096; i++)
counter[temp[i]]++;

ヒストグラムはソート (バブルソート) され、最も頻繁に発生する上位 8 つの値が取得されます。コードは Linux カーネル (2.6.35) で実行されます。

私が直面している問題は、ソート部分を削除すると、コードの実行にかかる時間が非常に速くなることです (ラップトップで 6 マイクロ秒、gettimeofday 関数を使用して測定)。しかし、並べ替えを導入すると、プロセスが大幅に遅くなります (44 マイクロ秒)。ソート機能自体には 20 マイクロ秒かかりますが、なぜそんなに時間がかかるのか理解できません。cachegrind を使用してメモリ分析を行いましたが、結果は正常であり、プリエンプションを無効にしようとしましたが、それでも違いはありません。誰かがここで私を助けることができれば. ありがとう！

4

2 に答える 2

2

バブルソートは低速で、値を最大4096 * 4096=16,777,216回比較および交換します。最適な値が8つだけ必要な場合は、1つのスイープを選択する方が確実に高速です。そんな感じ。

 const uint_t n = 8;
 uint_t best[n] = {0};
 uint_t index[n] = {0};
 uint_t j;

 for(uint_t i=0; i<4096; i++) {

   if(counter[i] > best[n-1]) {
     for(j=n-2; j && counter[i] > best[j]; j--);           /* Find the insertion position, as our value might be bigger than the value at position n-1. */
     memmove(&best [j+1], &best[j] , (n-1 -j) * sizeof best[0]);      /* Shift the values beyond j up 1  */
     memmove(&index[j+1], &index[j], (n-1 -j) * sizeof index[0]);
     best[j] = counter[i];                                 /* Put the current best value at the top */
     index[j] = i;                                         /* Store the index in the second array to know where the best value was. */
   }
 }

これにより、値を1回だけ比較し、memmove選択配列が小さいため、のコストはごくわずかです。配列を並べ替える必要はありません。このアルゴリズムはO（nm）で、nは配列のサイズ、mは選択したサイズです。最適な並べ替えはO（（n.log2 n）.m）です。したがって、mが小さく、nが大きい場合、一般的なソートアルゴリズムでは無敵です。

編集：インデックスの配列を追加しました。

EDIT2：私が最初に持っていた根本的なバグを修正するために2番目に導入されました。

EDIT3：コメント：memmoveサイズ0は許可されており、基本的にはnopです。

于 2011-07-05T14:02:47.843 に答える
1

バブルソートは遅い... O(N^2) の複雑さ... より高速なパフォーマンスが必要な場合は、ヒープのようなデータ構造を使用するか、配列でクイックソートアルゴリズムを実行します。どちらも O を返します(N log N) 並べ替えプロセスの複雑さ。さらに、どちらの方法も固定長配列でもうまく機能します。

于 2011-07-05T13:56:18.410 に答える