在Python中遍历目录树的更快方法是什么？

Question

假设给定的目录树大小适中：比如像Twisted或Python这样的开源项目，那么遍历和迭代该目录内所有文件/目录的绝对路径的最快方法是什么？

我希望在Python中完成此操作。os.path.walk速度较慢。因此，我尝试了ls -lR和tree -fi。对于一个包含大约8337个文件（包括tmp、pyc、test、.svn文件）的项目：

$ time tree -fi > /dev/null 

real    0m0.170s
user    0m0.044s
sys     0m0.123s

$ time ls -lR > /dev/null 

real    0m0.292s
user    0m0.138s
sys     0m0.152s

$ time find . > /dev/null 

real    0m0.074s
user    0m0.017s
sys     0m0.056s
$

tree 似乎比 ls -lR 更快（尽管 ls -R 比 tree 更快，但它不会显示完整路径）。find 是最快的。

有没有人能想到更快和/或更好的方法？在 Windows 上，如果需要，我可以简单地提供一个32位的二进制文件 tree.exe 或 ls.exe。

更新1：添加了 find 更新2：为什么我要这样做？……我正在尝试制作一个聪明的替代 cd、pushd 等命令以及其他依赖于传递路径的包装命令（如 less、more、cat、vim、tail）。该程序偶尔会使用文件遍历来实现这一点（例如，输入“cd sr grai pat lxml”将自动转换为“cd src/pypm/grail/patches/lxml”）。如果这个 cd 替代品需要运行半秒钟，我将不会满意。请参见：http://github.com/srid/pf

- Sridhar Ratnakumar

---

这似乎是一件很奇怪的优化事项。你在做什么以至于这成为了一个性能关键操作？你对算法进行了分析和研究，确定了这是问题所在？即使像 Twisted 这样的“大型”目录树也几乎不算大。 - Mike Graham

@Mike：背景：我正在尝试制作一个智能替代cd、pushd等命令的程序，并作为其他需要传递路径的命令（如less、more、cat、vim）的包装器。该程序偶尔会使用文件遍历来完成此操作（例如：键入“cd sr grai pat lxml”将自动转换为“cd src/pypm/grail/patches/lxml”）。如果这个 cd 替代程序运行时间要达到半秒钟，我将无法满意。http://github.com/srid/pf - Sridhar Ratnakumar

然后我们回到算法; 路径修正最好是逐个部分地处理，而不是“获取整个树并与之匹配”，因为每个路径组件的搜索集很小。Kernighan和Pike在《Unix编程环境》中有一个经典的交互式路径修正工具-寻找spdist()函数。 - msw

你还确定你在正确的方向上努力吗？我敢打赌，通过重新思考需要整个树的算法，你可以获得最可扩展的改进，而不是试图加快检索树的速度。 - Mike Graham

如果你要求的话，tree可以生成完整的路径：来自man tree的解释：**-f** — 打印每个文件的完整路径前缀。它还可以生成XML、JSON和HTML。 - undefined

Answer 1

如果你在pf中采用这种方法，即使os.path.walk不花费时间，也会变得非常缓慢。在所有现有路径上执行包含3个无界限制的闭包的正则表达式匹配将直接导致失败。以下是我参考的Kernighan和Pike的代码，这是一种适合此任务的正确算法：

/* spname:  return correctly spelled filename */
/*
 * spname(oldname, newname)  char *oldname, *newname;
 *  returns -1 if no reasonable match to oldname,
 *           0 if exact match,
 *           1 if corrected.
 *  stores corrected name in newname.
 */

#include <sys/types.h>
#include <sys/dir.h>

spname(oldname, newname)
    char *oldname, *newname;
{
    char *p, guess[DIRSIZ+1], best[DIRSIZ+1];
    char *new = newname, *old = oldname;

    for (;;) {
        while (*old == '/') /* skip slashes */
            *new++ = *old++;
        *new = '\0';
        if (*old == '\0')   /* exact or corrected */
            return strcmp(oldname,newname) != 0;
        p = guess;  /* copy next component into guess */
        for ( ; *old != '/' && *old != '\0'; old++)
            if (p < guess+DIRSIZ)
                *p++ = *old;
        *p = '\0';
        if (mindist(newname, guess, best) >= 3)
            return -1;  /* hopeless */
        for (p = best; *new = *p++; ) /* add to end */
            new++;                    /* of newname */
    }
}

mindist(dir, guess, best)   /* search dir for guess */
    char *dir, *guess, *best;
{
    /* set best, return distance 0..3 */
    int d, nd, fd;
    struct {
        ino_t ino;
        char  name[DIRSIZ+1];   /* 1 more than in dir.h */
    } nbuf;

    nbuf.name[DIRSIZ] = '\0';   /* +1 for terminal '\0' */
    if (dir[0] == '\0')     /* current directory */
        dir = ".";
    d = 3;  /* minimum distance */
    if ((fd=open(dir, 0)) == -1)
        return d;
    while (read(fd,(char *) &nbuf,sizeof(struct direct)) > 0)
        if (nbuf.ino) {
            nd = spdist(nbuf.name, guess);
            if (nd <= d && nd != 3) {
                strcpy(best, nbuf.name);
                d = nd;
                if (d == 0)     /* exact match */
                    break;
            }
        }
    close(fd);
    return d;
}

/* spdist:  return distance between two names */
/*
 *  very rough spelling metric:
 *  0 if the strings are identical
 *  1 if two chars are transposed
 *  2 if one char wrong, added or deleted
 *  3 otherwise
 */

#define EQ(s,t) (strcmp(s,t) == 0)

spdist(s, t)
    char *s, *t;
{
    while (*s++ == *t)
        if (*t++ == '\0')
            return 0;       /* exact match */
    if (*--s) {
        if (*t) {
            if (s[1] && t[1] && *s == t[1] 
              && *t == s[1] && EQ(s+2, t+2))
                return 1;   /* transposition */
            if (EQ(s+1, t+1))
                return 2;   /* 1 char mismatch */
        }
        if (EQ(s+1, t))
            return 2;       /* extra character */
    }
    if (*t && EQ(s, t+1))
        return 2;           /* missing character */
    return 3;
}

注意：这段代码是在 ANSI C、ISO C 或 POSIX 诞生之前编写的，当时人们直接读取目录文件。该代码的方法比所有指针操作更有用。

- msw

---

非常感谢，我会在这个周末研究一下，并在有需要时回来提问。 - Sridhar Ratnakumar

Answer 2

在性能方面，很难比find更好，但问题是它有多快，以及为什么你需要它如此快？你声称os.path.walk很慢，确实，在我的机器上对于一个包含16k个目录的树，它比较慢，大约慢了3倍。但是，我们谈论的是Python的0.68秒和1.9秒之间的差异。

如果创造速度记录是你的目标，那么你无法击败硬编码的C，它完全受到75%的系统调用限制，你无法让操作系统运行得更快。话虽如此，Python时间的25%用于系统调用。你想要对遍历的路径做什么？

- msw

---

为什么我需要它运行得那么快？ - 我已更新问题。 - Sridhar Ratnakumar

Answer 3

你没有提到的一个解决方案是 'os.walk'。我不确定它是否比 os.path.walk 更快，但它在客观上更好。

当你拥有目录列表时，你没有说明你将要做什么，所以很难给出更具体的建议。

- moshez

---

我计时了一下，在我的系统上 os.walk 比较慢，大约慢了15%，可能是因为它会返回所有文件而不仅仅是目录。但是，正如我在回答中提到的那样，2.3秒与0.7秒相比并不算太长。 - msw

我将如何处理筛选出的路径列表？我会做一个正则表达式匹配。请参考我对迈克的回复以及http://github.com/srid/pf/blob/master/src/pf/__init__.py。 - Sridhar Ratnakumar

Answer 4

虽然我怀疑你有多个读头，但是这里是如何遍历几百万个文件的方法（我们已经在几分钟内处理了超过1000万个文件）。

https://github.com/hpc/purger/blob/master/src/treewalk/treewalk.c

- Jon Bringhurst

---

链接已损坏。您是指这个链接吗：https://github.com/hpc/dcp/blob/master/src/treewalk.c？ - Jean-Francois T.