Может ли кто-нибудь объяснить, в чем причина серьезного замедления при повторении массивов bash в обратном направлении?
Пример:
time bash -c 'arr=();for i in {1..100000}; do arr+=( $i );done; echo "Straight"; i=0;while (( $i < 100000 )); do current_element=${arr[$i]}; ((i++));done'
Straight
real 0m0.270s
user 0m0.269s
sys 0m0.002s
time bash -c 'arr=();for i in {1..100000}; do arr+=( $i );done; echo "Reverse"; i=99999;while (( $i > 0 )); do current_element=${arr[$i]}; ((i--));done'
Reverse
real 0m25.569s
user 0m25.589s
sys 0m0.008s
Также
${arr[i-1]} + ${arr[i]}
намного быстрее, чем
${arr[i]} + ${arr[i-1]}
Спасибо за ваше время.
Редактировать:
Баш --версия
GNU bash, версия 4.3.42(1)-выпуск (x86_64-redhat-linux-gnu)
bash
на самом деле являются двусвязными списками, поэтому наивное ожидание состоит в том, что{$arr[$i]}
должна быть операцией O(n), независимо от того, увеличивается или уменьшаетсяi
. Похоже, что может быть какая-то оптимизация кэширования, которая ускоряет доступ для увеличенияi
. Это имеет смысл, учитывая, что основной вариант использования — передать содержимое массива в качестве позиционных параметров. - person chepner   schedule 15.09.2015