此答案特定于从大型数组中删除多个值的情况,其中性能很重要。
投票最多的解决方案是 (1) 数组上的模式替换,或 (2) 遍历数组元素。第一个速度很快,但只能处理具有不同前缀的元素,第二个有 O(n*k),n=数组大小,k=要删除的元素。关联数组是相对较新的功能,在最初发布问题时可能并不常见。
对于完全匹配的情况,在 n 和 k 较大的情况下,可以将性能从 O(n k) 提高到 O(n+k log(k))。在实践中,O(n) 假设 k 远低于 n。大多数加速是基于使用关联数组来识别要删除的项目。
性能(n 数组大小,要删除的 k 值)。性能衡量用户时间的秒数
N K New(seconds) Current(seconds) Speedup
1000 10 0.005 0.033 6X
10000 10 0.070 0.348 5X
10000 20 0.070 0.656 9X
10000 1 0.043 0.050 -7%
正如预期的那样,current
解与 N*K 呈线性关系,并且fast
解实际上与 K 呈线性关系,常数要低得多。由于额外的设置,解决方案比 k=1 时的解决方案稍慢fast
。current
“快速”解决方案:数组=输入列表,删除=要删除的值列表。
declare -A delk
for del in "${delete[@]}" ; do delk[$del]=1 ; done
# Tag items to remove, based on
for k in "${!array[@]}" ; do
[ "${delk[${array[$k]}]-}" ] && unset 'array[k]'
done
# Compaction
array=("${array[@]}")
current
从投票最多的答案中以解决方案为基准。
for target in "${delete[@]}"; do
for i in "${!array[@]}"; do
if [[ ${array[i]} = $target ]]; then
unset 'array[i]'
fi
done
done
array=("${array[@]}")