GitHub - iwiwi/parallel-radix-sort: An implementation of optimized parallel radix sort
概要 OpenMP を用いて並列化した Radix Sort です． また，参考文献の論文で提案されている高速化手法である Buffer based scheme を採用しています． キーのみのソートと，キー・値のペアのソートができます． キーとして，以下の型がとれます． 符号付き整数 (char, short, int, long, long long) 符号なし整数 (上のに unsigned がついたもの) 浮動小数点数 (float, double) 使い方 sample.cc や measure.cc を見ると大体分かると思います． コンパイル時に -fopenmp を付けないと並列化されないので注意してください． 性能 measure.cc で 2 億要素の int 配列のソートの時間を測ります． 実行例: % g++ -O3 measure.cc -fopenmp % ./a
priority_queue
priority_queue とは priority_queueとは優先度つき待ち行列と呼ばれるもので、 挿入された順序どおりに要素の取り出しを行うのではなく、 優先度の高い要素から先に取り出す待ち行列。 例えば、int型を格納するpriority_queueで、整数の値をそのまま優先度として用いると、値の大きな整数から順に取り出される待ち行列になります。 priority_queueはヒープと呼ばれるデータ構造が使われます。 このヒープは、完全な2分木の形をしていて、 木の各ノードは自身より下にの要素よりも大きな値を持ちます。 そのため、最大の値を持つ要素は常に木の根に含まれていることになります。 この木の根にある要素を取り出すことで常に最大の値を持つ要素を取り出します。 ヒープの実装は、ランダムアクセス([]を使った添字によるアクセス)のできるデータ構造を使って行えます。 STL にお
N-gram コーパスの作成コスト - やた＠はてな日記
今の方法で N-gram コーパスを作成するのにかかるコストを調べてみました．といっても，N-gram コーパスのマージや頻度によるカットオフにかかるコストは含んでいません．参考程度です． 実験環境は Core 2 Duo 1.6GHz で，コーパス作成用のプロセスには 2GiB のメモリを割り当てました． ※ グラフの作成には http://code.google.com/intl/ja/apis/chart/docs/chart_wizard.html を利用しています． 形態素 N-gram コーパスの作成コスト 入力は MeCab の出力 2GiB で，N は 1 〜 9 まで試しました． 公開している N-gram コーパスの作成に用いたのは約 470GiB なので，同じ環境で並列化しないと 20 時間くらいかかることになります．また，現在の 5-gram を基準にすると，7-g
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
