再帰シェルの最大機能を高速化するために並列性を使用しますか?

再帰シェルの最大機能を高速化するために並列性を使用しますか?

配列で最も高い値(350 int値)を見つけるにはmax関数が必要で、再帰の友人として再帰アプローチを試みました。

max () {
    len=$#
    a=$1
    b=$2
    case $len in
        0)
            echo NaN
            ;;
        1)
            echo $1
            ;;
        2)
            (( a > b )) && echo $a || echo $b
            ;;
        *)
            shift; shift
            max $(max $a $b) $(max $@)
            ;;
    esac
}

驚くほど遅いです。 350個の値は2.6秒かかります。

はい、正式なUNIX方式は次のとおりです。

time (echo ${yvals[@]} | tr " " "\n" | sort -n | tail -n 1 )

0,005秒とwhileループがかかります。

max () {
    anz=$#
    max=$1
    while ((anz > 0))
    do
        b=$2
        (( b > max )) && max=$b
        shift
        anz=$#
    done
    echo $max
}

0,010秒と大きく変わりません。 2倍遅い速度ですが、値が低すぎると、誤差範囲が測定値よりも高くなる可能性があります。値の数が高すぎない限り、最速のパフォーマンスにはあまり興味がありません。しかし、gnu-parallelが改善をもたらすことができるかどうか疑問に思って、長い間並列性についてもっと学ぶ機会を待ってきましたが、実際のケースで学ぶことを好み、ケースはほとんどありません。 、これは並列化の利点を享受できます。

だから私の素朴なアプローチは再帰バージョンを試すことでした。

time parallel max ::: ${yvals[@]} 

そして、-j + 0などのいくつかの並列実験オプションを追加しました。このオプションは350個の値を生成し、各値は他の値と比較されないため、それ自体が最大値です。 :)

マンページを参照したほか、Ole TangeのYT動画4本中2本も視聴しました。GNUパラレル、少し修正して採用できるほど、私のユースケースに近い例を見つけましたが、何も見つかりませんでした。

それでSEに尋ねるつもりがありましたが、別のことで注意が気になり、6つのシェルウィンドウの記録がめちゃくちゃになって質問を書き始め、コマンドを記録したかったです。試してみましたが、今は次のように書きました。

time parallel -X max ::: ${yvals[@]} 
6933
1689
23676
31553

驚くべきことに、実際に動作します。はい、コアは4つなので、4つの結果があり、どちらが最大であるかを簡単に把握できます。これらの最大値のうち最大値をとるmax関数を書くことができます。

time max $(parallel -X max ::: ${yvals[@]}) 
31553

real    0m0,501s (Only a 5th of the time, used without parallel).

したがって、0.5秒はシェルで対話的に作業するのに許容される範囲ですが、もちろんこの経験を達成するのは幸運と適切なレコード数です。シェルは再帰性能が悪いことが知られていますか?これは私の主な問題ではありません。

主な質問は、結果に対して関数を再実行する正規並列方法があるかどうかです。これは関数型プログラミングの問題を解決する一般的な方法です。折る。地図/削減は原則として同じだと思います。

ほとんどの場合、私が扱うデータが小さいので、並列処理に入る方法と出て行く方法を学ぶ機会と苦痛がありません。

答え1

maxBashの最初の500個の値に対して、関数はO(n ^ 2)時に実行されます。これはmax、残存価値で通話を行ったためである可能性が高いです。したがって、この値をコピーする必要があります。

mmax() {
    max $(seq $1)
}

seq 10000 | env_parallel --joblog bash.log mmax
(echo '#Bash';echo '#JobRuntime in seconds';field 10,4 < bash.log |sort -n) |
  head -n 1000 | plotpipe

ここに画像の説明を入力してください。

最初の1000の値の場合、状況は少し混乱します。

ここに画像の説明を入力してください。

ksh最初の500個の値については明確ではありません。

ここに画像の説明を入力してください。

ただし、1000 個の値については O(n^2) のように見えます。

ここに画像の説明を入力してください。

ksh12:37に衝突が発生しました:

ここに画像の説明を入力してください。

plotpipeそしてfield次から:https://gitlab.com/ole.tange/tangetools)。

関連情報