为什么生成更多的随机数据要慢得多？

Question

我想生成大量随机数。我编写了以下 bash 命令（请注意，我在这里使用 cat 用于演示目的；在我的实际用例中，我将数字输送到一个过程中）：

for i in {1..99999999}; do echo -e "$(cat /dev/urandom | tr -dc '0-9' | fold -w 5 | head -n 1)"; done | cat

数字打印速度非常低。但是，如果我生成的数量较少，速度会快得多：

for i in {1..9999}; do echo -e "$(cat /dev/urandom | tr -dc '0-9' | fold -w 5 | head -n 1)"; done | cat

请注意，唯一的区别是 9999 而不是 99999999。

这是为什么？数据是否缓冲在某处？有没有办法优化这个，让随机数 piped/streamed 立即变成 cat？

Answer 1

Why is this?

生成 {1..99999999} 100000000 个参数然后解析它们需要从 bash 分配大量内存。这会严重拖延整个系统。

此外，大块数据从 /dev/urandom 读取，其中约 96% 的数据被 tr -dc '0-9' 过滤掉。这会显着耗尽熵池并使整个系统停止运转。

Is the data buffered somewhere?

每个进程都有自己的缓冲区，所以：

cat /dev/urandom 正在缓冲
tr -dc '0-9' 正在缓冲
fold -w 5 正在缓冲
head -n 1 正在缓冲
管道左侧 - shell，有自己的缓冲区
右侧 - | cat 有自己的缓冲区

那是6个缓冲位。即使忽略来自 head -n1 和管道右侧 | cat 的输入缓冲，也有 4 个输出缓冲区。

另外，拯救动物和 stop cat abuse。使用 tr </dev/urandom，而不是 cat /dev/urandom | tr。有趣的事实 - tr 不能将文件名作为参数。

Is there a way to optimize this, so that the random numbers are piped/streamed into cat immediately?

删除整个代码。

只根据需要从随机源中获取尽可能少的字节。要生成 32 位数字，您只需要 32 位 - 不再。要生成一个 5 位数字，您只需要 17 位 - 四舍五入到 8 位字节，即只有 3 个字节。 tr -dc '0-9' 是一个很酷的技巧，但绝对不应该在任何实际代码中使用它。

奇怪的是，从那里复制代码，您可以：

for ((i=0;i<100000000;++i)); do echo "$((0x$(dd if=/dev/urandom of=/dev/stdout bs=4 count=1 status=none | xxd -p)))"; done | cut -c-5
# cut to take first 5 digits

但这仍然是 令人无法接受的 慢，因为它为每个随机数运行 2 个进程（我认为只取前 5 位数字会产生不好的分布）。

我建议使用 $RANDOM，在 bash 中可用。如果不是，如果您 真的想要 /dev/urandom（并且真的知道您为什么想要它），请使用 $SRANDOM。如果没有，我建议用真正的编程语言编写 /dev/urandom 的随机数生成，例如 C、C++、python、perl、ruby。我相信有人可以把它写成 awk.

下面看起来不错，但仍然将二进制数据转换为十六进制，只是稍后将它们转换为十进制是 shell 无法处理二进制数据的解决方法：

count=10;
# take count*4 bytes from input
dd if=/dev/urandom of=/dev/stdout bs=4 count=$count status=none |
# Convert bytes to hex 4 bytes at a time
xxd -p -c 4 |
# Convert hex to decimal using GNU awk
awk --non-decimal-data '{printf "%d\n", "0x"[=11=]}'

Answer 2

你为什么要运行循环这个？您只需运行一组这些命令即可生成所有内容，例如：

cat /dev/urandom | tr -dc '0-9' | fold -w 5 | head -n 100000000

即只生成一个数字流，而不是单独生成它们。

我赞成为此使用另一种语言的建议，它应该更有效率。例如，在 Python 中，它只是：

from random import randrange
for _ in range(100000000):
    print(randrange(100000))

Answer 3

@SamMason 给出了迄今为止最好的，因为他完全取消了循环：

cat /dev/urandom | tr -dc '0-9' | fold -w 5 | head -n 100000000

尽管如此，仍有很大的改进空间。首先，tr -dc '0-9' 只使用了来自 /dev/urandom 的大约 4% :-) 其次，根据最终使用这些随机数的方式，获取这些随机数可能会产生一些额外的开销去掉前导零——这样一些数字就不会被解释为八进制。让我提出一个更好的选择，使用 od 命令：

outputFile=/dev/null  # For test. Replace with the real file.
count=100000000

od -An  -t u2  -w2  /dev/urandom | head -n $count >$outputFile

使用 time 命令进行的快速测试表明这大约比 tr 版本快四倍。而且确实没有必要使用“另一种语言”，因为 od 和 head 都经过了高度优化，并且整个过程都以本机速度运行。

注意： 上述命令将生成 16 位整数，范围从 0 到 65535（含）。如果您需要更大的范围，那么您可以选择 32 位数字，这将为您提供从 0 到 4294967295 的范围：

od -An  -t u4  -w4  /dev/urandom | head -n $count >$outputFile

如果需要，最终用户可以使用模除法将它们缩小到所需的大小。

为什么生成更多的随机数据要慢得多？

Why is generating a higher amount of random data much slower?

bash

random

pipe

brace-expansion