Достаточно быстрый способ перемещения дерева каталогов в Python?

Question

Предполагая, что данное дерево каталогов имеет разумный размер: скажем, проект с открытым исходным кодом, такой как Twisted или Python, что является самым быстрым способом прохождения и перебора по абсолютному пути всех файлов/каталогов внутри этого каталога?

Я хочу сделать это изнутри Python. os.path.walk медленный. Поэтому я попробовал ls -lR и tree -fi. Для проекта с около 8337 файлов (включая ТМР, рус, тест, .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, если это необходимо.

Update 1: Добавлено find

Update 2: Почему я хочу, чтобы это сделать? ... Я пытаюсь сделать умную замену для команд cd, pushd и т. Д. И оболочки для других команд, полагающихся на проходящие пути (меньше, больше, 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 медленный, действительно, на моей машине в три раза медленнее на дереве из 16k-каталогов. Но опять же, мы говорим о разнице между 0,68 секунды и 1,9 секунды для Python.

Если вы устанавливаете запись скорости, это ваша цель, вы не можете бить жесткий код C, который полностью связан с системным вызовом на 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