algorithm - 在 FTP 中实现 mktree 的最快方法

Question

使用 FTP 协议递归创建目录（类似于 UNIX mkdir -p）的最快算法通常是什么？

我考虑过一种方法：

1. MKDIR 节点
2. 如果错误和剩余节点与下一个节点一起转到 1
3. 结尾

但是，如果目录的一部分很可能存在，这可能会导致性能不佳。例如，通过某些摊销，“/a/b/c/d/e/f/g”路径的“/a/b/c/d”部分存在 %99 的时间。

Answer 1

考虑到发送命令和接收响应需要花费大部分时间，创建目录路径的最快方法是使用尽可能少的命令。

因为除了尝试创建或 cd 到一个目录来检查它的存在之外别无他法，只需使用 mkdir a; mkdir a/b; ...， mkdir a/b/c/d/e/f 通常是最快的方法（不要 cd 进入子目录来创建下一个，因为这会延长过程）。

如果您以这种方式创建多个目录，您当然可以跟踪您已经创建了哪些顶级目录。此外，根据路径的长度和上层目录已经存在的可能性，您可以尝试从例如 mkdir a/b/c （对于 a/b/c/d/e/f）开始，然后回溯，如果它没有成功。但是，如果目录更可能不存在，从长远来看，这实际上会变慢。

Answer 2

如果现有目录层次结构在任何给定深度处结束的可能性相同，则对开始位置的二进制搜索将是最快的方法。但是正如dseifert 指出的那样，如果大多数时候目录已经存在到 k 级，那么在 k 级而不是 n/2 级开始二进制搜索会更快。

顺便说一句，您必须创建很多非常深的目录才能使这种优化值得您花时间。你确定你没有过早优化吗？