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

Question

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

首先想到的是将这些配置读取到一个动态分配的6-deep数组或数组中:

struct data ******measurements;

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

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

想到的另一个想法是使用 struct config 的映射到 struct data 使用 AVL 树或其他东西(我 already have 所以没有实现间接费用)。这解决了扩展配置参数的问题，但减少了对 O(log(n)) 的访问时间。

要使 O(log(n)) 有所不同，测试的数量可能会变得相当大。

我的问题是:在这里使用 6 层嵌套数组是否合理？或者有更好的方法吗？

Answer 1

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

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