Most efficient way to find subdirectories paths

user_10358011 0
Viewed 117

Let's say I've got the following directory structure

PROJECT
|
+ BUILD
|    |
|    + STH1
|    |    |
|    |    + 6.11.2
|    |    |
|    |    + 6.11.3
|    |    |
|    |    + .....
|    + STH2
|    |    |
|    |    + 6.11.2
|    |    |
|    |    + 6.11.3
|    |    |
|    |    + .....
+ COMMON
|    |
|    + 6.11.2
|    |
|    + ....

What would be the most efficient way to find all the 6.11.2 directories in the PROJECT directory in python?

I tried using

glob.glob('PROJECT/**/6.11.2', recursive=True)

It works, but it's not the best solution for me, because it will also look for directories like

PROJECT/BUILD/STH1/6.11.2/6.11.2

So it takes a lot of time, I only need to find the 1st occurrence of the directory 6.11.2, so searching deeper into it is a waste of time (also situation like sth/6.11.2/6.11.2 will not happen in my structure)

Is there a better way to do the search in python?

Note that 6.11.2 is also quite complex directory with lots of files and subdirectories, that's why it takes a lot of time to do the search recursively.

os.path glob directory algorithm python
2 Answers

If I understand it correctly, you don't want to find directories with the same basename, is that so? If yes, then this should do the trick:

import os
from collections import deque
from typing import List, Set


def scandir_only_dirs(path: str) -> List[str]:
    return [f.path for f in os.scandir(path) if f.is_dir()]


def scandir_no_same_basename(path: str) -> Set[str]:
    result = set()
    queue = deque(scandir_only_dirs(path))

    if not queue:
        return result

    visited_basenames = set()

    while queue:
        currdir = queue.popleft()
        basename = os.path.basename(currdir)
        if basename not in visited_basenames:
            result.add(currdir)
            queue.extendleft(scandir_only_dirs(currdir))
            visited_basenames.add(basename)

    return result

With your example directory tree, this function returns:

{'.\\build',
 '.\\build\\sth1',
 '.\\build\\sth2',
 '.\\build\\sth2\\6.11.2',
 '.\\build\\sth2\\6.11.3',
 '.\\common'}

This algorithm can of course be modified depending on whether you want some other part other than the basename to be taken into consideration, but the general idea is to perform a traversal and establish what is your criteria for "visited".

Edit

Adding the answer below because I had misunderstood the question:

def find_paths_to_dir(dir_basename: str, from_path: str=".") -> Set[str]:
    result = set()
    queue = deque(scandir_only_dirs(from_path))

    if not queue:
        return result

    while queue:
        currdir = queue.popleft()
        basename = os.path.basename(currdir)
        if basename == dir_basename:
            result.add(currdir)
        else:
            queue.extendleft(scandir_only_dirs(currdir))

    return result
user_8197200

The slowness is likely due to matching against files more than nested 6.11.2 directories. See if appending / to your pattern helps to possibly ignore files.

Also, try using the iterator version iglob which will save the cost of glob putting everything in a list.

filter(lambda p: p.count('6.11.2') == 1, glob.iglob('PROJECT/**/6.11.2/', recursive=True))

Otherwise you could always write your own directory traversal with os.scandir.

user_4219140
Related