替代嵌套数组(6个维度)，内存间隙保留O(1)访问

Question

我从运行不同配置的程序中读取统计数据。假设有6个配置(a、b、.、f)。配置可能不会线性变化，因此，如果您将度量看作一个表，表中可能会出现空白。问题是如何在内存中构造这些统计数据。

首先想到的是将这些配置读入一个动态分配的6深数组或数组：

struct data ******measurements;

现在这个很好用。您的内存开销很小(只有实际分配了数据的配置)，访问时间是O(1)。

除了大多数人不喜欢******指针这一事实之外，这也有一个缺点，即添加配置意味着向数组中添加维度，除非将对数组的读/写封装在函数中，否则会变得很难看。(在必要时，已经封装了Write来处理分配问题，因此这实际上并不是什么大事)。

想到的另一个想法是使用一个struct config到struct data的映射，使用一个AVL树或其他什么东西(因此，我已经有没有实现开销)。这解决了扩展配置参数的问题，但减少了对O(log(n))的访问时间。

对于O(log(n))来说，测试的数量可能会变得相当大，从而产生影响。

我的问题是:这里使用6深度嵌套数组是否合理？或者有更好的方法来做这件事？

Answer 1

真正的性能瓶颈(除了浪费内存)不是计算，而是您将遇到的间接方向和缓存丢失的数量。它们可以以百到千倍的因素支配着指数和诸如此类的计算。所以你最好的选择是减少间接方向的数目，并在计算上投资一点。据我所见，这最好通过散列你的6个指数来完成。这将使您的间接方向减少到两个，首先查找存储在哈希表中的值(可能是指针)，然后直接获取您感兴趣的数据。

Answer 2

注意，当前的设置不是O(1)，而是O(k)，其中k是维数。对于一棵平衡的树，它会转到O(log 2^k) == O(k) (我假设每个维度都有两个选择；但这不重要，…这里只是一个常数)。但是，您可能期望或不期望在实现平衡树方面产生更大的开销。

您可以做的是尝试使用类型防御和getter/setter函数(最好是不可链接的)抽象接口，然后使用任何您想要的实现。然后，您就不必过多地处理指针，并且仍然使用内部的任何结构。

Answer 3

X-树是高维数据高效存储和查找的常用选择.维基百科的文章链接只是一个存根，但它指向了一个更权威的来源。

它们基本上是R-Tree的改进版本，为最小化重叠进行了优化。

我不知道有什么c实现。