線形探索を高速化する単純なアイデア

線形探索というアルゴリズムがあります。これは、プログラムを勉強する上では避けて通れない基本的なアルゴリズムです。

線形探索とはなにかというと、ある配列があったとき、その中身を先頭から最後尾にかけて順番に走査していこうという考え方のことです。線形探索はこのように単純でわかりやすいので実装が簡単ですが、配列の要素数が大きくなるとそれだけ時間がかかるようになってしまいます。これを解消するようなアルゴリズムとして2分探索がありますがその話はまた後日しますん。

今回はこの線形探索をどうしたら高速化できるかを思いついたので、実装して検証してみましょうという企画です。

さっそく本題に入りましょう。今回、思いついたアイデアというのは線形探索のスレッド化です。

説明のために図を用意しました。（褒めて）

f:id:be116:20161213191652p:plain:w500

通常の線形探索では図のようにそれぞれの配列を一つずつ探索していきます。それと比較して、スレッドを使用した線形探索では複数の要素を複数のスレッドにより一気に探索することができます。

線形探索はメモリ効率が最適です。メモリ効率とは次に探索する要素がどれだけ近くにあるかを示す指標です。メモリ効率がいい、すなわち、次に探索する要素が近くにあれば、探索の時間は短縮されます。もし、次に探索する要素が遠くにあった場合には、それだけ探索に時間がかかるようになります。線形探索では、常に隣の要素を探索するためメモリ効率は最適と言っても過言では無いでしょう。（間違ってたら助けて）スレッドを使用した線形探索においても、常に近いところを探索し続けるため、メモリ効率は良いといえます。

次に実装の話に移りましょう。

スレッドは共有メモリを使用しています。説明がめんどくさいので適当ですが、１つのプログラムで走っているよ、だからどのすれっどからも１つのメモリ空間にアクセスできるよみたいなものです。

線形探索にスレッドを適用する場合、この共有メモリの概念が重要になります。スレッドには関数のように返り値を返すといった仕様がありません。そこでグローバル変数を使用して、返り値の代わりをしてもらいます。

というところで飽きてきたのでプログラムはこうなります。

逐次処理

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 8192

int flg = 0;
int* array;

int main()
{
  int i;
  clock_t start, end;

  array = (int*)calloc(sizeof(int),SIZE);

  array[SIZE-1] = 1;

  start = clock();

  for (i=0; i<SIZE; i++) {
    if (array[i]) {
      flg = 1;
      break;
    }
  }

  end = clock();

  if (flg)
    printf("みつけたぞ\n");
  else
    printf("なんぞこれ\n");

  printf("%lf秒もかかったぞ\n", (double)(end - start) / CLOCKS_PER_SEC);

  free(array);

  return 0;
}

スレッドを使用

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <thread>
#include <vector>

#define SIZE 8192
#define THREAD_NUM 32

int flg = 0;
int* array;

void func(int i)
{
  if (array[i]) {
    flg = 1;
    return;
  }
  return;
}

int main()
{
  int i, j;
  clock_t start, end;

  array = (int*)calloc(sizeof(int),SIZE);

  array[SIZE-1] = 1;

  std::vector<std::thread> th_group;

  start = clock();

  for (i=0; i<SIZE; i+=THREAD_NUM) {
    for (j=0; j<THREAD_NUM; j++) {
      th_group.push_back(std::thread(func, i+j));
    }
    for (auto itr=th_group.begin(); itr!=th_group.end(); ++itr) {
      itr->join();
    }
    th_group.resize(0);
    if (flg) {
      break;
    }
  }

  end = clock();

  if (flg)
    printf("みつけたぞ\n");
  else
    printf("なんぞこれ\n");

  printf("%lf秒もかかったぞ\n", (double)(end - start) / CLOCKS_PER_SEC);

  free(array);

  return 0;
}

要素数8192で比較。

逐次処理

みつけたぞ
0.000000秒もかかったぞ

スレッドを使用した場合

みつけたぞ
0.859375秒もかかったぞ

あれれー、おかしいぞー？スレッド化のメリットよりもスレッド生成のコストが上回ったっていうことなのかー？そーなのかー。

といった話でした。

まとめ。

なんでもかんでもスレッド使えばいいってもんじゃないね。はぁ…。

ぶろぐめんどくさい

技術系の記事と漫画レビューが入り混じった混沌

線形探索を高速化する単純なアイデア