アルゴリズムクイックリファレンス 第2版

12.9

 性能を上げるために並列性を加えよ

■

393

リオを提示する。

n

クイーン問題の解の個数を数え上げる例で見たように、このよ

うな近似では、ランダム性を活用して正確な解の推定値を計算することもできる。

試行を繰り返すと推定値の精度が上がるとわかっている場合にこのアプローチを使

うこと。

ブルームフィルタ

は、集まりの中の要素探索において、偽陽性は返すが、絶対に

偽陰性を返さないように注意深く設計されている。一瞥しただけでは、不正解を返

すアルゴリズムは役に立たないと思われるだろう。しかし、

ブルームフィルタ

は、

二次記憶やデータベースシステムを含む探索アルゴリズムの実行時間を劇的に削減

できる。否定解を返せば、要素が本当に集まりにないことがわかり、コストのかか

る探索を行う必要がなくなる。もちろん、

ブルームフィルタ

が失敗に終わる探索を

続けさせることがあるわけだが、これはアプリケーション全体の正しさに影響する

わけではない。

12.9

 性能を上げるために並列性を加えよ

本書に示したアルゴリズムは、単独の逐次型コンピュータを仮定して結果を計算

している。独立に計算可能な下位問題に分割できれば、現代のコンピュータで提供

される資源を活用してマルチスレッド解法を設計できる。例えば、

11

章でスピード

アップが達成できる

クイックソート

の並列化を示した。本書のアルゴリズムの中で、

並列性を活用できるものが他にあるだろうか。

凸包走査

にはソートプロセスがあり、

その後で下側の部分の凸包と上側の部分の凸包が独立に処理されたこ ...