ゼロ以外の最小値を決定する最速の方法

Question

例えば4つの整数の配列を持つと、どのようにしてそれが最小でないと判断できるのですか？

Answer 1

この問題には並列解決策がありますが、おそらくそれほど努力する価値はありません。

まず、アレイにわたって動作xchg(m, n)を定義：

xchg(m, n) => ((a[m] > a[n] && a[n] != 0) || a[m] == 0) ? swap(a[m],a[n]) 

それら両方が非ゼロ値、またはスワップが含まれている場合、この操作は、2つの要素「M」をソートし、「n」は昇順に'm'要素の値がゼロであればそれらを返します。

xchg(0,2) xchg(1,3) 
xchg(0,1) xchg(2,3) 
xchg(1,2) 

ペアxchg操作を厳密順次実行にわたって40％の時間コストを削減、並列に実行することができる次のよう

次に、我々は、5つのそのような一連の操作を実行します。終了すると、配列内の0でない要素は昇順にソートされます。最小値の要素は[0]になります。その値がゼロの場合、配列に0以外の値はありません。

この溶液ソーティングネットワーク（http://en.wikipedia.org/wiki/Sorting_network）によって提供される固有の並列性を利用するが、4つの要素の順次走査もないつ以上の比較演算を使用し、そして決定的半分のような多くのストレージを必要とするが、平均して書き込み：

シーケンシャルスキャン

int v = a[0] 
for (n = 1; n < 4; n++) { 
    if ((a[n] < v && a[n] != 0) || v == 0) v = a[n] 
} 

Answer 2

入力によって異なります。配列がソートされていない場合は、配列全体をループする必要があります。配列がソートされている場合は、ゼロでないものが見つかるまでループするだけです。これははるかに短くなります。

Answer 3

要素が配列に追加されるときに最小値を保持しないか、ソート順に配列を保持しない限り、他の解決策は見当たりませんが、すべてのメンバーを繰り返して最小値を決定します。

各メンバーをテストする「高速な」方法はありません。

一般的に、私はそれが実際に遅いことが証明されない限り、何かを最適化しないことをお勧めします。あなたのプログラムの古いルールは、コードの10％でその時間の90％を費やすのが一般的です。プログラマーが99.99％という規則は、その10％ではないコードを最適化するでしょう。

はあなたのコードをプロフィール - あなたのコードをプロファイリング - あなたのコードをプロファイリング

Answer 4

まあそれをコーディングする最速の方法はstd::min({a,b,c,d})です。

さらに深刻なことに、アプリケーションが多くの価値を最小限に抑えるようなものにボトルネックを起こしている場合、より良い解決策は、その最小限の検索タスクを分割してGPUに送信する方法を見つけることですまたは多くのスレッド）、これは同時に多くの最小の計算結果を操作できます。

並列処理は、おそらくアセンブリで最小限の関数を書くのに役立ちます。

Answer 5

我々はマイクロ最適化を考えている場合は、潜在的にあるためあまりシーケンシャル依存関係のため、近代的なアウトオブオーダープロセッサ上min(min(a,b),min(c,d))代わりのmin(min(min(a,b),c),d)を計算するために速くなる可能性：元にプロセッサがmin(a,b)を計算することができます利用可能な実行ユニットが十分な場合は、min(c,d)を独立して並列に実行します。これは、プロセッサに条件付き移動命令があることを前提としているため、演算minは分岐を必要としません。