「マルチスレッド線型探索」を編集中

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

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

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

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

==関連項目==
* [[マルチスレッド]]
* [[線型探索]]
* [[OpenMP]]

[[category: アルゴリズム]]