Performance considerations while accessing array elements

Question

I am currently learning some bash in my free time and worked on a few easy coding challenges using bash for fun. Solving the last challenge I observed some weird optimization issues:

# read the number of input values
read N

# read all input values into an array
readarray -n $N P

# sort the input array in an ascending order
PS=($(printf "%s\n" ${P[@]} | sort -n))

# init the current minimum distance of two horses by the max input value plus one
Min=10000001

# iterate over the ascending sorted array
# and find the minimum distance
for ((i = 1; i < N; i++)); do
  # compute the difference between the current and the last
  #D=$((PS[i]-PS[i-1]))
  D=$((-PS[i-1]+PS[i]))

  if [ $D -le $Min ]; then
    Min=$D
  fi
done

# finally print the minimum distnce
echo $Min

Somehow accessing PS[i] and right afterwards PS[i-1] results in the test case of a 100'000 input values to run out of time. Accessing the exact same array elements in the reversed order however results the test case to run through properly. A no- associative array access should take O(1) time, so how is it possible that the order of access can effect the runtime performance? Is there some bash magic going on internally I am not aware of (like arrays being implemented as singly linked lists or something like that??)

A glib comment: if you're worried about performance, don't program with bash. It's known to be slow. — glenn jackman, Nov 27 '15 at 14:49
http://stackoverflow.com/questions/32592662/bash-array-iteration-direction-and-performance - According to the answers to this question, arrays in Bash are linked lists, as you suspected. — Karl Nicoll, Jan 06 '17 at 12:20
bash arrays and maps are associative array, that is, a linked list with kv pairs. so arrays take O(n) time worst case, and so do maps. — Jason Hu, Jan 06 '17 at 13:02

score 0 · Answer 1 · edited May 23 '17 at 12:01

Bash arrays are not arrays in the C sense, since you can have sparse arrays without wasting memory:

a=([1]=0 [100000000]=2 [10000000000]=3)

Normal arrays allow O(1) access because the memory location specified by an index can be calculated by a formula in in O(1), which is usually because the array is stored in contiguous memory and you only need to calculate an offset. Usually, sparse arrays are implemented using linked lists, and even if they were implemented using something else like hashmaps, access may not be O(1).

Performance considerations while accessing array elements

1 Answers1