4

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

我想要创建的是一个迭代器，它使用迭代工具、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 并在困难的情况下抛出错误。

4

5 回答 5

4

我相信，如果不使用大量辅助存储来存储接近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 的新功能！

于 2012-05-23T23:26:36.967 回答
3

这种方法怎么样。我首先创建 x*y 数组并将其重塑为二维。然后，知道每个单元格可以由一个整数唯一标识，得到一个从 0 到 (x*y) 的样本。

import numpy

x_count = 10000
y_count = 20000

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

large_table = numpy.arange(y_count * x_count).reshape(y_count, x_count)
print large_table

def get_random_item(sample_size):
    from random import sample
    for i in sample(xrange(y_count * x_count), sample_size):
        y,x = divmod(i, y_count)
        yield (x,y)

for x,y in get_random_item(10):
    print '%12i   x: %5i y: %5i' % (large_table[x][y],  x,y)

返回：

（首先模拟您通过产品创建的现有二维阵列）

[[        0         1         2 ...,      9997      9998      9999]
 [    10000     10001     10002 ...,     19997     19998     19999]
 [    20000     20001     20002 ...,     29997     29998     29999]
 ..., 
 [199970000 199970001 199970002 ..., 199979997 199979998 199979999]
 [199980000 199980001 199980002 ..., 199989997 199989998 199989999]
 [199990000 199990001 199990002 ..., 199999997 199999998 199999999]]

然后，它返回 2-dim 坐标，可以简单地通过 array[x][y] 将其转换为您的单元格内容

   154080675   x: 15408 y:   675
   186978188   x: 18697 y:  8188
   157506087   x: 15750 y:  6087
   168859259   x: 16885 y:  9259
    29775768   x:  2977 y:  5768
    94167866   x:  9416 y:  7866
    15978144   x:  1597 y:  8144
    91964007   x:  9196 y:  4007
   163462830   x: 16346 y:  2830
    62613129   x:  6261 y:  3129

sample() 声明它“用于无替换的随机抽样”，并且这种方法遵循建议“这对于从大量人口中抽样特别快速且节省空间：sample(xrange(10000000), 60)。” 在 python随机页面上找到。

我注意到，虽然我使用 get_random_item() 作为生成器，但底层的 sample() 仍然在生成一个完整的列表，所以内存使用仍然是 y*x + sample_size，但它运行得非常快。

于 2012-05-23T22:41:46.707 回答
1

您已经在使用 O(N=R*C) 内存，因此您不妨为迭代器使用 O(N) 内存。复制所有元素并对它们进行随机排序，就像对一维情况所做的那样。如果您要访问每个元素，这只是一个合理的做法，您说这是您的情况。

（记录在案：否则，记忆并不是一个糟糕的问题，因为你只需要“记住”你以前在哪里。因此你可以保留你已经访问过的索引列表。如果你曾经这样做过这很糟糕计划访问每个元素，因为如果使用不断增长的黑名单来实现拒绝采样可能会花费很长时间。（您也可以使用递减的白名单来实现它，这相当于第一个解决方案。）

于 2012-05-23T19:43:33.637 回答
1

您已经说过，您的网格中的大多数单元格的测试可能会失败。如果是这种情况，随机抽样单元格可能不是一个好主意，因为您将很难在不使用大量内存的情况下跟踪您已经检查过的单元格。

相反，您最好将测试应用于整个网格并从通过它的元素中选择一个随机元素。

此函数返回一个通过测试的随机元素（如果都失败，则返回 None）。它使用很少的内存。

def findRandomElementThatPasses(iterable, testFunc):
    value = None
    passed = 0

    for element in iterable:
        if testFunc(element):
            passed += 1
            if random.random() > 1.0/passed:
                value = element

    return value

你可以这样称呼它：

e = findRandomElementThatPasses((x,y) for x in xrange(X_SIZE)
                                      for y in xrange(Y_SIZE),
                                someFunctionTakingAnXYTuple)

如果您使用的是 Python 3，请使用 range 而不是 xrange。

于 2012-05-23T23:22:40.510 回答
0

在 perl 你可以做这样的事情：

# how many you got and need
$xmax = 10000000;
$ymax = 10000000;
$sampleSize = 10000;

# build hash, dictionary in python
$cells = {};
$count = 0;
while($count < $sampleSize) {
  $x = rand($xmax);
  $y = rand($ymax);
  if(! $cells->{$x}->{$y}) {
    $cells->{$x}->{$y}++;
    $count++;
  }
}
# now grab the stuff
foreach ($x keys %{$cells}) {
  foreach ($y keys %{$cells->{$x}}) {
    getSample($x, $y);
  }
}

没有重复，相当随机，记忆力也不大。

于 2012-05-23T19:38:11.707 回答