高效的算法和存储格式的表3xN

Question

给出以下表格:

|A|B|C|
|0|0|1|
|1|0|3|
|1|1|1|
|1|2|1|
|1|3|1|
|1|4|2|
|2|5|1|

我需要想出最有效的算法和存储格式，允许我在给定A和B的情况下确定C:

                +-----------+
                |   BLACK   |
A = 0, B = 0 -> |    BOX    | -> 1
                +-----------+

                +-----------+
                |   BLACK   |
A = 1, B = 4 -> |    BOX    | -> 2
                +-----------+

算法应该在内存和效率之间提供良好的权衡。我的第一次尝试是将a和B进行散列，并将其用作映射的键:

{
    "0.0": 1,
    "1.0": 3,
    "1.1": 1,
    "1.2": 1,
    "1.3": 1,
    "1.4": 2,
    "2.5": 1
}

但是我怀疑这是不是最好的方法(考虑到为这样的映射分配的内存和查找时间，因为这个表可以包含数千行)。

谁能给我一个更好的解决方案?

Answer 1

哈希表听起来是一种非常合理的方法，即使对于数千行也是如此。你在用什么语言?您的表有多大?您第一次尝试的性能如何?

你的数据中有你可以使用的模式吗?A, B和C的可能范围是什么?

需要更多的数据。

[这是一个评论，不是一个答案，但显然我没有足够的声誉发表评论]

更新以包含嵌套数组思想的示例:

var table = [];
function add_entry (A, B, C) {
  if (!table[A])
    table[A] = []; // create if it doesn't already exist
  table[A][B] = C;
}
function retrieve_entry (A,B) {
  return table[A][B];
}

生成如下结构:

table = [
  [ 1 ],
  [ 3, 1, 1, 1, 2 ],
  [ undefined, undefined, undefined, undefined, undefined, 1 ]
];

标准javascript数组，只是伪装的对象，处理稀疏性很好。因为我错过了即使A改变B也均匀增加的部分(我认为B每次都从0开始)，如果你使用类型化数组，你需要显式存储一个(类型化数组，偏移)对;你还需要事先算出尺寸。这可能有点乱，但应该是完全可行的。它可能会更有效，也可能不会，这主要取决于每个B值对应多少个C值。