python - 无需替换的内存高效随机数迭代器

Question

我觉得这个应该很容易，但经过多次搜索和尝试后我无法找到答案。基本上我有大量的元素，我想随机抽样而不更换。在这种情况下，它们是二维数组中的单元格。我将用于较小数组的解决方案不会转换，因为它需要改组内存数组。如果我必须抽样的数量很少，我也可以随机抽样项目并保留我尝试过的值的列表。不幸的是，我经常不得不对所有细胞中的很大一部分进行取样，尽可能多。

我想创建的是一个迭代器，它使用 itertools、numpy 和/或随机生成下一个随机单元格(x 和 y 索引)的某种组合。另一种可能的解决方案是创建一个迭代器，它会产生下一个介于 0 和 (x_count * y_count) 之间的随机数(无需替换)，我可以将其映射回单元格位置。这两者似乎都不容易实现。

感谢您的任何建议!

这是我目前的解决方案。

import numpy as np
import itertools as itr
import random as rdm

#works great
x_count = 10
y_count = 5

#good luck!
#x_count = 10000
#y_count = 20000

x_indices = np.arange(x_count)
y_indices = np.arange(y_count)

cell_indices = itr.product(x_indices, y_indices)
list_cell_indices = list(cell_indices)
rdm.shuffle(list_cell_indices)

for i in range(25):
    print list_cell_indices[i]

因此，根据目前的回复和我尝试翻译我一无所知的 perl，我明白我能做的最好的是:

import numpy as np
import itertools as itr
import random as rdm

x_count = 10000
y_count = 5000

sample_count = 10000
keep_probability = 0.01


tried_cells = set()
kept_cells = set()

while len(kept_cells) < sample_count:
    x = rdm.randint(0, x_count)
    y = rdm.randint(0, y_count)

    if (x, y) in tried_cells:
        pass
    else:
        tried_cells.add((x, y))
        keep = rdm.random() < keep_probability
        if keep:
            kept_cells.add((x,y))


print "worked"

在大多数情况下，处理时间和使用的内存并没有那么糟糕。也许我可以检查平均单元格 keep_probability 和 sample_count 并针对困难的情况抛出错误。

Answer 1

我认为，如果不为接近 R * C 的样本大小使用大量辅助存储，就无法不放回 地对序列进行采样。虽然有一些巧妙的方法可以减少小样本的存储量，但如果您希望对超过三分之一的数据集进行采样，最好还是创建一个单独的列表。 random.sample 是为此目的的自然选择；坦率地说，我只是将二维 numpy 数组的扁平化版本直接传递给它。 (除非你也需要索引，在这种情况下，随机采样整数并将它们转换成坐标，la hexparrot 的解决方案，是一个合理的方法。)

>>> a = numpy.arange(25).reshape((5, 5))
>>> random.sample(a.ravel(), 5)
[0, 13, 8, 18, 4]

如果您查看 random.sample 的实现，您会看到对于较小的样本量，它已经大致完成了上面 perl 代码所做的工作——跟踪集合中先前选择的项目并丢弃集合中已有的选择。对于更大的样本大小，它会创建输入的副本——这比更大值的集合更有效，因为集合比每个存储项目的列表占用更多空间——并稍微修改 Fisher-Yates shuffle ，当它有 sample_size 项目时停止(即它不会打乱整个列表，所以它比自己打乱整个事情更有效率。)

基本上，我敢打赌你不会比 random.sample 做得更好，除非你用 c 编写一些东西。

但是 -- 我确实找到了这个，您可能会觉得它很有趣:numpy.random.choice .这似乎以 c 速度进行随机抽样，有或没有放回。收获？这是 Numpy 1.7 的新功能!