4

我需要在内存中保留一些关于可能大量文件和目录（通常多达几十万）的数据。显而易见的做法是使用Dictionary<string, Something>带有路径的a作为key，但是这样做有两个问题：

  • 许多文件将有很大一部分路径是相同的，因此存储每个文件的完整路径可能会浪费内存
  • 我需要能够快速访问有关目录所有后代的数据；使用字典，唯一的方法是测试每个键并检查它是否以指定的路径开头，这是非常低效的

这个问题似乎是使用前缀树（或trie）的一个很好的候选，路径段作为“字符”。我尝试实现它，通过前缀查找性能并不算太差（大约比字典快 4 倍），但它有两个问题：

  • 内存消耗没有减少，可能是因为每个节点的孩子列表的开销
  • 构建时间比使用字典要差得多（填充集合要慢 4 倍）

我确定这一定是一个非常普遍的问题，所以也许有一些我不知道的众所周知的解决方案？

4

2 回答 2

2

只是一些通用的想法：

首先，Patricia trie可能是改善尝试的内存消耗的最著名方法——它将所有节点都有一个子节点的路径压缩到一个节点中，并沿路径连接字符。还有一个版本，您可以将数据视为二进制数字序列，其优点是您始终最多有 2 个子节点，并且更易于实现。

其次，内存消耗实际上取决于您如何存储给定节点的子节点 - 您是否维护一个 256 个节点的数组？这通常是直接查找最有效的方式，但如果您需要遍历所有子项，也会消耗最多的内存并且速度很慢。其他选项包括：

  • 存储对数组(letter, child node)- 这可能是最节省内存的方法，因为它只存储您真正关心的对象，并且它在遍历所有子对象时也具有良好的性能。但是，您必须检查所有对以进行直接查找 - 这通常离根较远，但可能是根附近的问题。

  • 在每个节点内存储某种字典，将字母映射到子节点。这在性能方面是最平衡的——它为所有操作提供了相当不错的速度，并且在一定程度上节省了内存。

此外，如果您预先构建整个集合然后只查询它，则有一种基于Tarjan 表存储子链接的方法，这可能会增加构建时间，但会节省内存和稍后的查询时间。

于 2012-11-05T11:12:17.570 回答
-1

类似前缀树的方法怎么样。即如果你想存储

/root/x
/root/a/b
/root/a/c
/root/a/d
/root/a/e
/root/a/c/e
/root/a/c/f
Here is how your tree will look like. 
                       root
                     /    \
                    x   __ a __ 
                       /  / \   \ 
                     b   c    d   e
                        / \
                       e   f

它将节省空间，因为每个目录名称将只存储一次。搜索和插入也是 O(log(n))

于 2012-11-07T09:18:34.503 回答