C++とpthreadによるマルチスレッド処理で巨大な配列の最大値を高速に求める方法

問題の概要

非常に大きな整数型配列が与えられたとき、マルチスレッド処理を活用して配列内の最大値を効率的に求めます。データサイズが大きいほど、並列処理による高速化の効果は顕著になります。

例

入力配列が {10, 14, -10, 8, 25, 46, 85, 1673, 63, 65, 93, 101, 125, 50, 73, 548} の場合、

この配列の最大要素は 1673 です。

アルゴリズム

• 配列のサイズを total_elements（総要素数）とします。
• N 個のスレッドを作成します。
• 各スレッドは (total_elements / N) 個ずつの配列要素を担当し、その範囲内の最大値を求めます。
• 最後に、各スレッドが報告した最大値の中から全体の最大値を算出します。

この手法は「分割統治」の考え方に基づいています。大規模なデータを複数のスレッドで並列に走査することで、シングルスレッドでの線形探索よりも短時間で最大値を特定できます。

サンプルコード

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 10
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) typedef struct struct_max {
    int start;
    int end;
    int thread_num;
} struct_max;
int arr[] = {10, 14, -10, 8, 25, 46, 85, 1673, 63, 65, 93, 101, 125, 50, 73, 548};
int max_values_from_threds[MAX];
void *thread_fun(void *arg) {
    struct_max *s_max = (struct_max*)arg;
    int start = s_max->start;
    int end = s_max->end;
    int thread_num = s_max->thread_num;
    int cur_max_value = INT_MIN;
    for (int i = start; i < end; ++i) {
        if (arr[i] > cur_max_value) {
            cur_max_value = arr[i];
        }
    }
    max_values_from_threds[thread_num] = cur_max_value;
    return NULL;
}
int main() {
    int total_elements = SIZE(arr);
    int n_threads = 4;
    struct_max thread_arr[4];
    for (int i = 0; i < 4; ++i) {
        thread_arr[i].thread_num = i + 1;
        thread_arr[i].start = i * 4;
        thread_arr[i].end = thread_arr[i].start + 4;
    }
    pthread_t threads[4];
    for (int i = 0; i < 4; ++i) {
        pthread_create(&threads[i], NULL, thread_fun, &thread_arr[i]);
    }
    for (int i = 0; i < 4; ++i) {
        pthread_join(threads[i], NULL);
    }
    int final_max_val = max_values_from_threds[0];
    for (int i = 0; i < n_threads; ++i) {
        if (max_values_from_threds[i] > final_max_val) {
            final_max_val = max_values_from_threds[i];
        }
    }
    printf("Maximum value = %d\n", final_max_val);
    return 0;
}

コードの解説

struct_max 構造体： 各スレッドに割り当てる情報をまとめています。担当範囲の開始インデックス（start）、終了インデックス（end）、およびスレッド番号（thread_num）を保持します。

thread_fun 関数： 各スレッドが実際に実行する処理です。初期値を INT_MIN（int 型の最小値）として設定し、担当範囲の要素を順に比較して範囲内の最大値を求めます。結果はグローバル配列 max_values_from_threds にスレッド番号をキーとして格納されます。

main 関数： 配列を4つに分割し、pthread_create() でスレッドを生成して各範囲の探索を並列に開始します。pthread_join() ですべてのスレッドの完了を待機した後、各スレッドの結果を比較して全体の最大値を出力します。

出力

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Maximum value = 1673