检查 bash 中的索引数组是稀疏还是密集

我在 bash 中有一个动态生成的索引数组，想知道它是否是sparse or dense.
如果在最后一个条目之前有未设置的索引，则数组是稀疏的。否则数组是密集的。

该检查应该在每种情况下都有效，即使是空数组、非常大的数组（扩展时超过 ARG_MAX），当然还有具有任意条目的数组（例如空条目或包含*, \、空格和换行符）。后者应该相当简单，因为您可能无论如何都不想扩展数组的值。

理想情况下，检查应该高效且便携。

以下是一些用于检查您的解决方案的基本测试用例。 您的检查可以使用硬编码的全局变量名称a为了与旧的 bash 版本兼容。对于 bash 4.3 及更高版本，您可能需要使用local -n isDense_array="$1"相反，这样您就可以指定要检查的数组。

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

要对您的支票进行基准测试，您可以使用

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

Approach

非空密集数组的索引来自0 to ${#a[*]}-1。由于鸽巢原理，last稀疏数组的索引必须大于或等于${#a[@]}.

bash脚本

为了获得最后一个索引，我们假设索引列表${!a[@]}是按升序排列的。 Bash 的手册没有指定任何顺序，但是（至少对于 bash 5 及以下版本）实现保证了这个顺序（在源代码文件中array.c搜索array_keys_to_word_list).

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

对于小型阵列，这非常有效。对于巨大的数组，检查有点慢，因为${!a[*]}。该问题的基准测试耗时 9.8 秒。

内置可加载 Bash

这个答案中的方法只需要last指数。但bash只允许提取all索引使用${!a[*]}这是不必要的慢。在内部，bash 知道最后一个索引是什么。因此，如果您愿意，您可以编写一个可加载的内置函数来访问 bash 的内部数据结构。

当然，这不是一个真正实用的解决方案。如果性能真的那么重要，那么您就不应该使用 bash 脚本。尽管如此，我还是为了好玩而编写了这样一个内置函数。

可加载的 bash 内置 https://github.com/schaetzc/bash-loadable-is-array-dense

上述内置函数的空间和时间复杂度与数组的大小和结构无关。检查isdense a应该像这样快b=1.