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

Предполагая, что данное дерево каталогов имеет разумный размер: скажем, проект с открытым исходным кодом, такой как 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"). Я не буду удовлетворен, если эта замена компакт-диска займет, скажем, полсекунды для запуска. Смотрите http://github.com/srid/pf

Источник

4 ответа

Ваш подход в 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 можно было представить что-либо, когда один читал файлы директории raw. Подход к коду гораздо полезнее, чем весь выбор указателя.

Источник

Было бы трудно стать намного лучше, чем find в производительности, но вопрос в том, насколько быстрее и зачем вам нужно, чтобы это было так быстро? Вы утверждаете, что os.path.walk медленный, действительно, он примерно в 3 раза медленнее на моей машине по дереву каталогов по 16 КБ. Но опять же, мы говорим о разнице между 0,68 секундами и 1,9 секундами для Python.

Если ваша цель - установить рекорд скорости, вы не можете побить жестко закодированный C, который полностью на 75% связан с системным вызовом, и вы не можете заставить ОС работать быстрее. Тем не менее, 25% времени Python тратится на системные вызовы. Что вы хотите сделать с пройденными путями?

Источник

Хотя я сомневаюсь, что у вас есть несколько головок для чтения, вот как вы можете пройти несколько миллионов файлов (мы сделали 10M+ за несколько минут).

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

Источник

Одним из решений, которое вы не упомянули, является "os.walk". Я не уверен, что это будет быстрее, чем os.path.walk, но объективно лучше.

Вы не сказали, что вы будете делать со списком каталогов, когда он у вас есть, поэтому трудно дать более конкретные предложения.

Источник
Другие вопросы по тегам