gpt4 book ai didi

language-agnostic - 如何有效地搜索文件系统(算法方面)?

转载 作者:行者123 更新时间:2023-12-04 07:44:25 25 4
gpt4 key购买 nike

深度优先搜索是一种可怕的文件系统搜索方式——在实践中,可能位于非常靠近根目录下的文件可能需要很长时间才能使用 DFS 找到,因为 DFS 会分散注意力另一个深层的、不相关的目录层次结构。
然而,它的资源需求非常好——它需要保持打开状态的文件句柄数量只与层次结构的深度成正比,而不是它的大小。

广度优先搜索是显而易见的解决方案——它非常快。
(我上次测量时,它与我系统上的 DFS 花费的时间大致相同,大约 8 秒。)

然而 BFS 有其自身的问题 -- BFS 需要保持打开非常大量的目录句柄,可能有数百万。 (在我的系统上,它大约有 100,000 个句柄,这高得离谱。它很可能会更多。)

这会导致几个问题:

  • 保持打开如此多的句柄不仅会消耗内存(无论如何相对便宜),还会消耗许多其他类型的资源,例如虚拟文件系统(网络、挂载目录等)中文件的句柄,以及可能是其他有限的内核级资源。

  • 它还会给用户带来其他实际问题:例如,一个一直处于打开状态的虚拟目录无法再关闭!这意味着,例如,用户可能无法关闭程序、弹出某些设备或关闭某种外部连接。这种方法可能会出现各种各样的问题。

这似乎是迭代深化,然后才是解决方案。

问题是什么?实践起来很慢。
我的麻烦是大型目录(例如 Windows 中的 WinSxS)被重新枚举每个深度级别,即使它们不需要这样做。上次我尝试这样做时,迭代加深在我的系统上比 DFS 慢约 15 倍。所以 8 秒的搜索大约需要 120 秒左右,这是 Not Acceptable 。

当然,试图跟踪您不应该打开的目录(也许是因为您注意到您不再需要打开它们)违背了使用迭代深化的初衷,因为它揭示了我们的所有资源问题有 BFS。

所以,问题很简单:

如果您正在搜索一个您不熟悉的文件系统,您应该如何着手在速度和可用性之间取得可接受的平衡?有比 BFS 更好的选择吗?

最佳答案

如果您真的对文件的位置没有任何指导,那么我认为您无能为力。您应该尝试使用一些技巧来尽量减少寻道和寻道时间,但是文件系统会变得支离 splinter 并且您无法了解这一点,因此很难在那里做很多事情。在许多文件系统上,在搜索子目录之前搜索目录中的文件应该更快,尤其是当您正在寻找可能已内联的小文件时。使用完整的 BFS 不耗尽内核资源也是一件好事。

即使您只是知道文件可能在哪里,这也会有很大帮助。例如,如果它是用户放在某处然后忘记位置的文件,则从主目录、临时目录和驱动器的根目录开始,并执行 DFS 直到合理的递归限制(例如 6- 8 会在我的 Windows 或 OS X 机器上找到任何手动放置的文件或自动下载的文件),理论上用户通常不会意外地得到很深的树,但自动生成的层次结构可能会很深。如果该搜索失败,请返回并搜索您之前跳过的深层目录。如果文件就是丢失了,无论如何搜索都会很慢,所以为了安全起见,回退到 DFS 并且不会在用户继续使用机器时造成太多问题。

最重要的是,如果系统有任何类型的搜索索引,请先检查它,即使这意味着要编写更多代码来支持它。

关于language-agnostic - 如何有效地搜索文件系统(算法方面)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12831668/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com