「マルチスレッド線型探索」の版間の差分

@@ 1行目: / 1行目: @@
-'''マルチスレッド線型探索'''とは、通常は1個ずつ候補を見ていく[[線型探索]]を、
+'''マルチスレッド線型探索'''とは、通常は1個ずつ候補を見ていく[[線型探索]]を、一度に複数の候補を見ることで[[高速化]]することを狙ったテクニックである。
-一度に複数の候補を見ることで[[高速化]]することを狙ったテクニックである。
+== 概要 ==
+線形探索は単純に総当たりで[[データ]]を探す手法である。線形探索は単純であるが故に[[並列処理]]に都合がよく、処理終了通知などを除き基本的に[[スレッド]]間の[[同期]]の必要がなく、[[ロック]]が発生しないため、[[並列度]]を限りなく高めることができる。
+このため[[マルチスレッド]]化や[[GPGPU]]化などにより高速化を望めるというものである。
+なお、このアルゴリズムに限った話ではないが、対象となるデータ数が極めて少ない場合には、スレッド生成コスト（スレッド生成に要する時間）やデータ転送コストが主目的の処理時間を上回ってしまう場合があるので注意する必要がある。
+ちなみにこの問題を改善する方法として[[スレッドプール]]や[[hUMA]]などの技法が考案されている。
 ==使用例==