我需要生成近 10 亿条唯一整数记录。我尝试使用 awk,但它没有生成超过 500 万条记录。以下是我到目前为止所尝试过的 -
awk -v loop=10000000000 -v range=10000000000 'BEGIN{
srand()
do {
numb = 1 + int(rand() * range)
if (!(numb in prev)) {
print numb
prev[numb] = 1
count++
}
} while (count<loop)
}'
但它没有生成超过 599160237 条记录,并且进程被自动终止
答案1
您可以使用 GNU seq
+sort
首先生成一个唯一的 1B 整数列表(按顺序),然后将sort -R
它们随机打乱。虽然这不具有 CPU 效率,但它与内存无关,因为排序将使用尽可能多的可用内存,然后恢复到临时文件。
这将需要几分钟(取决于您机器的 CPU/Ram/磁盘):
$ seq 1000000000 > 1B.txt
$ ls -lhog 1B.txt
-rw-rw-r-- 1 9.3G Dec 26 17:31 1B.txt
$ sort -R 1B.txt > 1B.random.txt
如果您可以使用具有足够 RAM 的计算机,则可以使用 GNU shuf
:
$ shuf -i 1-1000000000 > 1B.random.txt
根据经验,shuf
我的机器需要约 8GB 的可用内存和约 6 分钟的运行时间。
答案2
最好使用不会分配太多内存的程序来完成任务。但是,随机数生成存在一个问题:如果您需要完全随机数,那么您需要使用“好的”随机数源,例如 /dev/urandom。
我认为这个C程序可以帮助您完成这项任务。它在运行时生成数字,并使用您指定的三个参数:start int、end int 以及要生成的数字。因此,要生成 (0..200) 范围内的 100 个整数,您可以执行以下操作:
./mkrnd 0 200 100
您可能需要重定向到文件,所以这样做
./mkrnd 0 200 100 >randomints.txt
编译很简单,直接做即可gcc mkrnd.c -o mkrnd
(或者我可以帮你编译)。
相信足够快,但我认为仍然需要几个小时才能工作。对于我在 Athlon64 5000+ 上的情况:
% time null ./mkrnd 0 1000000000 10000000
real 0m33.471s
user 0m0.000s
sys 0m0.000s
删除 #if 0 ... #endif 以使其从 /dev/urandom 中获取随机整数(可能会更慢)。
关于内存要求:在 musl 系统上,在整个运行期间,它只需要 4K RSS。
编辑:用clock_gettime 替换gettimeofday 可提供双倍速度。
答案3
在 python3.4 中,您可以生成并使用如下所示的巨大数字:
#!/bin/python3.4
import random
print(random.sample(range(1, 1000000000000),1000000000))
这将打印十亿个唯一的数字
如果存在分配巨大样本的内存问题,那么可以使用范围并循环打印数字,但这将是一个序列,而不是随机的:
x=range(1, 1000000000000)
for i in x:
print (i) #or process i , whatever the operation is.
答案4
进程被终止的原因可能是awk
您的代码遇到的数组存在错误/限制,或者您的代码非常消耗空间,以至于达到了某些基于进程的限制。
我的意思是,您正在尝试构建一个最大索引为 100 亿(基于range
)的数组,其中包含 10 亿个定义值。因此,awk
可能需要为 100 亿个变量预留空间。我不太熟悉这意味着多少空间,但是 100 亿个 16 位整数意味着 18.5 GB,即使很awk
聪明地构建这样一个稀疏数组,它也需要超过 1.8 GB,所以存储你的数字正在生成。
为了能够保持结果的唯一性,您需要将所有先前的值保存在某个地方,因此它必然会占用很大的空间,但其他语言可能会允许算法完成。
那么如何摆脱巨大的内存需求呢?
A.Gordon 提出了一种选择,即依赖一个序列并对其进行洗牌以获得随机性。当要求结果应该真正是数字并且您希望它们来自给定范围时,这种方法很有效。如果范围比从 1 到 N 更复杂,您可以使用 生成序列awk
,然后将其传递给sort -R
。另请参阅我对答案的评论,了解如何使生成数字的范围和计数不同。
一种选择可能是使用加密(散列)函数来生成随机数,但在这种情况下,您无法将范围定义为 1 到 N,因为这些函数通常会产生 N 位输出,并且您无法破坏结果没有产生冲突的风险(集合中的重复数字)。但是,这样的函数将保证轻松产生 10 亿个唯一的输出(因为这些哈希函数被设计为即使有非常大的数量也不会产生相同的输出两次)重复调用)。根据实现的不同,它们的输出可能不是数字而是字符串,并且可以将字符串输出转换为数字,但由于它们的输出大小通常非常大,因此转换产生的数字范围将非常巨大。你可以从这个 Stackoverflow 问题如果您有兴趣探索此选项。
如果您可以冒发生碰撞的风险,即使这种情况不太可能发生,您也可以尝试使用良好的随机源(/dev/urandom 是一个选项)来生成 10 亿个数字。我不知道从中获得 10 亿个唯一号码的可能性有多大,但尝试一下肯定值得一试。但是,没有内存有效的方法来判断结果集中是否存在重复项,因为这需要将所有数字都存储在内存中进行比较。