Pick a random file from a directory tree

Question

I'm working on a python module to randomly choose a wallpaper for my desktop background among thousands of pictures in my photo library.

I though I'd make a general function:

get_random_file(ext, top)

Return the name of a random file in a directory tree with top as root.

Since I'm dealing with a very large directory tree, listing all possible files would be very time consuming (edit: see comments on C. Harley answer). So I went for heuristic method, making sure all files are covered and adding an upper bound in case there are no files with given extension. There are occasionally false negatives, which is not a too big deal, but most importantly, it runs nearly instantly.

Algorithm is simple:

1. Get a list of directories, including .
2. Pick a random directory from that list.
3. If the picked directory is . (either randomly, or only available option), then retrieve a list of files in that directory.
4. If the list of files is empty, go back to 1.
5. Return a random file from that list.

Note that this algorithm can go many levels deep into sub-directories.

So far I'm happy with performance and returned values. It is able to quickly pick up a file in a very large tree.

However, I'm after general comments in terms of performance and also code style.

What I'm not particularly proud of in my code is the use of next(os.walk(top))[1] to get the list of sub-directories in the current directory.

There are also false negatives, when asking for a file extension with not many occurrences in a tree with many directories. However, I don't want to increase the limit too much to avoid waiting when really there are not such files in the tree.

The code:

# -*- coding: utf-8 -*-
"""
Created on Wed Aug 29 14:05:27 2018
@author: raf
"""
import os
import sys
import glob
import random


def get_random_files(ext, top):
    '''Return the name of a random file within a top path.

    Works recursivelly in subdirectories.

    Note that a full list of files could be got with
        glob(top + '/**/*.' + ext, recursive=True)

    However that would be extremely slow for large directories.
    '''
    _top = top
    ct, limit = 0, 50000
    while True:

        if ct > limit:
            return 'No file found after %d iterations.' % limit
        ct += 1

        try:
            dirs = next(os.walk(top))[1]
        except StopIteration:  # access denied and other exceptions
            top = _top
            continue

        i = random.randint(0, len(dirs))
        if i == 0:  # use .
            files = glob.glob(top + '/*.' + ext)
            if not files:
                top = _top
                continue
            i = random.randint(0, len(files)-1)
            return files[i]

        top += '/' + dirs[i-1]


if __name__ == '__main__':
    if len(sys.argv) > 1:
        print(get_random_files(sys.argv[1], os.getcwd()))
    else:
        print(get_random_files('*', os.getcwd()))

Answer 1

If we rewrite your code to take advantage of Pathlib, we get the following:

import os
import sys
import random
from pathlib import Path


def get_random_files2(ext, top=os.getcwd()):
    file_list = list(Path(top).glob(f"**/*.{ext}"))
    if not len(file_list):
        return f"No files matched that extension: {ext}"
    rand = random.randint(0, len(file_list) - 1)
    return file_list[rand]


if __name__ == '__main__':
    extension = sys.argv[1] if len(sys.argv) > 1 else "*"
    print(get_random_files2(extension))

I appended a "2" to the function name in my example just to make it easier to copy/paste if you want.
The benefits of using Pathlib is that we can glob directly from the path object, and it will recursively get a list of files throughout the tree.

I noticed your code only works with os.getcwd() so there was no point in injecting two parameters into get_random_files. However, I left the function signature the same in case you want to enhance it later.

The looping seemed out of place when (a) you want to check for files (b) you want a random file. So, the code gets the files or returns "No files found", and if it finds some files, picks one of them from the list of files. Please take some time to understand the approach I used. The biggest take-aways you can have are:

• Infinite loops are bad (the while True:) unless you really, really need them (because you don't want to write event-based code or you just want to block),
• Looping is always slow,
• Modifying variables inside loops is bad (your construction/approach is faulty when you modify variable content when those variables control or affect the functionality or processing of what your code is actually doing),
• if you're going to use random values, it's best to understand why you're doing that. If it's to pick from a list, ensure you populate the list first, don't rely on the random value to dictate your actions.
• Look at keeping functions to 4 or so lines - because this will ensure you adhere to the Single Responsibility principal, which makes your code better in the long run (less support and maintenance).

Otherwise, a good attempt at automation. Keep it up and post more of your code when you have it.

Answer 2

There are many problems with your approach.

• It can be extremely unfair depending on your tree structure. do a depth first complete walk and list probabilities. root is probability 1, in each level divide by number of dirs (including .), finally divide by number of (matching) files. list all these hit probabilities and compare them. if your tree is not balanced you will probably conclude to drop your approach

• It will fail to find rare file patterns. The primary chance for a file to be found is depending on the directory structure only, only the last denominator is depending on the file pattern. so this approach will not scale, limit has to grow with the actual tree size and there is a good chance that you will fail even so. In a balanced tree you could fix that by going deep randomly once, then switching to a regular DFS walk. However this will not succeed when your patterns are not evenly distributed.

I propose to do a database (simple file list or better) where you can efficiently match against your pattern and do the random select an all matches. You can update the database in the background. You will not be limited to glob patterns but can also do regex and also match path names.