C言語でマルチスレッドを活用した線形検索の実装方法

ここでは、配列内の特定の要素を検索する際に、マルチスレッドの概念をどのように応用できるかを解説します。アプローチは非常にシンプルです。まず複数のスレッドを作成し、配列をいくつかの部分に分割します。そして、それぞれのスレッドが担当範囲の検索を行い、目的の要素が見つかった時点でフラグを立てて識別できるようにします。

サンプルコード

#include <stdio.h>
#include <pthread.h>
#define MAX 16
#define THREAD_MAX 4
int array[MAX] = { 1, 5, 7, 10, 12, 14, 15, 18, 20, 22, 25, 27, 30, 64, 110, 220 };
int key = 18;
int flag = 0; // 要素が見つかったかどうかを示すフラグ
int current_thread = 0;
void* ThreadSearch(void* args) { // 全スレッドで実行される線形検索関数
    int num = current_thread++;
    for (int i = num * (MAX / 4); i < ((num + 1) * (MAX / 4)); i++){
       if (array[i] == key)
          flag = 1; // キーが見つかったらフラグをセット
    }
}
int main() {
    pthread_t thread[THREAD_MAX];
    for (int i = 0; i < THREAD_MAX; i++) { // 複数のスレッドを作成
       pthread_create(&thread[i], NULL, ThreadSearch, (void*)NULL);
    }
    for (int i = 0; i < THREAD_MAX; i++) {
       pthread_join(thread[i], NULL); // すべてのスレッドが完了するまで待機
    }
    if (flag == 1)
       printf("Key element is found\n");
    else
       printf("Key element is not present\n");
}

実行結果

$ gcc 1249.Thread_search.cpp -lpthread
$ ./a.out
Key element is found

プログラムの仕組み

このプログラムでは、16個の要素を持つ配列を4つのスレッドで並行して検索しています。各スレッドは current_thread 変数をインクリメントしながら自身の担当番号を取得し、配列を4等分したうちの1区間（4要素ずつ）を担当します。

POSIXスレッド（pthread）ライブラリを使用しており、pthread_create() でスレッドを生成し、pthread_join() ですべてのスレッドの処理完了を待ち合わせます。全スレッドの終了後、フラグ変数 flag の値を確認することで、キーとなる要素が配列内に存在するかどうかを判定しています。

なお、大規模なデータを扱う場合、このように検索処理を複数のスレッドに分散させることで、シングルスレッドでの線形検索と比べて処理時間を短縮できる可能性があります。