未定义索引的默认值最快的数据结构？

Question

我想创建一个2d数组，其中，当我访问索引时，将返回值。但是，如果访问未定义的索引，它将调用回调并用该值填充索引，然后返回该值。

该数组也将具有负指数，但我可以通过使用4个数组（每个象限围绕0,0）来克服这个问题。

Answer 1

您可以创建依赖于元组和字典中的Matrix类，具有下列行为：

from collections import namedtuple 
2DMatrixEntry = namedtuple("2DMatrixEntry", "x", "y", "value") 
matrix = new dict() 
defaultValue = 0 

# add entry at 0;1 
matrix[2DMatrixEntry(0,1)] = 10.0 

# get value at 0;1 
key = 2DMatrixEntry(0,1) 
value = {defaultValue,matrix[key]}[key in matrix] 

干杯

Answer 2

这个问题可能是计算器过于宽泛。 - 没有一种通用的“一刀切”解决方案，结果取决于所使用的语言（和标准库）。

这个问题有几个问题。首先让我们考虑一个二维数组，我们说这已经是该语言的一部分，并且这种数组在访问时动态增长。如果情况并非如此，那么这个问题就会变得与语言有关。

现在经常在分配内存时，语言自动初始化点（语言取决于这是怎么回事，最好的方法是什么，看看RAII）。虽然我可以预见，具体细胞的实际计算可能是昂贵的（与分配相比）。在这种情况下，一个有趣的事情可能就是所谓的“两阶段建设”。该数组必须填充元组/对象。对象的默认构造将bit/boolean设置为false - 表示该值未准备就绪。然后在acces上（即一个get()方法或一个operator() - 语言相关），如果这个位是假的，它会构造，否则它只是读取。

---

另一种方法是使用字典/键值映射。关键是坐标和价值。这具有的优点是访问构造的问题继承了数据结构（尽管语言依赖）。然而，使用映射的缺点是值的查找速度从O（1）变为O（logn）。 （虽然实际时间根据语言而有很大差异）。

---

最后，我希望你明白，如何做到这一点取决于更具体的要求，你所使用的语言和其他库。最后，每种语言只有一个数据结构：未分配值的长序列。任何比这更先进的东西都取决于语言。