在Python中遍歷目錄樹的方法合理得快？

Question

假設給定的目錄樹具有合理的大小：說一個像Twisted或Python這樣的開源項目，遍歷和遍歷該目錄內所有文件/目錄的絕對路徑的最快方法是什麼？

我想在Python中做到這一點。 os.path.walk很慢。所以我嘗試了ls -lR和樹-fi。對於具有約8337文件的項目（包括TMP，PYC，測試的.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等。和包裝命令的其他命令依賴於傳遞路徑（更少，更多，貓，vim，尾巴）。該程序偶爾會使用文件遍歷來做到這一點（例如：鍵入「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很慢，實際上，在我的機器上，它比16k目錄的樹慢了3倍。但是，我們再次談論Python的0.68秒和1.9秒之間的差異。

如果設置的速度記錄是你的目標，你不能打硬編碼ç這是完全75％的系統調用的約束，你不能讓操作系統走得更快。也就是說，25％的Python時間花費在系統調用中。你想用遍歷路徑做什麼？

Answer 3

你在PF做法將是無可救藥緩慢，即使os.path.walk沒有采取任何時候都。在所有現存路徑中進行包含3個無界閉包的正則表達式匹配會在那裏殺死你。下面是從Kernighan and 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任何事情之前是書面的方式是即使一個想象讀取目錄文件raw。代碼的方法比所有的指針索引要有用得多。

Answer 4

儘管我懷疑你有多個讀頭，但你可以遍歷幾百萬個文件（我們已經在幾分鐘內完成了10M +）。

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