2

我正在通过运行具有不同配置的程序读取统计数据。假设有 6 种配置（a, b, ..., f）。配置可能不会线性变化，因此如果您将测量值视为表格，则表格中可能存在间隙。问题是关于在内存中构建这些统计数据。

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

struct data ******measurements;

现在这工作正常。您的内存开销非常小（实际上只会分配具有数据的配置），并且访问时间为O(1).

除了大多数人不喜欢******指针这一事实之外，这还有一个缺点，即添加配置意味着向数组添加维度，这可能会变得很难看，除非对数组的读/写封装在函数中。（Write 已经被封装以在必要时处理分配，所以这实际上没什么大不了的）。

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

O(log(n))为了有所作为，测试的数量可能会变得相当大。

我的问题是：在这里使用 6 深的嵌套数组是否合理？或者有没有更好的方法来做到这一点？

4

3 回答 3

2

请注意，您当前的设置不是 O(1)，而是 O(k)，其中 k 是维数。对于平衡树，无论如何它都会达到 O(log 2^k) == O(k) （我假设每个维度都有两个选择；但没关系……这里只是一个常数）。不过，您可能会或可能不会期望在实现平衡树时产生更大的开销。

您可以做的是尝试使用 typedef 和 getter/setter 函数（最好是可内联的）抽象接口，然后使用您想要的任何实现。那么你就不用那么多处理指针了，仍然使用里面的任何结构。

于 2012-06-11T17:14:58.503 回答
2

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

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

我不知道手头的交流实施。

于 2012-06-11T17:47:35.277 回答
1

真正的性能瓶颈（除了浪费内存）不是计算，而是您将遇到的间接次数和缓存未命中数。这些可以主导指数和类似东西的计算的数百到数千倍。因此，您最好的选择是减少间接次数并在计算上投入一些精力。据我所知，这最好通过散列你的 6 个索引来完成。这会将您的间接寻址减少到两个，首先查找存储在哈希表中的值（可能是指针），然后直接获取您感兴趣的数据。

于 2012-06-12T08:15:45.113 回答