在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

Answer 1

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

你没有说明在获取到目录列表后打算怎么处理，所以很难给出更具体的建议。

Answer 2

想要在性能上比 find 更好是很难的，但问题是你到底想要多快，为什么需要这么快？你说 os.path.walk 很慢，确实，在我这台机器上处理一个有 16,000 个目录的树时，它大约慢了 3 倍。不过，我们说的其实是 0.68 秒和 1.9 秒之间的差别，这对于 Python 来说并不算太大。

如果你的目标是创造一个速度记录，那你就无法超越用 C 语言写的代码，因为它的 75% 时间都在进行系统调用，而你也无法让操作系统变得更快。话虽如此，Python 的运行时间中有 25% 是花在系统调用上的。你到底想用遍历到的路径做些什么呢？

Answer 3

你在pf中的做法会非常慢，即使os.path.walk根本不耗时间。因为在所有现存的路径中进行包含三个不限制的匹配的正则表达式会让你崩溃。这里有一段我提到的来自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这些概念出现之前写的，当时人们是直接读取目录文件的。这段代码的方法比那些复杂的指针操作要实用得多。