我希望尽可能高效地将所有目录存储在一个巨大的驱动器中,并且能够根据完整路径检索目录。 每个目录都有其名称的字段(不是完整路径)以及指向其父目录的指针和子目录列表。 你认为哪条路要走?
正如我所看到的,有几种方法:
a)将完整路径存储到字典中的每个目录并进行简单的查找。 优点:快速,缺点:每个完整路径字符串都占用了不必要的和冗余的内存量
b)将实际目录名称存储在带有该名称的所有目录列表的字典中,然后检查匹配项是否正确:优点:相当快,缺点:必须存储每个目录的列表或使用装箱来存储字典中的列表或目录。
c)跳过字典,从根部遍历树并通过拆分路径找到匹配。 也许使用PLINQ来加快速度。 优点:字典中没有内存开销,缺点:可能比查找慢。
d)我还没有想过的其他方式...
I want to store all directories on a huge drive as efficiently in memory as possible and also be able to retrieve a directory given it's full path. Each directory has fields for it's name (not it's full path) and a pointer to it's parent and a list of subdirectories. Which way do you think the way to go is?
As I see it there's a couple of ways:
a) Store the full paths to each directory in a dictionary and do a simple lookup. Pros: fast, Cons: each full path string takes up uneccessary and redundant amount of memory
b) Store just the actual directory name in a dictionary with a list of all directories with that name, then check the matches if it's correct: Pros: pretty fast, Cons: has to either store a list for each directory or use boxing to store either a list or directory in the dictionary.
c) Skip the dictionary, traverse the tree from the root and find a match by splitting the path. Perhaps use PLINQ to speed things up. Pros: No memory overhead with the dictionary, cons: potentially slower than lookup.
d) some other way i haven't thought of...
最满意答案
如果可以将子目录存储为字典而不是列表(并且对于需要所有子目录的情况,可以使用Values属性轻松完成),那么您可以逐步遍历每一步为O(1)的路径,因此从完整路径查找目录的复杂性是O(n),其中n是路径中的步数,与系统中的目录数量无关。
If you could store the subdirectories as a dictionary rather than as a list (and for cases where you want all the subdirectories, that's easily done using the Values property) then you can step through the path with each step being O(1) and hence the complexity of finding the directory from the full path being O(n) where n is the number of steps in the path, not related to the number of directories in the system.
更多推荐
发布评论