そしてAcceler8並列プログラミングコンテストについて説明します。 はい、これは学ぶだけでなく、「小さな」賞品の1つであるHPのノートパソコン2台とAsusのネットブック10台で 働く機会がある競争です。
手を試してみませんか？
一見したところ、今回の競争は非常に単純です。プログラミングの問題を1つだけ解決する必要があります。
一見したところ、ソリューションは並列であり、おそらくスケーラブルでなければなりません。
それで、私たちは何について話しているのでしょうか？
タスクについて簡単に
値の2次元行列が与えられた場合、すべての部分行列の中で要素の最大和を含む長方形の部分行列を見つける必要があります。
タスクの詳細については、コンテストページをご覧ください 。
ソリューション概要
タスクが順次額検索によって解決されることは明らかですが、解決策は遅すぎます。
int maxSum = A[0][0]; int maxI0 = 0, maxJ0 = 0, maxI1 = 1, maxJ1 = 1; for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) for (int width = 1; width <= M - i; width++) for (int height = 1; height <= N - j; height++) { int currentSum = sum_subarray(A, i, j, i + width, j + height); if (currentSum > maxSum) { maxSum = currentSum; maxI0 = i; maxJ0 = j; maxI1 = i + width - 1; maxJ1 = j + height - 1; } } cout << "Max subarray: [" << maxI0 << "][" << maxJ0 << "] .. [" << maxI1 << "][" << maxJ1 << "]"; cout << endl << "Max value = " << maxSum << endl; cout << "Area = " << (maxI1 - maxI0 + 1) * (maxJ1 - maxJ0 + 1) << endl;
明らかに、このアプローチは「まったく壮大ではありません」。
賢明な決定方法
このタスクには多くのアプローチがあります。
- 最初に、 Daily One Algorithmで説明されている（マトリックスプロパティに基づく）興味深いキャッシングを使用できます。
最初に、ゼロで満たされた中間行列Bを作成します。各要素B [i] [j]は、左上隅（A [0] [0]）からA [i] [j]までの部分行列要素の合計を格納します。
これで、サブマトリックスの要素の合計は次のようになります。
sum = B[i2][j2]- B[i1-1][j2] - B[i2][j1-1] + B[i1-1][j1-1]
- 次に、元は1次元配列用に作成されたKadaneアルゴリズムを使用してみてください。または、 stackoverflow.comのユーザーの1人が指定した修正アルゴリズムを移植して並列化できます。
- 第三に、少し考えて、美しく、並行して、迅速なソリューションを書くことができます;）
すべてのカードを公開するわけではありません。 今ではすべてが平等な立場にあります-1か月（決定は11月15日まで）、Googleと教科書への無料アクセス。
簡単そうですね。
そして最もおいしい-おやつに。
スケーラビリティをどのように評価しますか？
この問題には多くのアプローチと多くの洪水があります。 最も単純なソリューションを採用することにしましたが、現実に最も近いソリューションも採用しました。
コードは2つの異なるプラットフォームでテストされます。 1つは、有名なハードウェア特性、有名なプロセッサブランド、有名なサイズの2次キャッシュを備えたManycore Testing Lab 40 コアマシンです（「 MTL構成 」を参照）。 2つ目は小さなシステムです。これについてはほとんど何もわかっていません（2〜4コア、メモリのいくつかのギグ-それがすべての情報です）。
このような状況でソリューションを最適化することは困難ですか？ はい
一方、「小さなマシン」やMTLの媒体では、誰よりも速く作業できます-これで十分です。
それとも、誰かが両方のマシンでより良い結果を達成するでしょうか？ 時間を表示します。
だから、興味のある人のために、小さなリンク： コンテストへの登録 。 コメントに質問を書いたり、 コンテストフォーラムに行ってください 。
そして、それは壮大です！ ;）