Check if an indexed array in bash is sparse or dense

Question

I have a dynamically generated, indexed array in bash and want to know whether it is sparse or dense.
An array is sparse iff there are unset indices before the last entry. Otherwise the array is dense.

The check should work in every case, even for empty arrays, very big arrays (exceeding ARG_MAX when expanded), and of course arrays with arbitrary entries (for instance null entries or entries containing *, \, spaces, and linebreaks). The latter should be fairly easy, as you probably don't want to expand the values of the array anyways.

Ideally, the check should be efficient and portable.

Here are some basic test cases to check your solution. Your check can use the hard-coded global variable name a for compatibility with older bash versions. For bash 4.3 and higher you may want to use local -n isDense_array="$1" instead, so that you can specify the array to be checked.

isDense() {
  # INSERT YOUR CHECK HERE
  # if array `a` is dense, return 0 (success)
  # if array `a` is sparse, return any of 1-255 (failure) 
}
test() {
  isDense && result=dense || result=sparse 
  [[ "$result" = "$expected" ]] ||
  echo "Test in line $BASH_LINENO failed: $expected array considered $result"
}

expected=dense
a=(); test
a=(''); test
a=(x x x); test

expected=sparse
a=([1]=x); test
a=([1]=); test
a=([0]=x [2]=x); test
a=([4]=x [5]=x [6]=x); test
a=([0]=x [3]=x [4]=x [13]=x); test

To benchmark your check, you can use

a=($(seq 9999999))
time {
  isDense
  unset 'a[0]'; isDense
  a[0]=1; unset 'a[9999998]'; isDense
  a=([0]=x [9999999999]=x); isDense
}

user_6770384 · Answer

Approach

Non-empty, dense arrays have indices from 0 to ${#a[*]}-1. Due to the pigeonhole principle, the last index of a sparse array must be greater or equal ${#a[@]}.

Bash Script

To get the last index, we assume that the list of indices ${!a[@]} is in ascending order. Bash's manual does not specify any order, but (at least for bash 5 and below) the implementation guarantees this order (in the source code file array.c search for array_keys_to_word_list).

isDense() {
  [[ "${#a[*]}" = 0 || " ${!a[*]}" == *" $((${#a[*]}-1))" ]]
}

For small arrays this works very well. For huge arrays the check is a bit slow because of the ${!a[*]}. The benchmark from the question took 9.8 seconds.

Loadable Bash Builtin

The approach in this answer only needs the last index. But bash only allows to extract all indices using ${!a[*]} which is unnecessary slow. Internally, bash knows what the last index is. So if you wanted, you could write a loadable builtin that has access to bash's internal data structures.

Of course this is not a really practical solution. If the performance really did matter that much, you shoudn't use a bash script. Nevertheless, I wrote such a builtin for the fun of it.

Loadable bash builtin

The space and time complexity of above builtin is indepent of the size and structure of the array. Checking isdense a should be as fast as something like b=1.

user_7366100 · Answer

UPDATE: (re)ran tests in an Ubuntu 20 VM (much better times than previous tests in a cygwin/bash env; times are closer to those reported by Socowi)

NOTE: I populated my array with 10 million entries ({0..9999999}).

Using the same assumption as Socowi ...

To get the last index of an array, we assume that the list of indices ${!a[@]} is in ascending order. Bash's manual does not specify any order, but (at least for bash 5 and below) the implementation guarantees this order

... we can make the same assumption about the output from typeset -p a, namely, output is ordered by index.

Finding the last index:

$ a[9999999]='[abcdef]'
$ typeset -p a | tail -c 40
9999998]="9999998" [9999999]="[abcdef]")

1st attempt using awk to strip off the last index:

$ typeset -p a | awk '{delim="[][]"; split($NF,arr,delim); print arr[2]}'
9999999

This is surprisingly slow (> 3.5 minutes for cygwin/bash) while running at 100% (single) cpu utilization and eating up ~4 GB of memory.

2nd attempt using tail -c to limit the data fed to awk:

$ typeset -p a | tail -c 40 | awk '{delim="[][]"; split($NF,arr,delim); print arr[2]}'
9999999

This came in at a (relatively) blazing speed of ~1.6 seconds (ubuntu/bash).

3rd attempt saving last array value in local variable before parsing with awk

NOTES:

as Socowi's pointed out (in comments), the contents of the last element could contain several characters (spaces, brackets, single/double quotes, etc) that make parsing quite complicated
one workaround is to save the last array value in a variable, parse the typeset -p output, then put the value back
accessing the last array value can be accomplished via array[-1] (requires bash 4.3+)

This also comes in at a (relatively) blazing speed of ~1.6 seconds (ubuntu/bash):

$ lastv="${a[-1]}"
$ a[-1]=""
$ typeset -p a | tail -c 40 |  awk -F'[][]' '{print $(NF-1)}'
9999999
$ a[-1]="${lastv}"

Function:

This gives us the following isDense() function:

initial function

unset -f isDense

isDense() {
  local last=$(typeset -p a | tail -c 40 | awk '{delim="[][]"; split($NF,arr,delim); print arr[2]}')
  [[ "${#a[@]}" = 0 || "${#a[@]}" -ne "${last}" ]]
}

latest function (variable=last array value)

unset -f isDense

isDense() {
  local lastv="${a[-1]}"
  a[-1]=""
  local last=$(typeset -p a | tail -c 40 | awk -F'[][]' '{print $(NF-1)}')
  [[ "${#a[@]}" = 0 || "${#a[@]}" -ne "${last}" ]]
  rc=$?
  a[-1]="${lastv}"
  return "${rc}"
}

Benchmark:

from the question (minus the 4th test - I got tired of waiting to repopulate my 10-million entry array) which means ...
keep in mind the benchmark/test is calling isDense() 3x times
ran each function a few times in ubuntu/bash and these were the best times ...

Socowi's function:

real    0m11.717s
user    0m9.486s
sys     0m1.982s

oguz ismail's function:

real    0m10.450s
user    0m9.899s
sys     0m0.546s

My initial typeset|tail-c|awk function:

real    0m4.514s
user    0m3.574s
sys     0m1.442s

Latest test (variable=last array value) with Socowi's declare|tr|tail-n function:

real    0m5.306s
user    0m4.130s
sys     0m2.670s

Latest test (variable=last array value) with original typeset|tail-c|awk function:

real    0m4.305s
user    0m3.247s
sys     0m1.761s

user_8584929 · Answer

isDense() {
  local -rn array="$1"
  ((${#array[@]})) || return 0
  local -ai indices=("${!array[@]}")
  ((indices[-1] + 1 == ${#array[@]}))
}

To follow the self-contained call convention:

test() {
  local result
  isDense "$1" && result=dense || result=sparse 
  [[ "$result" = "$2" ]] ||
  echo "Test in line $BASH_LINENO failed: $2 array considered $result"
}

a=(); test a dense
a=(''); test a dense
a=(x x x); test a dense

a=([1]=x); test a sparse
a=([1]=); test a sparse
a=([0]=x [2]=x); test a sparse
a=([4]=x [5]=x [6]=x); test a sparse
a=([0]=x [3]=x [4]=x [13]=x); test a sparse

Check if an indexed array in bash is sparse or dense

3 Answers

Approach

Bash Script

Loadable Bash Builtin