检查bash中的索引数组是稀疏的还是密集的 [英] Check if an indexed array in bash is sparse or dense

问题描述

我在bash中有一个动态生成的索引数组，我想知道它是稀疏还是密集。
一个数组是稀疏的当且仅当在最后一个条目之前有未设置的索引。否则，数组是密集的。

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

理想情况下，支票应该是高效和便携的。

这里有一些用于检查您的解决方案的基本测试用例。 您的检查可以使用硬编码的全局变量名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
}

推荐答案

方法

非空密集数组的索引从0到${#a[*]}-1。由于归鸽原则，稀疏数组的最后索引必须大于或等于${#a[@]}。

Bash脚本

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

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

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

可加载的Bash Builtin

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

当然，这不是一个真正实用的解决方案。如果表演真的那么重要，你就不应该使用猛烈的脚本。尽管如此，我还是写了这样一个内置程序，只是为了好玩。

Loadable bash builtin

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

这篇关于检查bash中的索引数组是稀疏的还是密集的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！