击.最快速有效的阵列搜索

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

最快的版本（用于大型阵列）

使用grep -qFx在array[*]。_{抑制输出并存在于第一场比赛中。搜索固定字符串而不是正则表达式。搜索整行而不是子字符串。这可确保搜索字符串与元素不匹配。
-q
-F
-xbabc}

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 "array[@]" | grep -qFx
3. (IFS=$'\n'; echo "array[*]";) | grep -qFx

结果如下：

1. 65.5秒
2. 59.3秒
3. 00.4秒（是的，这是小数点前的零）