最大値を見つける2次元配列N * Nの比較数が少ない

Question

Cで2次元配列N * Nの最大値を比較したい場合があります。私はO（N^2）アルゴリズムで単純にそれを行うことができますが、それは遅すぎると思います。

私は別の方法について考えました。私は単純に1回ループし、行と列を同時に検索し、複雑さを減らそうとします。 （私はO（2（n-1））だと思います）あなたは私が何をしようとしているのかをこの絵で見ることができます。私は列と行の内容をチェックするために、同じループを使用

。

もっと知りたいことは何ですか？同様に、2次元配列をO（N log N）の複雑さでソートしますか？値がソートされていないと仮定します。

Answer 1

M x M要素の2次元配列が決してソートされていない場合、O（M^2）よりもうまくいくとは限りません。

行列にはM^2要素があるので、ソートするとO（M^2 log M^2）の複雑さがあります。大部分の適切な並べ替えはO（N log N）であり、N = M^2。

Answer 2

[コア、中]のチャンクに分割します。最大化する各チャンクの並列に結果から骨を選んでください。

Answer 3

確かに、dbushは複雑さの点で正しい答えを持っています。

実際の実行時間（複雑さだけでなく）を「高速」にしたい場合は、キャッシュを考慮する必要があります。並行して行と列を下げることは、データの局所性が非常に悪く、データの行数が比較的多い場合は、列を反復処理するときにキャッシュミスが発生します。最大値を見つけるには、少なくとも1回はすべての要素をタッチしなければなりません。「行の大」順序でそれらをタッチするのが最も速くなります。

Answer 4

あなたはおそらく...

を1次元配列に配列をキャストし、平坦化されたポインタを反復処理することができ、私は説明します：

あなたはおそらく知っているように、メモリ内の2次元配列が格納されています平らな状態で。この例では

| c[0][0] | | c[0][1] | | c[1][0] | | c[1][1] | | c[2][0] | ... 
| Byte 1 | | Byte 2 | | Byte 3 | | Byte 4 | | Byte 5 | ... 

、c[1][1] == ((char*)c)[3]：配列char c[4][2]はこのようになります。このため

dbushが指摘するように、すべてのメンバーが同じタイプであるとき、それは安全に1次元配列に2次元配列をキャストすることが可能です、すなわち

int my_array[20][20]; 

for (int i = 0; i < 400 ; i++) { 
    ((int *)(my_array))[i] = i; 
} 

// my_array[19][0] == 180; 

（アップ彼の答えを投票）、もしあなたの行列はM x Mの要素です。そして、M^2はあなたが得ようとしている最良の配列です。このように配列を平坦化すれば、操作の前にメモリをコピーする必要がなくなります。良いかもしれない1次元配列に配列をキャストする理由

EDIT

誰かが尋ねました。

考え方は、ネストされた内部ループを回避し、オプティマイザの作業を容易にすることです。コンパイラは、ループが単一のディメンションループであり、配列のサイズが固定されている場合、ループを展開する可能性が高くなります。