生成大量不重复的随机数序列

Question

生成大量不重复的随机数序列

13

我需要填写一个由编号（测试数据）标识的大量记录的文件。记录数量非常大，这些编号应该是唯一的，并且记录的顺序应该是随机的（或伪随机的）。

我尝试过以下方法：

# coding: utf-8
import random

COUNT = 100000000

random.seed(0)
file_1 = open('file1', 'w')
for i in random.sample(xrange(COUNT), COUNT):
    file_1.write('ID{0},A{0}\n'.format(i))
file_1.close()

但它正在消耗我的所有内存。

有没有一种方法可以生成一个大的洗牌的连续（不一定是唯一的，但最好是连续的）整数序列？使用生成器而不是将整个序列保存在内存中？

- warvariuc

1

@Blender，那种方法不需要在内存中存储所有元素吗？ - Dogbert

3

@Dogbert：向下滚动，跳过最受欢迎的答案。有一些回答涉及内存问题。 - Blender

你真的有一亿个数字吗，还是问题更加普遍？ - Eric O. Lebigot

是的，我需要生成一个几十GB的测试记录文件。 - warvariuc

https://getkerf.wordpress.com/2016/03/30/the-best-algorithm-no-one-knows-about/ - warvariuc

显示剩余2条评论

4个回答

4

也许是这样的（不一定连续，但是会是唯一的）：

from uuid import uuid4

def unique_nums():  # Not strictly unique, but *practically* unique
    while True:
        yield int(uuid4().hex, 16)
        # alternative yield uuid4().int

unique_num = unique_nums()
next(unique_num)
next(unique_num) # etc...

- Jon Clements

看起来很简单！有没有一种方法可以使用种子重复序列？ - warvariuc

1

仅供参考，这并不保证唯一性，尽管它们在前10^8个数字中是唯一的。基本上只是取非常大的随机数，然后观察是否存在冲突。 - DSM

1

这里有一个关于碰撞可能性的参考链接：http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates - Eric O. Lebigot

@EOL 感谢您提供的链接 - 非常有用的参考资料。 - Jon Clements

0

这个程序会让你的内存保持正常，但很可能会损坏你的硬盘 :)

它会生成一个包含从0到100000000的数字序列的文件，然后随机选择其中的位置并将其写入另一个文件。为了“删除”已经被选择的数字，必须重新组织第一个文件中的数字。

import random

COUNT = 100000000

# Feed the file
with open('file1','w') as f:
    i = 0
    while i <= COUNT:
        f.write("{0:08d}".format(i))
        i += 1

with open('file1','r+') as f1:
    i = COUNT
    with open('file2','w') as f2:
        while i >= 0:
            f1.seek(i*8)
            # Read the last val
            last_val = f1.read(8)
            random_pos = random.randint(0, i)
            # Read random pos
            f1.seek(random_pos*8)
            random_val = f1.read(8)
            f2.write('ID{0},A{0}\n'.format(random_val))
            # Write the last value to this position
            f1.seek(random_pos*8)
            f1.write(last_val)
            i -= 1
print "Done"

- jujaro

一个细节：你的 while 循环通常应该写成 for … in xrange(…) 循环。 - Eric O. Lebigot

有一个有趣的生成排列的算法。如果您用文字解释一下，那会让您的答案更易读。请注意，您生成的数字总数为COUNT+1而不是COUNT。我还想指出，通过使用二进制表示而不是文本表示，它显然可以更有效率地实现（磁盘使用因子2）。 - Eric O. Lebigot

在https://dev59.com/3nVC5IYBdhLWcg3wvT7g#196065上有一个类似但更简单的方法（只需一个文件），并且有解释！ - Eric O. Lebigot

感谢 @EOL 的评论，我会添加一些解释。 - jujaro

0

您可以轻松地从读取（在Linux上）/dev/urandom或使用os.urandom()和struct.unpack()获取随机整数：

返回一个包含n个随机字节的字符串，适用于加密使用。

此函数从特定于操作系统的随机源返回随机字节。返回的数据应该足够不可预测，以供加密应用程序使用，尽管其确切质量取决于操作系统实现。在类UNIX系统上，这将查询/dev/urandom，而在Windows上，它将使用CryptGenRandom。如果未找到随机源，则会引发NotImplementedError。

>>> for i in range(4): print( hex( struct.unpack('<L', os.urandom(4))[0]))
... 
0xbd7b6def
0xd3ecf2e6
0xf570b955
0xe30babb6

另一方面，random包：

然而，由于完全是确定性的，它并不适用于所有目的，并且对于加密目的来说完全不适用。

如果您真的需要唯一记录，您应该选择this或EOL提供的答案。

但是假设有真正随机的源，可能会出现重复字符，您将有1/N（其中N = 2 ** sizeof(int)*8 = 2 ** 32）的机会在第一次猜测时命中项目，因此您可以获得(2**32) ** length个可能的输出。

另一方面，当仅使用唯一结果时，您将获得最大值：

product from i = 0 to length {2*32 - i} 
               = n! / (n-length)!
               = (2**32)! / (2**32-length)!

! 表示阶乘，而不是逻辑否定。因此，您只会减少结果的随机性。

- Vyktor

很不幸，我真的需要它们是唯一的。 - warvariuc

@warwaruk 我很好奇为什么，但在这种情况下，只需按照EOL的答案去做（尽管我真的不确定numpy在加密方面的表现如何）。 - Vyktor

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric O Lebigot · Accepted Answer

如果你有一亿个数字，就像这个问题中描述的那样，那么这实际上可以在内存中管理（大约需要0.5GB）。

正如DSM所指出的那样，这可以通过标准模块以高效的方式完成：

>>> import array
>>> a = array.array('I', xrange(10**8))  # a.itemsize indicates 4 bytes per element => about 0.5 GB
>>> import random                                                               
>>> random.shuffle(a)

同时，您也可以使用第三方的NumPy包，这是一种高效管理数组的标准Python工具：

>>> import numpy
>>> ids = numpy.arange(100000000, dtype='uint32')  # 32 bits is enough for numbers up to about 4 billion
>>> numpy.random.shuffle(ids)

(如果您的程序已经使用NumPy，此方法才有用，因为标准模块方法效率差不多)。

这两种方法在我的电脑上花费的时间大约相同(洗牌大约1分钟)，但它们使用的0.5GB对于当前计算机来说并不太大。

PS: 由于可能的排列数量远远超过随机生成器使用的周期，所以洗牌元素太多时不能真正实现随机性。换句话说，Python的洗牌次数比可能的洗牌次数少!