有効な2D配列のデルタデータ構造

Question

私はプロトタイプを作成していますが、現在、ロードされているギアをどのように設計するかはわかりません。

目的は簡単です.2D配列のデルタを保存し、後でgetDelta（i、j）または他のインターフェイス経由で戻します。最適な圧縮は現在必要ではなく、配列のサイズメモリのO^2ではなく、パフォーマンスがあります。

詳細：デルタを形成

1. いくつかのための稼働率で、アレイ全体のデルタを尋ねると1：1です。
2. 現在、フロートデータが保存されていますが、実装の詳細としてこれを固定したくありません。
3. デルタは固定サイズになっています。それは配列の行の量（または列;配列は常に正方形である）と同じです。
4. これは、コンシューマーとライターのコードを同じ（または他の相互に既知の）順序で入れて読むことを再設計することは可能ですが、これを最適化するための最良の方法はわかりません。

p.s.これはJavaのタスクですが、C、Perl、Mathematica、Fortran、疑似コードやアイデアは歓迎しますが、他の言語ベースの例はあまり明確ではないかもしれません。効率的に「デルタ」（即ち、差）場合には2つの2Dアレイの間の値のほとんどが同じであると予想されるを格納する

Answer 1

、あなただけの要素の値を格納するhash map又はmapを使用することができそれは異なっている。

C++での迅速な実装：

#include <bits/stdc++.h> 
using namespace std; 

typedef float value_type; 
vector<vector<value_type>> original_array; 
map<pair<int, int>, value_type> different_elements; 

void calculate_delta(const vector<vector<value_type>> &another_array) { 
    int i, j; 
    for (i = 0; i < original_array.size(); ++i) { 
     for (j = 0; j < original_array[i].size(); ++j) { 
      if (another_array[i][j] != original_array[i][j]) { 
       // store the different element 
       different_elements.insert(make_pair(make_pair(i, j), 
                another_array[i][j]); 
      } 
     } 
    } 
} 

value_type get_delta(int i, int j) { 
    auto it = different_elements.find(make_pair(i, j)); 
    if (it == different_elements.end()) { 
     return original_array[i][j]; 
    } 
    return it->second; // return the stored value 
}