在几乎均匀地采样的随机顺序中，在不大的内存需求的情况下以均匀采样的随机顺序进行迭代

Question

我想在0到N-1范围内迭代整数，其中N是一个大数字。for i in range(N):可以很容易地完成。

但是，我想以随机顺序迭代数字。这也可以使用以下操作很容易完成：

from random import shuffle
a = list(range(N))
shuffle(a)
for i in a:
      do_something(i)

这种方法的问题在于它需要将存储在内存中存储整个数字列表。（shuffle(range(N))引起错误）。这使得我对于大型N的目的不实用。

我想拥有一个迭代器的对象（就像range(N)一样），该对象不会将所有数字存储在内存中（再次，就像range(N)一样），并且以随机顺序进行迭代。

现在，当我说"随机顺序"时，实际上是说该顺序是从(0,1,...,N-1)的所有排列集合中的均匀分布中采样的。我知道这个数字可能非常大（N!），因此，如果迭代器需要表示哪个排列，则需要在内存中非常大。

因此，我可以在"实际上不是统一的分布"的"随机顺序"上定下来，从某种意义上说，我尚未定义。

如果我有这样的迭代器，这就是我的操作方式：

a = random_order_range(N) # this object takes memory much smaller than then factorial of N
for i in a:
    do_something(i)

有什么想法如何完成？

---

edit1：

实际上，我真正感兴趣的是，如果可能的话，内存消耗甚至小于~N ...对于某些k，可能会大于1的O(k*N)。

Answer 1

import functools, random, itertools  
from collections import deque
import random
from bloom_filter import BloomFilter
def random_no_repeat(random_func, limit):
    already_returned = BloomFilter()
    count = 0
    while True:
        i = random_func()
        if i not in already_returned:
            count += 1
            already_returned.add(i)
            yield i
            if (count == limit):
                break
def count_iter_items(iterable):
    counter = itertools.count()
    deque(itertools.zip_longest(iterable, counter), maxlen=0)  # (consume at C speed)
    return next(counter)
N = 1e5
random.seed(0)
random_gen = random_no_repeat(functools.partial(random.randint, 0, int(N)))
for index, i in  enumerate(random_gen):
    print(index, i)

Answer 2

我对空间和时机要求不太确定，但这应该比N!要少得多 - 通过固定限制low和high和seen的set，也不应该在内部。需要过度长时间绘制一个数字，然后当您简单地从n bruteforce中检查并检查seen中是否：

import random 
def random_range(N): 
    seen = set()
    low = 0
    high = N
    seen = set()
    while low < high:
        k = random.choice(range(low,high))
        if k in seen:
            # already drafted - try again
            continue
        else:
            yield k
            seen.add(k)
            # fix lower
            while low in seen:
                seen.remove(low)
                low += 1
            # fix upper
            while high-1 in seen:
                seen.remove(high-1)
                high -= 1
for i in random_range(20):
    print(i, end = ", ")

输出：

7, 2, 5, 18, 11, 3, 6, 10, 14, 9, 15, 17, 19, 0, 16, 4, 1, 12, 13, 8,

如果您将N插入2^63，则seen集将在缩小之前增长巨大，因为击中低点或高点的概率很小 - 这是最大的内存消耗。

。

运行时间变得更糟，Fuller seen在range(low,high)方面，因为它可能需要2000继续击中seen中没有的随机数：

# pseudo 
seen = { 1-99999,100001-99999999999 } 
low = 0
high = 99999999999+2

这不是"可降低"，并且只有3个数字可以从range(0, 99999999999+2)中绘制 - 但是进入这样的事情的机会也很小。

您的选择; o）