Phần tử lớn nhất trong mảng rất lớn sử dụng pthreads trong C++

Đề bài

Cho mảng số nguyên rất lớn, tìm phần tử lớn nhất sử dụng đa luồng (multithreading).

Ví dụ

Mảng: {10, 14, -10, 8, 25, 46, 85, 1673, 63, 65, 93, 101, 125, 50, 73, 548}

Phần tử lớn nhất: 1673

Thuật toán

1. Gọi kích thước mảng là total_elements
2. Tạo N luồng (threads)
3. Mỗi luồng xử lý (total_elements/N) phần tử, tìm max cục bộ
4. Tính max toàn cục từ các max cục bộ của từng luồng

Chương trình C++ (POSIX threads)

#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;
}

Kết quả

Maximum value = 1673

Lưu ý

• Code sử dụng POSIX threads (pthread) - chuẩn trên Linux/Unix
Trên Windows có thể dùng std::thread (C++11) hoặc Windows API
• Cần compile với flag -lpthread: g++ -pthread program.cpp