2つの巨大な配列の間の変化の発見

Question

簡潔にするために、私は非常に大きな2D空間を単純なビット配列にマップしました（実際には約200kのメンバーです）。

ここで、1の「円」を描く小さなアルゴリズムを実行して、中心点と半径を指定したとします。

ここで左側の円が描かれ、そして次の計算上、それは今、私はこれらのマップの多くの層を持っている、とした後、私は計算1.

0000000  0001000 
0001000  0011100 
0011100 -> 0011100 
0011100  0001000 
0001000  0000000 
0000000  0000000 

上に移動し、センターの例ですそれらを「平坦化」する必要があります（Photoshopのブレンドレイヤーオプションのようなものです）。そして、現在、私はアレイ全体で毎回反復し、配列全体を結合します。

擬コード

for(int x = 0; x < width; x++) 
    for(int y = 0; y < height; y++) 
     int index = x + y * width 
     result[index] = layer1[index] * layer2[index] 

これは非常に非効率的であり、私は自分のパフォーマンスを改善する必要があります。

UPDATE：私たちは

スパース行列は、我々は必要なものを正確にだったやってしまった、と我々は最高の私たちの使用を適したキーの辞典（DOK）は（動的それぞれを構築する使用して終了何それらを一緒に「ブレンド」する）。これ部材マーキング、

1. float配列は、我々は（値）
2. ビット配列（同じサイズ）を有する可能性があるメンバーの最大数として寸法：

   我々は思い付いた溶液を3つの配列を使用することでしたvalue配列内のメンバのポインタへのポインタの一種として使用されるインクリメントint + value配列内で使用されるインデックスを保存する+

3. int配列（同じサイズ）インデックス配列

私たちのニーズはメモリ使用量とCPUに大きく依存していたので、ブレンドごとに新しい配列を生成しないために、各疎行列を二重バッファ形式でラップしました。

最終的には、このソリューションではCPU使用率が従来よりも15倍向上しました（メモリ使用量を約98％削減しました）。私が理解から

Answer 1

、およびPhotoshopのレイヤーのアナロジーを使用して：

あなたが「密」の2D配列として保存されている基礎となる「画像」を、持っている、そしてもちろん、それはあなたのデータなので、すべての「画素」であります重要。ここまでは順調ですね。

余分な層は小さな変化を表す：2次元配列として表される場合、そのエントリのほぼすべてはゼロであろう。その場合

は、あなたが疎行列表現にを見てみたい：代わりに、完全な2次元配列を格納するので、あなただけの非ゼロのセルの座標を記録タプル[(i1,j1), (i1, j2), ..., ]のリストを格納します。

そうすれば、これらの行列上で動作する任意のアルゴリズムが代わりには行列が持っているどのように多くの総エントリに基づいてありますどのように多くの非ゼロの順序で実行されます。