找到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中排序數組中數字的最小差異

回答

相關問題