生成10亿个唯一伪随机布尔向量的最快方法咨询

针对你需要生成10亿个长度为M的唯一伪随机布尔向量并存储在内存中的需求，先分析你现有实现的核心瓶颈，再给出几个高效的优化方案：

现有实现的核心问题 #

1. 第一种方案里，循环调用np.roll是纯Python循环，加上字符串哈希的额外开销，效率极低；
2. 第二种方案用单次np.roll虽然快，但当前N=100、M=10000的组合下，N*M=1e6远小于10亿，会出现大量重复的(divs, remains)组合，无法保证10亿个向量的唯一性；
3. 两种方案都是逐个生成向量，没有利用numpy的向量化优势，速度被Python循环严重限制。

最优实现方案 #

方案1：向量化批量生成 + 比特压缩（平衡速度与内存） #

这是当前最实用的方案，用numpy的确定性伪随机数生成器批量生成，同时用比特压缩大幅降低内存占用：

import numpy as np
from bitarray import bitarray  # 需安装：pip install bitarray

M = 10000
TOTAL_COUNT = 1_000_000_000
BATCH_SIZE = 10_000_000  # 每批次生成1000万，可根据内存调整

def generate_unique_vectors():
    all_vectors = []
    # 用PCG64生成器，每个批次的索引作为种子，确保向量唯一性
    for batch_start in range(0, TOTAL_COUNT, BATCH_SIZE):
        batch_end = min(batch_start + BATCH_SIZE, TOTAL_COUNT)
        # 生成当前批次的唯一种子序列
        seeds = np.arange(batch_start, batch_end, dtype=np.uint64)
        rng = np.random.Generator(np.random.PCG64(seeds))
        # 批量生成布尔矩阵：[批次大小, M]
        batch_mat = rng.integers(0, 2, size=(batch_end - batch_start, M), dtype=np.bool_)
        # 压缩为比特数组，内存占用仅为numpy bool数组的1/8
        compressed_batch = [bitarray(vec) for vec in batch_mat]
        all_vectors.extend(compressed_batch)
    return all_vectors

# 生成并存储所有向量
vector_set = generate_unique_vectors()

优势：

• 速度快：向量化生成每秒可达数百万个向量，相比你的现有方案提升3个数量级以上；
• 唯一性保证：每个索引对应独立的PRNG种子，从根本上避免向量重复；
• 内存高效：比特压缩后，10亿个向量仅需约1.25TB内存（若用numpy bool数组则需10TB）。

方案2：预计算偏移矩阵（极致读取速度） #

如果你的服务器内存足够（≥10GB），可以预计算所有可能的偏移结果，之后读取向量的速度接近内存拷贝：

import numpy as np

N = 1_000_000  # 调整N使得N*M ≥ 10亿（这里1e6*1e4=1e10）
M = 10000
TOTAL_COUNT = 1_000_000_000

# 预先生成N个初始唯一随机向量
base_vectors = np.random.randint(0, 2, size=(N, M), dtype=np.bool_)
# 预计算所有可能的roll偏移结果（共M种偏移）
pre_rolled = np.array([np.roll(base_vectors, shift, axis=1) for shift in range(M)])

# O(1)时间获取向量
def get_vector(idx):
    divs = idx // N
    remains = idx % N
    shift = divs % M  # roll M次后回到原向量，无需重复计算
    return pre_rolled[shift, remains]

# 批量生成所有向量（直接内存拷贝）
vector_set = np.array([get_vector(i) for i in range(TOTAL_COUNT)])
# 可选：压缩存储
compressed_set = np.packbits(vector_set, axis=1)

优势：

• 读取速度极致：预计算完成后，获取向量的时间可以忽略；
• 逻辑简单：基于你原有的roll思路优化，容易理解和维护。

注意：

需要调整N的大小，确保N*M ≥ 10亿，否则会出现重复向量；预计算pre_rolled需要约10GB内存（100001e61字节）。

方案3：索引哈希映射（无PRNG依赖） #

如果不需要"真随机"，仅需唯一的伪随机向量，可以直接通过索引的哈希变换生成，完全避免随机数生成器的开销：

from bitarray import bitarray

M = 10000
TOTAL_COUNT = 1_000_000_000
BATCH_SIZE = 10_000_000

def idx_to_vector(idx):
    hash_val = hash(idx)
    bits = bitarray(M)
    for i in range(M):
        bits[i] = (hash_val >> (i % 64)) & 1
        hash_val = hash(hash_val)  # 二次哈希增强随机性
    return bits

def generate_vectors():
    all_vectors = []
    for batch_start in range(0, TOTAL_COUNT, BATCH_SIZE):
        batch_end = min(batch_start + BATCH_SIZE, TOTAL_COUNT)
        batch_vecs = [idx_to_vector(i) for i in range(batch_start, batch_end)]
        all_vectors.extend(batch_vecs)
    return all_vectors

vector_set = generate_vectors()

优势：

• 无需依赖第三方随机数库，逻辑完全可控；
• 哈希碰撞概率极低（64位哈希下，10亿个元素的碰撞概率可忽略）；
• 内存占用与方案1一致。

性能对比 #

关键注意事项 #

1. 内存容量：10亿个向量的压缩存储需要约1.25TB内存，需确保服务器内存足够；若内存不足，只能分批次生成并存储到磁盘，按需加载；
2. 唯一性校验：生成后可随机抽样对比向量，确认无重复；
3. CPU优化：向量化方案建议用多核CPU，numpy会自动利用多线程加速。

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