c# – 用于将数据与文件系统路径相关联的高效数据结构?
我需要在内存中保留一些关于可能大量文件和目录的数据(通常高达几十万).显而易见的方法是使用Dictionary< string,Something>以路径为关键,但这有两个问题:
>许多文件的路径都有很大的共同点,因此存储每个文件的完整路径可能会浪费内存 这个问题似乎是使用前缀树(或trie)的理想选择,路径段为“字符”.我试图实现它,并且通过前缀查找性能并不是太糟糕(比字典快4倍),但它有两个问题: >内存消耗不会减少,可能是因为每个节点的子列表开销 我敢肯定它一定是一个非常普遍的问题,所以也许有一些我不知道的众所周知的解决方案? 解决方法
只是一些通用的想法:
首先,Patricia trie可能是提高尝试内存消耗的最着名的方法 – 它压缩所有节点将一个子节点放入一个节点的路径,并沿路径连接字符.还有一个版本,您可以将数据视为二进制数字序列,其优点是您总是最多有2个子节点,并且它也更容易实现. 其次,内存消耗实际上取决于您如何存储给定节点的子节点 – 您是否维护256个节点的数组?这通常是直接查找的最有效方式,但是如果需要遍历所有子节点,它也会消耗最多的内存并且速度很慢.其他选择是: >存储一对数组(字母,子节点) – 这可能是内存效率最高的,因为它只存储您实际关注的对象,并且它还具有迭代所有子节点的良好性能.但是,您必须检查所有对以进行直接查找 – 这通常距离根更远,但可能是根目录附近的问题. 此外,如果你预先构建整个集合然后只是查询它,有一种方法可以存储基于Tarjan tables的子链接,这可能会增加构造时间,但以后会节省内存和查询时间. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |