如何高效计算两个巨型向量各元素的两两和？

核心思路：利用有序性+位图批量操作（替代O(n²)遍历） #

当前代码的O(n²)双重循环存在致命问题：非连续内存访问导致缓存命中率极低——向量元素唯一但不连续，nr1+nr2的索引是跳跃式的，每次访问pResult都会触发缓存缺失。而利用两个向量已排序、元素唯一的特性，可以用位图+位运算把复杂度降到O(M+N)（M是取值范围，N是向量元素数），速度提升几个数量级。

具体实现：位图偏移+或操作 #

1. 把第二个向量转成位图：用vector<uint64_t>模拟位图（每64位打包成一个uint64_t），标记所有存在的元素位置。
2. 结果位图批量更新：对第一个向量的每个元素a，把第二个向量的位图向右偏移a位，然后和结果位图做或操作（只要存在任意一对a+b，就标记对应位置为1）。
3. 转换回原格式：如果需要uint8_t类型的结果，再把位图转成对应的vector。

优化后的代码

#include <vector>
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <omp.h> // 可选，用于多线程并行

namespace
{
std::vector<uint32_t> populate(size_t pRange, size_t pValues)
{
    std::vector<uint32_t> result;
    std::srand((unsigned)std::time(0));
    result.reserve(pValues);
    for (uint32_t i = 0; i < pValues; i++)
    {
        uint32_t randomValue = std::rand() % pRange;
        result.push_back(randomValue);
    }
    std::sort(result.begin(), result.end());
    // 确保元素唯一（符合题目要求）
    auto last = std::unique(result.begin(), result.end());
    result.erase(last, result.end());
    return result;
}

// 自定义位图类，基于uint64_t数组，支持偏移或操作
class Bitmap {
private:
    std::vector<uint64_t> data;
    size_t size_bits;

    inline size_t block_idx(size_t bit) const { return bit / 64; }
    inline uint64_t bit_mask(size_t bit) const { return 1ULL << (bit % 64); }

public:
    Bitmap(size_t bits) : size_bits(bits) {
        data.resize((bits + 63) / 64, 0);
    }

    // 设置某一位为1
    void set(size_t bit) {
        if (bit >= size_bits) return;
        data[block_idx(bit)] |= bit_mask(bit);
    }

    // 将当前位图偏移offset位后，或到目标位图中
    void shift_or(Bitmap& target, size_t offset) const {
        if (offset >= target.size_bits) return;
        const size_t start_block = block_idx(offset);
        const uint64_t shift_left = offset % 64;
        const uint64_t shift_right = 64 - shift_left;
        const size_t src_block_count = data.size();

        // 处理第一个块的跨块偏移
        if (start_block < target.data.size()) {
            const uint64_t val = data[0];
            target.data[start_block] |= val << shift_left;
            if (shift_left != 0 && start_block + 1 < target.data.size()) {
                target.data[start_block + 1] |= val >> shift_right;
            }
        }

        // 处理中间的块
        for (size_t i = 1; i < src_block_count; i++) {
            const size_t target_idx = start_block + i;
            if (target_idx >= target.data.size()) break;
            const uint64_t val = data[i];
            target.data[target_idx] |= val << shift_left;
            if (shift_left != 0 && target_idx + 1 < target.data.size()) {
                target.data[target_idx + 1] |= val >> shift_right;
            }
        }
    }

    // 转换为uint8_t向量（兼容原接口）
    std::vector<uint8_t> to_uint8_vector() const {
        std::vector<uint8_t> vec(size_bits, 0);
        for (size_t i = 0; i < data.size(); i++) {
            const uint64_t val = data[i];
            for (size_t j = 0; j < 64; j++) {
                const size_t bit_pos = i * 64 + j;
                if (bit_pos >= size_bits) break;
                vec[bit_pos] = (val >> j) & 1;
            }
        }
        return vec;
    }
};
}

void calculateVectorSums(std::vector<uint32_t> const& pVector1,
                         std::vector<uint32_t> const& pVector2,
                         std::vector<uint8_t>& pResult)
{
    const size_t max_b = pVector2.back();
    const size_t max_sum = pVector1.back() + max_b + 1;

    // 构建vector2的位图
    Bitmap b_bitmap(max_b + 1);
    for (uint32_t b : pVector2) {
        b_bitmap.set(b);
    }

    // 初始化结果位图
    Bitmap result_bitmap(max_sum);

    // 并行处理vector1（可选，需开启OpenMP）
    #pragma omp parallel for
    for (size_t i = 0; i < pVector1.size(); i++) {
        const uint32_t a = pVector1[i];
        b_bitmap.shift_or(result_bitmap, a);
    }

    // 转换回原格式
    pResult = result_bitmap.to_uint8_vector();
}

int main(void)
{
    auto vector1 = populate(2000000, 150000);
    auto vector2 = populate(2000000, 150000);

    std::vector<uint8_t> output;
    calculateVectorSums(vector1, vector2, output);

    // 验证：统计唯一和的数量
    size_t unique_count = 0;
    for (uint8_t val : output) {
        if (val) unique_count++;
    }
    std::cout << "唯一和的数量：" << unique_count << std::endl;
    return 0;
}

进一步优化方向 #

1. SIMD指令加速 #

可以用AVX2/AVX-512指令集优化shift_or操作，一次处理4个/8个uint64_t块，比如用_mm256_or_si256批量执行或操作，能把内存操作速度提升4-8倍。

2. 多线程并行 #

示例代码中已经加入了OpenMP的并行循环，只要编译器开启OpenMP支持（比如GCC加-fopenmp参数），就能利用多核CPU同时处理多个a的偏移或操作，完全无锁（因为或操作是幂等的，多个线程修改同一个uint64_t元素不会冲突）。

3. GPU加速（适合超大规模数据） #

如果CPU优化仍不够，可以用CUDA/OpenCL实现GPU加速：

• 把向量数据复制到GPU显存，用线程块处理每个a，批量执行位图偏移或操作；
• 利用GPU的大规模并行性，一次处理成千上万的a元素，效率远超CPU。不过需要额外的开发成本，且数据传输到GPU有一定开销，适合数据量特别大的场景。

为什么原bitset方案慢？ #

你之前用bitset速度慢，是因为std::bitset是固定大小的模板类，动态场景下不够灵活，且手动位操作是逐位处理的，没有批量优化。而自定义的Bitmap用uint64_t打包，一次处理64位，缓存命中率更高，批量操作的开销被摊薄，速度会远快于逐位操作的bitset。

内容的提问来源于stack exchange，提问作者oddstar