0

给定下表：

|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
}

但我怀疑这是最好的方法（关于为此类映射分配的内存和查找时间，因为该表可以包含数千行）。

有人可以告诉我一个更好的解决方案吗？

4

1 回答 1

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 每次都从零开始），所以如果您使用类型化数组，则需要显式存储一个 (typed array, offset) 对；您还需要事先计算好尺寸。这可能有点混乱，但应该是完全可行的。它可能会或可能不会更有效，这在很大程度上取决于每个 B 值有多少 C 值。

于 2013-05-16T08:13:05.317 回答