「マルチスレッド線型探索」の版間の差分
ナビゲーションに移動
検索に移動
imported>GamerBook 細 |
imported>GamerBook 細 |
||
| 1行目: | 1行目: | ||
| − | '''マルチスレッド線型探索''' | + | '''マルチスレッド線型探索'''（読み：まるちすれっどせんけいたんさく）とは、通常は1個ずつ候補を見ていく[[線型探索]]を、一度に複数の候補を見ることで[[高速化]]することを狙ったテクニックである。 |
== 概要 == | == 概要 == | ||
| − | + | [[線形探索]]は単純に総当たりで[[データ]]を探す手法である。 | |
| − | このため[[マルチスレッド]]化や[[GPGPU]] | + | 単純であるが故に[[並列処理]]に都合がよく、処理終了通知などを除き基本的に[[スレッド]]間の[[同期]]の必要がなく、[[ロック]]が発生しないため、[[並列度]]を限りなく高めることができる。 |
| + | このため[[マルチスレッド]]化や[[GPGPU]]化などにより比類なき高速化を望めるというものである。 | ||
| − | + | なお、この[[アルゴリズム]]に限った話ではないが、対象となるデータ数が極めて少ない場合には、スレッド生成コストやデータ転送コストなどの前準備の処理時間が、主目的の処理時間を上回ってしまう場合があるので注意する必要がある。 | |
ちなみにこの問題を改善する方法として[[スレッドプール]]や[[hUMA]]などの技法が考案されている。 | ちなみにこの問題を改善する方法として[[スレッドプール]]や[[hUMA]]などの技法が考案されている。 | ||
2013年8月26日 (月) 02:37時点における版
マルチスレッド線型探索（読み：まるちすれっどせんけいたんさく）とは、通常は1個ずつ候補を見ていく線型探索を、一度に複数の候補を見ることで高速化することを狙ったテクニックである。
概要
線形探索は単純に総当たりでデータを探す手法である。 単純であるが故に並列処理に都合がよく、処理終了通知などを除き基本的にスレッド間の同期の必要がなく、ロックが発生しないため、並列度を限りなく高めることができる。 このためマルチスレッド化やGPGPU化などにより比類なき高速化を望めるというものである。
なお、このアルゴリズムに限った話ではないが、対象となるデータ数が極めて少ない場合には、スレッド生成コストやデータ転送コストなどの前準備の処理時間が、主目的の処理時間を上回ってしまう場合があるので注意する必要がある。 ちなみにこの問題を改善する方法としてスレッドプールやhUMAなどの技法が考案されている。
使用例
- 複数の動画を同時に再生し、どこかにあったはずの発言やイベント、ネタなどを探す
- 大量のスタッフを動員してチョコレートを開封し続け、金のチケットを探す
