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

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

[3,5,8,9] 

Result : 1 (9-8)

的问题是，在最后的测试，以实现拼图使用量非常大的数字，我的代码是不够优化。

之前找到minimu区别，我的阵列一样，排序：

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

你有什么我可以做的事情有足够optimzed要经过测试的任何想法？顺便说一句，我对Bash几乎一无所知，我在python中用usaly代码。

来源

2015-12-19 Kevin M

有什么问题吗？它的复杂性是N（LOG N）..那么问题是什么？ – SMA

我无法在编码上实现代码挑战，因为“它没有足够优化”，正如它在网站上所说的@SMA –

我怀疑这会有帮助;外壳根本不适合快速数值计算。唯一的区别是我已经将数组索引操作的数量减半。

# 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 
}

来源

2015-12-19 17:47:14 chepner

非常感谢你，第一个完美的作品，我不知道有可能做一个for循环就像在bash中一样，它使用很多less资源 –

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)

来源

2015-12-19 18:50:45 Cyrus

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

回答

相关问题