マルチスレッド線型探索

提供: MonoBook
ナビゲーションに移動 検索に移動

マルチスレッド線型探索(読み:まるちすれっどせんけいたんさく)とは、通常は1個ずつ候補を見ていく線型探索を、一度に複数の候補を見ることで高速化することを狙ったテクニックである。

概要[編集 | ソースを編集]

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

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

使用例[編集 | ソースを編集]

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

関連項目[編集 | ソースを編集]

参考文献[編集 | ソースを編集]