Python 3: How to best iterate over all lines in a big file (+1 million lines) in a random order

Question

Ok, so I have multiple textfiles, each containing well over 500.000 or even 1.000.000 lines.

Currently I do something like this:

import random

def line_function(line):
    # Do something with given line

def random_itteration(filepath):
    with open(filepath) as f:
        lines = f.readlines()
        random.shuffle(lines)
        for line in lines:
            result = line_function(line)

The thing is that the Python Docs on random.shuffle() clearly state (emphasis added by me):

Note that even for small len(x), the total number of permutations of x can quickly grow larger than the period of most random number generators. This implies that most permutations of a long sequence can never be generated. For example, a sequence of length 2080 is the largest that can fit within the period of the Mersenne Twister random number generator.

So the question is:

What would be the fastest and most efficient way to make my setup work as intended?

Further info:

There is a reason why I want to apply line_function() to a random line and not simply iterate over them in the sequence they are in. Also note that I highly prefer to only process each line once.

Finally, shuffling the textfile up front, or dividing it into smaller files unfortunately isn't an option. And isn't what I am asking.

---

Any insights are more then welcome! Thnx in advance guys.

Answer 1

As Mark Dickinson says, the doc line you are quoting has essentially no practical implications for real-world code. It definitely doesn't have any relevance for your code.

It doesn't matter whether the shuffle produces a truly uniform random distribution over all possible permutations. What matters is whether the shuffle is distinguishable from such a distribution, up to some standard of distinguishability. random.shuffle is statistically indistinguishable from a perfectly random shuffle up to the quality of the underlying Mersenne Twister algorithm, and the ways in which it is distinguishable have nothing to do with the period.

You don't need to do anything special to make your setup "work as intended". random.shuffle already works.

Answer 2

You're going to have trouble doing this "quickly and efficiently" in Python, but if you must, the place to start is going to be a shuffling algorithm like the Fisher-Yates algorithm.

Once you implement that, load your files, and record at which byte offset each line starts at. Shuffle that array, open your files, then iterate over your array, and read from the offset to the next newline.

With datasets as large as you're proposing, it's reasonable to expect that lines = f.readlines() will simply be too much memory pressure, demanding a more complex, but more scalable solution, using offsets.

For more efficient reruns, perhaps also consider saving out the offset metadata once it's generated, so you don't need to walk over the whole file (or the whole files) every time.

Answer 3

I'd rather do a shuffle on a list of integers than the huge lines.
(Integers being the index/position of the line in the list of lines)
Something like this:

import random
from random import randint

def line_function(line):
    # Do something with given line

def random_itteration(filepath):
    with open(filepath) as f:
        lines = f.readlines()
        count = len(lines)
        #random_index_list = random.shuffle(list(xrange(count)))
        random_index_list = random.sample(range(count+1),count)
        for index in random_index_list:
            result = line_function(lines[index])

        #shuffled_lines = random.shuffle(lines)
        #for line in shuffled_lines:
        #    result = line_function(line)