8

たとえば4つの整数の配列を持っている場合、それがゼロ以外の最小値であることをどのように判断できますか?最速の方法で?

4

5 に答える 5

9

要素が配列に追加されるときに最小値を保持するか、配列をソートされた順序で保持しない限り、すべてのメンバーを反復して最小値を決定する以外に解決策はありません。

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

一般に、実際に遅いと証明されない限り、何かを最適化しないことをお勧めします。プログラムの古いルールは、コードの 10% で 90% の時間を費やすという一般的なルールが当てはまります。プログラマーが 99.99% の確率でコードを最適化する可能性が 10% にないというルールも同様です。

コードのプロファイリング - コードのプロファイリング - コードのプロファイリング

于 2012-01-15T03:38:10.080 に答える
7

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

まずxchg(m, n)、配列aに対する操作を定義します。

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

この操作は、2 つの要素 'm' と 'n' が両方ともゼロ以外の値を含む場合は昇順で並べ替え、'm' 要素の値がゼロの場合はそれらを入れ替えます。

次に、次のような 5 つの操作のセットを実行します。

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

ペアになっxchgた操作は並行して実行できるため、厳密に順次実行する場合に比べて時間コストが 40% 削減されます。完了すると、配列内のゼロ以外の要素が昇順で並べ替えられます。最小値の要素は a[0] になります。その値がゼロの場合、配列にはゼロ以外の値はありません。

このソリューションは、ソート ネットワーク ( http://en.wikipedia.org/wiki/Sorting_network ) によって提供される固有の並列性を利用しますが、4 つの要素の順次スキャンでも 3 つ以下の比較操作しか使用せず、決定的に必要な比較操作は半分です。平均ストレージ書き込み:

順次スキャン

int v = a[0]
for (n = 1; n < 4; n++) {
   if ((a[n] < v && a[n] != 0 ) || v == 0) v = a[n]
}
于 2012-11-12T18:17:23.533 に答える
3

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

于 2012-01-15T06:08:14.900 に答える
3

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

于 2012-01-15T03:37:03.310 に答える
0

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

より深刻な注意: アプリケーションが多くの値の最小値を取得するなどのボトルネックを抱えている場合、より良い解決策は、その最小値を見つけるタスクを部分に分割し、GPU (または多くのスレッド) に送信する方法を見つけることです。 、同時に多くの最小発見計算を実行できます。

並列処理は、アセンブリで最小限の関数を書こうとする以上の助けになるでしょう。

于 2012-01-15T03:39:11.817 に答える