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 из файла и пытаюсь подготовить около 100 тыс. Сегментов (т. Е. Выходных строк) с 30 идентификаторами каждый, объединенными:.Есть ли способ, которым я мог бы сделать это быстро?

Answer 1

Несмотря на то, что bash действительно является неподходящим инструментом для работы (связанные списки ... см. Комментарии выше), все еще возможно сделать это с приемлемой производительностью, используя coproc и shuf -r.

Немногосложный пример, требует $a сверху:

( 
     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

• -r получает shuf, чтобы не перемешивать, а просто выплевывать случайные элементы без запоминания бесконечно.
• Внешний ( ) необходим, потому что я хотел, чтобы выход цикла перешел на pv для измерения.Это показывает, что у меня есть проблема с этим решением: я не думаю, что coprocs просты в использовании, так как вы не можете прочитать их вывод из подоболочки, и вам нужно подумать о том, как завершить их корректно.shopt -s lastpipe может помочь с некоторыми проблемами.

В целом, это примерно в 200 раз быстрее, чем оригинальная версия (примите это с более чем одним зерном соли), но, конечно, все ещеаналогичный фактор медленнее, чем оптимизированная нативная реализация.