如何高效随机抽取n选r组合？Python内存优化需求

问题描述 #

我有一个长度为n的列表的列表，记为superlist = [sublist1, sublist2, ..., sublistn]。需要从中随机抽取大量r元素组合（无需全部抽取），我的场景是n=35、r=8，需抽取10000个组合。

在Python 3.9中运行时遇到问题：组合总数达1e7量级，且每个组合包含长列表，随机打乱操作速度慢、内存占用极高，导致集群因内存占用过高终止进程。我希望找到一种更快、内存占用更低的nCr格式随机组合获取方式，理想情况下无需生成全部组合。

我尝试的代码如下：

import numpy as np
from itertools import combinations as comb
from sklearn.utils import shuffle
largenumber = 10000
all_combs = np.array(list(comb(superlist, r)))
perm = np.arange(all_combs.shape[0])
np.random.shuffle(perm)
if max(perm)<=largenumber:
   required_combs = all_combs[perm]
else:
   required_combs = all_combs[perm][0:largenumber]

但np.random.shuffle和comb(superlist,r)操作极慢且内存占用极高。

解决方案：无重复随机生成组合索引 #

核心思路是直接生成不重复的随机组合索引，不需要先生成所有组合，从根源避免内存爆炸。

方法1：Python内置模块实现（轻量高效） #

利用random模块直接生成不重复索引，通过集合去重确保组合唯一，适合样本量远小于总组合数的场景（比如10000远小于C(35,8)=23535820）。

import random

def random_combinations(superlist, r, num_samples):
    n = len(superlist)
    seen = set()
    result = []
    while len(result) < num_samples:
        # 生成r个不重复的随机索引，排序后转元组（可哈希，用于去重）
        idx_tuple = tuple(sorted(random.sample(range(n), r)))
        if idx_tuple not in seen:
            seen.add(idx_tuple)
            # 根据索引取出对应子列表组合
            result.append([superlist[i] for i in idx_tuple])
    return result

# 使用示例
# superlist = [sublist1, sublist2, ..., sublist35] 替换为你的实际列表
required_combs = random_combinations(superlist, 8, 10000)

优势：

• 内存占用极低：仅存储已生成的索引和最终10000个组合，无需加载百万级全部组合。
• 速度快：跳过生成所有组合的耗时步骤，直接生成目标索引。

方法2：numpy批量生成（适合更大样本量） #

结合numpy的批量随机生成能力，减少Python循环开销，效率更高。

import numpy as np

def np_random_combinations(superlist, r, num_samples):
    n = len(superlist)
    seen = set()
    result = []
    batch_size = 1000  # 批量生成，降低循环次数
    while len(result) < num_samples:
        # 批量生成r个不重复的随机索引
        batches = np.random.choice(n, size=(batch_size, r), replace=False)
        for idx_arr in batches:
            idx_tuple = tuple(np.sort(idx_arr))
            if idx_tuple not in seen:
                seen.add(idx_tuple)
                result.append([superlist[i] for i in idx_tuple])
                if len(result) == num_samples:
                    break
    return result

# 使用示例
required_combs = np_random_combinations(superlist, 8, 10000)

优势：

• 批量生成索引，减少Python循环的性能损耗，比纯Python实现更快。
• 同样无需生成全部组合，内存占用可控。

原代码问题分析 #

• itertools.combinations(superlist, r)会生成所有23535820个组合，每个组合包含8个子列表的引用，转成numpy数组后内存占用会急剧膨胀。
• np.random.shuffle需要对百万级数组进行原地打乱，不仅耗时，还会进一步占用内存资源。

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