マルチスレッド線型探索

マルチスレッド線型探索とは、通常は1個ずつ候補を見ていく線型探索を、一度に複数の候補を見ることで高速化することを狙ったテクニックである。

概要

線形探索は単純に総当たりでデータを探す手法である。線形探索は単純であるが故に並列処理に都合がよく、処理終了通知などを除き基本的にスレッド間の同期の必要がなく、ロックが発生しないため、並列度を限りなく高めることができる。 このためマルチスレッド化やGPGPU化などにより高速化を望めるというものである。

なお、このアルゴリズムに限った話ではないが、対象となるデータ数が極めて少ない場合には、スレッド生成コスト（スレッド生成に要する時間）やデータ転送コストが主目的の処理時間を上回ってしまう場合があるので注意する必要がある。 ちなみにこの問題を改善する方法としてスレッドプールやhUMAなどの技法が考案されている。

使用例

• 複数の動画を同時に再生し、どこかにあったはずの発言やイベント、ネタなどを探す
• 大量のスタッフを動員してチョコレートを開封し続け、金のチケットを探す

関連項目

• マルチスレッド
• 線型探索