Python：排列列表的内存高效随机抽样

Question

我想对 Python 中列表的 n 个随机排列进行采样。

这是我的代码：

obj = [    5     8     9 ... 45718 45719 45720]
#type(obj) = numpy.ndarray

pairs = random.sample(list(permutations(obj,2)),k= 150)

虽然代码可以满足我的要求，但它会导致内存问题。我有时会在 CPU 上运行时收到错误 Memory error，而在 GPU 上运行时，我的虚拟机会崩溃。

如何使代码以更节省内存的方式工作？

Answer 1

您可以避免列出可能占用大量内存的排列迭代器。您可以通过使用 replace=False.

对列表进行采样来生成随机排列

import numpy as np
obj = np.array([5,8,123,13541,42])
k = 15
permutations = [tuple(np.random.choice(obj, 2, replace=False)) for _ in range(k)]
print(permutations)

这个问题会变得更难，例如，如果您在随机排列中不施加重复。

编辑，无重复代码

我认为这是非重复情况的最佳方法。

我们在置换矩阵中对 1 to n**2-n 中的所有可能置换进行索引，其中应避免对角线。我们对索引进行采样，不重复也不列出，然后将样本映射到排列的坐标，然后从矩阵的索引中得到排列。

import random
import numpy as np

obj = np.array([1,2,3,10,43,19,323,142,334,33,312,31,12])
k = 150
obj_len = len(obj)

indexes = random.sample(range(obj_len**2-obj_len), k)
def mapm(m):
    return m + m //(obj_len) +1

permutations = [(obj[mapm(i)//obj_len], obj[mapm(i)%obj_len]) for i in indexes]

这种方法不基于任何假设，不加载排列，而且性能也不基于 while 循环未能插入重复项，因为从来没有生成重复项。

Answer 2

这完全避免了使用 permutations：

count = len(obj)
def index2perm(i,obj):
    i1, i2 = divmod(i,len(obj)-1)
    if i1 <= i2:
        i2 += 1 
    return (obj[i1],obj[i2])
pairs = [index2perm(i,obj) for i in random.sample(range(count*(count-1)),k=3)]

Answer 3

基于 Pablo Ruiz 的出色回答，我建议将他的采样解决方案包装到一个生成器函数中，该函数通过跟踪它已经产生的内容来产生独特的排列：

import numpy as np

def unique_permutations(sequence, r, n):
    """Yield n unique permutations of r elements from sequence"""
    seen = set()
    while len(seen) < n:
        # This line of code adapted from Pablo Ruiz's answer:
        candidate_permutation = tuple(np.random.choice(sequence, r, replace=False))

        if candidate_permutation not in seen:
            seen.add(candidate_permutation)
            yield candidate_permutation

obj = list(range(10))
for permutation in unique_permutations(obj, 2, 15):
    # do something with the permutation

# Or, to save the result as a list:
pairs = list(unique_permutations(obj, 2, 15))

我的假设是，您正在对大量可能排列的一小部分进行采样，在这种情况下，冲突将非常罕见，因此保持 seen 集合不会很昂贵。

警告：如果您要求的排列比给定的输入可能的排列更多，则此函数是一个无限循环。它也会变得越来越慢 n 接近可能的排列数量，因为碰撞会越来越频繁。

如果我要将这个函数放入我的代码库中，我会在顶部放置一个屏蔽来计算可能排列的数量，并在 n 超过该数量时引发 ValueError 异常，并且如果 n 超过该数字的十分之一或类似数字，则可能会输出警告。

Python：排列列表的内存高效随机抽样

Python: Memory-efficient random sampling of list of permutations

python

permutation