代码之家 › 专栏 › 技术社区 › Lior

以几乎均匀采样的随机顺序在长迭代器上迭代而无需大量内存[重复]

permutation iterator python

Lior · 技术社区 · 6 年前

这个问题已经有了答案:

Iteratively generating a permutation of natural numbers 3个答案

我想遍历范围内的整数 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) ),它不会将所有数字存储在内存中(同样,就像 范围(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)

你知道怎么做吗?

编辑1:

实际上,我真正感兴趣的是,内存消耗将比 ~N ,如果可能。。。也许有点像 O(k*N) k 可能比1小得多。

2 回复 | 直到 6 年前

Hadi Farah 6 年前

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)

Patrick Artner 6 年前

我对空间和时间要求不太确定,但这应该远远少于 N! -通过限制 low 和 high 以及 set 属于 seen 内部的也不需要很长的时间来画一个数字,然后当你简单地从N开始并检查是否在 看到 :

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 看到 set在缩小之前会变得很大,因为到达低点或高点的概率很小——这就是造成最大内存消耗的原因。

运行时变得更糟 看到 是关于 range(low,high) 因为它可能需要2000继续命中一个不在 看到 已经:

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

这不是“可还原的”,只剩下3个数字 range(0, 99999999999+2) -但得到这样一件事的机会也有点小。

你的选择;o)