Bash:以随机索引访问大型数组很慢

Question

当我创建一个大型 bash 数组(即>10000 个元素(时，在随机位置访问它很慢。

请考虑以下示例：

a=($(seq 1000000))
while true; do
idx=$(( ($RANDOM * 32786 + $RANDOM) % 1000000 ))
echo ${a[idx]}
done | pv -r --line-mode 1>/dev/null

这向我展示了每秒可怜的 500 行的吞吐量。 躲避访问会使性能恢复到合理的水平。

这是为什么呢？数组是否以某种方式以奇怪的方式实现？

在一个更现实的例子中，我正在从文件中读取一些 1Mio ID，并尝试准备大约 100k 个存储桶(即输出行(，每个存储桶有 30 个 ID，由:连接。有没有办法让我快速做到这一点？

Answer 1

尽管bash确实是这项工作的错误工具(链表...请参阅上面的评论(，仍然可以使用 coproc 和shuf -r以可接受的性能执行此操作。

一个有点复杂的例子，需要上面的$a：

(
shopt -s lastpipe
coproc rid { 
for e in "${a[@]}"; do
echo "$e"; 
done | shuf -r; 
};
seq 150000 
| while read s; do
for i in {1..10}; do
read -u ${rid[0]} a;
s="$s:$a";
done;
echo "$s";
done
) | pv -ls 150000 >/dev/null

• -rshuf不洗牌，而只是吐出随机元素而不无限期地记住。
• 外部( )是必要的，因为我希望循环的输出转到pv进行测量。这显示了我在这个解决方案中遇到的一个问题：我认为 coprocs 不容易使用，因为您无法从子 shell 读取它们的输出，您必须考虑如何干净地终止它们。shopt -s lastpipe可能有助于解决一些问题。

总而言之，这比原始版本快了大约 200 倍(以不止一粒盐为例(，但当然仍然比优化的本机实现慢一个类似的因素。