4

これは簡単なはずなのに、何度も検索してみても答えがわかりません。基本的に、交換せずにランダムな順序でサンプリングしたいアイテムが非常にたくさんあります。この場合、それらは2D配列のセルです。小さい配列に使用するソリューションは、メモリ内の配列をシャッフルする必要があるため、変換されません。サンプリングする必要のある数が少なければ、ランダムにアイテムをサンプリングして、試した値のリストを保持することもできます。残念ながら、私は多くの場合、すべてのセルの非常に大きな割合をサンプリングする必要があります。

私が作成したいのは、次のランダムセル（xおよびyインデックス）を生成するitertools、numpy、および/またはrandomの組み合わせを使用するイテレーターです。別の可能な解決策は、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。また、小さなサンプルサイズのストレージの量を減らす賢い方法はありますが、データセットの約3分の1以上をサンプリングすることが予想される場合は、別のリストを作成する方がよいでしょう。random.sampleこの目的のための自然な選択です。率直に言って、2次元のnumpy配列のフラット化されたバージョンを直接渡します。（インデックスも必要な場合を除いて、その場合は、intをランダムにサンプリングして座標に変換するのが、合理的な方法です。）

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

の実装をrandom.sample見ると、サンプルサイズが小さい場合、上記のperlコードとほぼ同じように実行されていることがわかります。つまり、セット内で以前に選択されたアイテムを追跡し、すでにセット内にある選択を破棄します。サンプルサイズが大きい場合は、入力のコピーが作成されます。これは、値が大きい場合のセットよりもメモリ効率が高くなります。これは、セットが保存されたアイテムごとのリストよりも多くのスペースを占めるためです。また、わずかに変更されたフィッシャー-イェーツシャッフルを実行して停止します。アイテムがある場合sample_size（つまり、リスト全体をシャッフルしないため、自分ですべてをシャッフルするよりも効率的です）。

random.sample基本的に、私の賭けは、cで何かをコーディングしない限り、自分でロールするよりもうまくいくことはないということです。

しかし-私はこれを見つけました、あなたが面白いと思うかもしれません：numpy.random.choice。これは、c速度での置換の有無にかかわらずランダムサンプリングを行うように見えます。キャッチ？Numpy 1.7の新機能です！

于 2012-05-23T23:26:36.967 に答える
3

このアプローチはどうでしょうか。最初に x*y 配列を作成し、それを 2 次元に変形します。次に、各セルを単一の整数で一意に識別できることがわかっているので、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)

どちらが返されますか:

(最初に、製品を介して作成した既存の 2 次元配列をシミュレートします)

[[        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]]

次に、配列 [x][y] を介してセルの内容に変換できる 2 次元座標を返します。

   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

グリッド内のほとんどのセルでテストが失敗する可能性が高いとおっしゃいました。その場合、大量のメモリを使用せずにすでにチェックしたセルを追跡するのは難しいため、セルをランダムにサンプリングすることはお勧めできません。

代わりに、グリッド全体にテストを適用し、合格した要素からランダムな要素を選択する方がよい場合があります。

この関数は、テストに合格したランダムな要素を返します（または、すべてが失敗した場合は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を使用している場合は、xrangeの代わりにrangeを使用してください。

于 2012-05-23T23:22:40.510 に答える
1

すでに O(N=R*C) メモリを使用しているため、イテレータに O(N) メモリを使用することもできます。すべての要素をコピーし、1 次元の場合と同様にランダムに並べ替えます。これは、各要素にアクセスする場合にのみ行うのが合理的なことです。これはあなたの場合です。

（記録のために：そうでなければ、以前にどこにいたかを「覚える」だけでよいので、メモリはそれほど悪い問題ではありません。したがって、すでにアクセスしたインデックスのリストを保持できます。増加するブラックリストを使用して実装すると、拒否サンプリングに非常に長い時間がかかる可能性があるため、各要素にアクセスするように計画してください (最初のソリューションと同等の、減少するホワイトリストを使用して実装することもできます)。

于 2012-05-23T19:43:33.637 に答える
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 に答える