如何高效实现无放回且不重复的全量随机抽取？——分批次抽取场景的性能优化诉求

你的问题核心在于当前实现的过滤剩余元素操作存在严重性能瓶颈——每次抽取后用列表推导式[i for i in original_list if i not in list(drawn_numbers)]生成剩余列表，本质是对每个元素做一次in检查（时间复杂度O(k)，k为每次抽取的400个元素），再加上整个列表的遍历（O(n)，n为当前剩余元素数量），这就导致每次抽取的时间成本居高不下，哪怕列表逐渐缩小，单次操作的开销依然很大。

最优解决方案：先整体随机打乱，再分块抽取 #

无放回全量抽取所有元素，本质等价于对整个列表做一次随机排列，然后按指定大小分割成若干块。这种方法只需要一次O(n)的打乱操作，之后每次分块都是O(1)的切片（numpy）或低开销的列表切片，总耗时会大幅降低。

方案1：使用numpy实现（推荐，适合大数据量）

numpy的shuffle是原地打乱数组，效率极高，配合array_split可以快速分割成均匀块：

import time
import numpy as np

def efficient_chunked_draw(original_array, chunk_size):
    # 原地打乱数组，时间复杂度O(n)
    np.random.shuffle(original_array)
    # 分割为指定大小的块（这里正好能整除，无需处理剩余元素）
    return np.array_split(original_array, len(original_array) // chunk_size)

# 测试示例
if __name__ == "__main__":
    # 模拟你的50800个数字的源列表
    original_data = np.arange(50800)
    start = time.time()
    all_chunks = efficient_chunked_draw(original_data, 400)
    end = time.time()
    print(f"完成127次抽取总耗时: {end - start:.2f}秒")
    
    # 可以遍历每个块使用
    for chunk_idx, chunk in enumerate(all_chunks, 1):
        print(f"第{chunk_idx}次抽取的前5个元素: {chunk[:5]}...")

方案2：纯Python实现（无需numpy）

如果你的源数据是普通Python列表，用标准库random的shuffle同样高效：

import time
import random

def efficient_chunked_draw_py(original_list, chunk_size):
    # 原地打乱列表
    random.shuffle(original_list)
    # 按步长分割成块
    return [original_list[i:i+chunk_size] for i in range(0, len(original_list), chunk_size)]

# 测试示例
if __name__ == "__main__":
    original_data = list(range(50800))
    start = time.time()
    all_chunks = efficient_chunked_draw_py(original_data, 400)
    end = time.time()
    print(f"完成127次抽取总耗时: {end - start:.2f}秒")

性能对比说明 #

这种方法的总时间复杂度是O(n)（仅一次打乱操作的开销），而你原来的实现时间复杂度是O(n²)（每次抽取都要遍历剩余列表并做元素检查），实际运行时总耗时会从3分57秒降到几百毫秒甚至更短，完全符合预期。

额外提示 #

如果你的源数据不能被原地修改（比如需要保留原始顺序），可以先复制一份再打乱：

# numpy版本
temp_array = original_array.copy()
np.random.shuffle(temp_array)

# Python列表版本
temp_list = original_list.copy()
random.shuffle(temp_list)

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