coding 4 fun試合まとめ

チームのプログラミングコンテストでは、テキストファイルを与え、20の常用語を削除した後、出現頻度の上位10語を統計します.
ハッシュテーブル、c++言語実装を採用しています.
1.mmapを使用して、コンテンツをメモリにマッピングします.
2.テキスト分割、境界条件の処理、ranges[]で各区間の開始と終了位置を指定します.
3.Workerスレッドでブロック処理を行い、各単語に対してハッシュテーブルの対応する位置で検索し、挿入します.
4.Workerスレッド終了後、統計結果のあるハッシュテーブルが得られ、結果をフィルタリング(常用単語20個を除く)しvectorにロードする.
5.std::algorithmのheapを使用してスタックを構築し、最初の10要素を取り出します.
最適化
1.freadではなくmmapを使用する:freadはまずディスクからメモリのカーネル空間にコンテンツをコピーし、ユーザー状態に移行し、mmapに比べて1回のコピーが多くなる.
2.ハッシュ表を1枚だけ採用し、マルチスレッド間の結合を避け、挿入操作時にロックをかけず、CASのような原子操作を採用した.

asm volatile(
“lock;
\t”
“cmpxchgq %3, %2″
: “=a”(old)
: “0″(0), “m”(*p), “r”(np)
: “memory”);

cmpxchgqについての紹介はこちらをご覧ください.IntelフォーマットアセンブリとLinuxのAT&Tフォーマットが異なることに注意してください.
3.最後に単語をフィルタリングするときは、長さを判断し、合わないものをそのまま見逃すことで、比較回数を減らすことができます.
まとめ
1.前処理(マッピング、分割)に時間がかかり、CPUを十分に活用していないため、ブロックに分けて読み込んで処理すれば、より効果的である可能性がある.
2.最後に、濾過後の結果を格納するために巨大なheapを簡単に構築し、スタックを構築した.この一歩はよく考えていないので、もっと良い最適化案があるはずです.
3.単一チェーンテーブルを用いて衝突を処理し、この単一チェーンテーブルは末尾にのみ挿入され、削除操作はなく、CAS操作自体の原子性を加えることでinsert操作の原子性を保証できるが、この操作にはバグがあるようだ.
4.ロックもシステム呼び出しも時間がかかるので、正確性を保証する前提で、できるだけ使わなくてもいいです.