arrays - 有效二维数组的delta数据结构

Question

我正在制作原型(prototype)，目前不确定如何设计一个加载齿轮。

它的目的很简单——保存 2D 数组的增量并稍后将其作为 getDelta(i,j) 或通过任何其他接口(interface)返回。现在不需要最好的压缩，只是不需要 O^2 的数组大小内存，但性能是。

详细信息:

1. 形成delta与求整个数组的delta在某次序运算中的比例为1:1。
2. 目前，存储了一个 float 据，但我不想将其固定为实现细节。
3. Delta 的大小固定；它与数组的行数(或列数；此外，数组始终为正方形)相同。
4. 这可以修改消费者和编写者代码，使其以相同(或任何其他相互已知的)顺序放置和读取，但我不知道，这是使用它来优化它的最佳方式。

附注这是一个 Java 任务，但作为一个一般的数据结构问题:C、Perl、Mathematica、Fortran、伪代码或想法是受欢迎的，其他基于语言的示例对我来说可能不太清楚。

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
}