题目

设计一个线程池来并行查找一个整数向量中的最大值。每个线程负责处理向量的一部分，并找到该部分的最大值。最终，主线程将这些局部最大值合并，得到全局最大值。

简介

在多核处理器的现代计算机中，利用多线程可以显著提高计算密集型任务的性能。本题要求你实现一个线程池，通过并行处理来查找一个整数向量中的最大值。每个线程将处理向量的一个子集，并找到该子集的最大值。主线程将这些局部最大值合并，以确定全局最大值。

要求

1. 线程安全：确保在多线程环境下数据访问和更新不会发生冲突。
2. 线程池：
   • 创建指定数量的线程。
   • 每个线程处理向量的一个子集，并找到该子集的最大值。
3. 合并结果：主线程将所有线程的结果合并，得到全局最大值。
4. 输出结果：打印全局最大值。

实现工具

• 编程语言：C++
• 标准库：<iostream>, <thread>, <vector>, <mutex>, <limits>

代码实现

#include <iostream>
#include <thread>
#include <vector>
#include <mutex>
#include <limits>

// 定义一个类来查找局部最大值
class MaxFinder {
private:
    const std::vector<int>& data_;
    const size_t start_;
    const size_t end_;
    int local_value_;

public:
    MaxFinder(const std::vector<int>& data, size_t start, size_t end)
        : data_(data), start_(start), end_(end), local_value_(std::numeric_limits<int>::min()) {}

    void FindLocalMax() {
        for (size_t i = start_; i < end_; ++i) {
            if (data_[i] > local_value_) {
                local_value_ = data_[i];
            }
        }
    }

    int getLocalMax() const {
        return local_value_;
    }
};

// 定义一个线程池类
class ThreadPool {
private:
    const std::vector<int>& data_;
    const size_t num_threads_;

public:
    ThreadPool(const std::vector<int>& data, size_t num_threads)
        : data_(data), num_threads_(num_threads) {}

    int FindGlobalMax() {
        std::vector<std::thread> threads;
        std::vector<MaxFinder> finders;
        finders.reserve(num_threads_); // 预分配内存

        size_t chunk_size = data_.size() / num_threads_; // 每个线程处理的数据块大小

        for (size_t i = 0; i < num_threads_; ++i) {
            size_t start = i * chunk_size;
            size_t end = (i == num_threads_ - 1) ? data_.size() : start + chunk_size;
            finders.emplace_back(data_, start, end);
            threads.emplace_back(&MaxFinder::FindLocalMax, &finders[i]);
        }

        for (auto& thread : threads) {
            thread.join();
        }

        int global_max = std::numeric_limits<int>::min();
        for (const auto& max_finder : finders) {
            if (max_finder.getLocalMax() > global_max) {
                global_max = max_finder.getLocalMax();
            }
        }

        return global_max;
    }
};

int main() {
    std::vector<int> data = {1, 2, 35, 56, 74, 23, 56, 78, 90, 12, 34, 56, 78, 90, 23, 45, 67, 89};
    size_t num_threads = 4;

    ThreadPool pool(data, num_threads);
    int global_max = pool.FindGlobalMax();

    std::cout << "The global max is: " << global_max << std::endl;

    return 0;
}

代码说明

1. MaxFinder 类：

   • MaxFinder 类用于查找一个子集中的最大值。
   • 构造函数接受一个整数向量、起始索引和结束索引。
   • FindLocalMax 方法遍历子集，找到最大值并存储在 local_value_ 中。
   • getLocalMax 方法返回局部最大值。

2. ThreadPool 类：

   • ThreadPool 类管理线程池，并负责将任务分配给各个线程。
   • 构造函数接受一个整数向量和线程数量。
   • FindGlobalMax 方法创建多个线程，每个线程处理向量的一个子集，并找到该子集的最大值。
   • 所有线程完成后，主线程合并所有局部最大值，得到全局最大值。

3. main 函数：

   • 初始化一个整数向量 data 和线程数量 num_threads。
   • 创建 ThreadPool 对象并调用 FindGlobalMax 方法。
   • 打印全局最大值。

测试

• 编译并运行上述代码，观察输出的全局最大值。
• 尝试改变 data 向量的内容和 num_threads 的值，验证程序的正确性和性能。