在 bash 中找到排序数组中数字之间的最小差异

Question

我正在做一个代码挑战，对于给定的数字，我必须找到最小的差异。例如：

[3,5,8,9]

Result : 1 (9-8)

问题是实现拼图的最终测试使用了大量数字，我的代码优化不够。

在找到最小差异之前，我对数组进行了排序：

IFS=$'\n' sorted=($(sort -n <<<"${array[*]}"))

然后，我在数组上做一个 for 循环以找到最小的，但是这需要太多时间所以我尝试做 i+4 而不是 i++ 但我不认为这才是真正的问题。

这是我找到最小值的代码：

smallest=5000
for (( i=2; i<N; i=$((i+1)) ));do
    diff=$((${sorted[i]}-${sorted[i-1]}))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
done

你知道我可以做些什么来优化一些东西来通过测试吗？顺便说一句，我对 Bash 几乎一无所知，我通常在 python.

中编写代码

Answer 1

我怀疑这会有帮助； shell 根本不适用于快速数值计算。唯一的区别是我将数组索引操作的数量减少了一半。

# No need to guess at an upper bound
N=${#sorted[@]}
smallest=$((${sorted[N-1]} - ${sorted[0]}))

current=${sorted[0]}
for next in "${sorted[@]:1}"; do
    diff=$(($next - $current))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
    current=$next
done

我不认为使用 C 风格的循环会比遍历数组元素更快，但如果是，下面是如何处理：

# Indices run from 0 to N-1
# No need for $((...)); ((...)) is already an arithmetic context
current=${sorted[0]}
for ((i=1; i<N; i++)); do
    next=${sorted[i]}
    diff=$(($next - $current))
    if [ $diff -lt $smallest ]; then
        smallest=$diff
    fi
    current=$next
done

最后，您可以尝试完全不使用数组，而只是从标准输入中读取数据。

sort -n <<EOF |
5
3
9
8
EOF
| {
    smallest=5000   # Now you do have to guess again
    read current
    while read next; do
        diff=$((next - current))
        if [ $diff -lt $smallest ]; then
            smallest=$diff
        fi
        current=$next
    done
}

Answer 2

array=(5 3 9 8)
IFS=$'\n' sorted=($(sort -n <<<"${array[*]}"))
for ((i=0;i<${#sorted[@]}-1;i++)); do 
  diff[$i]="$((${sorted[$i+1]}-${sorted[$i]})) (${sorted[$i+1]}-${sorted[$i]})"
done
IFS=$'\n' result=($(sort -n <<<"${diff[*]}"))
echo "Result : ${result[0]}"

输出：

Result : 1 (9-8)

在 bash 中找到排序数组中数字之间的最小差异

Find the minimum difference between numbers in a sorted array in bash

arrays

bash

optimization

puzzle