arrays - bash 。最快最有效的数组搜索

Question

我需要在 bash 进程中多次执行数组搜索。我需要知道什么是最快最有效的方法。我知道该怎么做。问题的重点是如何以最快的方式做到这一点。现在，我这样做:

#!/bin/bash

array_test=("text1" "text2" "text3" "text4" "text5")
text_to_search="text4"

START=$(date +%s.%N)

for item in "${array_test[@]}"; do
    if [ ${item} = "${text_to_search}" ]; then
        echo "found!!"
        break
    fi
done

END=$(date +%s.%N)
DIFF=$(echo "$END - $START" | bc)
echo $DIFF

通过这段代码我们可以测量时间。

假设我们的数组中有 300 项或更多项。有没有更快的方法？我需要提高性能。谢谢。

编辑 我正在使用 bash 4.2。真正的数组有换行符:

array_test=(
"text1"
"text2"
"text3"
"text4"
"text5"
)

Answer 1

最快版本(适用于大型数组)

在 array[*] 中使用 grep -qFx。
<子> -q 抑制输出并存在于第一个匹配项上。
-F 搜索固定字符串而不是正则表达式。
-x 搜索整行而不是子字符串。这确保了搜索字符串 b 与元素 abc 不匹配。

if ( IFS=$'\n'; echo "${array[*]}" ) | grep -qFx "$text_to_search"; then
    echo "found!"
fi

假设:要搜索的数组和文本都不包含换行符。

也可以搜索带有换行符的文本，只要有一个已知的未使用字符可以存储在 bash 变量中即可。我发现 \x1E(ASCII 控制字符 »记录分隔符«)效果很好。改编后的版本如下所示:

export d=$'\x1E' # unused character, here "Record Seperator"
if ( IFS="$d"; echo "$d${array[*]}$d" ) | grep -qF "$d$text_to_search$d"; then
    echo "found!"
fi

理论上，您可以通过在数组切片上使用多个并行 grep 来进一步加快速度。但是，速度如此之快(请参阅下面的结果)，您可能永远不会遇到并行搜索得到返回的情况。

测试

我使用了一个大小为 1'000'000 的数组，生成如下:

size=$((10 ** 6))
array_test=($(seq -f 'text%.0f' 1 "$size"))

(顺便说一下:使用 {1..1000000} 比 seq 慢数量级)

搜索模式是所述数组的最后一个条目

text_to_search="text$size"

测试了三种搜索方式

1. 您的方法使用 for 循环
2. printf %s\\n "数组[@]"| grep -qFx
3. (IFS=$'\n'; echo "array[*]";) | grep -qFx

结果如下:

1. 65.5 秒
2. 59.3 秒
3. 00.4 秒(是的，那是小数点前的零)