selecteer random element uit een grote lijst (of: regel uit file)

Wednesday 29 December 2010, 23:46:00 | python

Als je van te voren weet hoe veel elementen je hebt om uit te kiezen, is het kinderlijk eenvoudig om 1 willekeurige daaruit te kiezen: Neem een willekeurig getal tussen 1...N en pak het zoveelste element.

Als je de complete verzameling zonder problemen in memory kan houden, kun je het in Python direct met random.choice(...) doen.

Het wordt lastiger als de verzameling elementen niet in 1 keer in memory gelezen kan worden (bijvoorbeeld omdat hij te groot is, of zelfs een onbekende grootte heeft). Een voorbeeld is dat je een willekeurige regel uit een tekstbestand wilt hebben waarbij je niet van tevoren weet hoe groot dat bestand is.

Je kunt proberen het hele bestand in te lezen en daarna 1 regel eruit te halen zoals boven beschreven, maar dat kost erg veel tijd en geheugen als het bestand groot is. Beter is om een slim algoritme te gebruiken:

import random

def random_line(afile):
    line = next(afile)
    for num, aline in enumerate(afile):
        if random.randrange(num + 2): continue
        line = aline
    return line

Dit is de Python implementatie van Waterman's "Reservoir Algorithm". Het loopt de complete file slechts 1 keer door en heeft nooit meer geheugen nodig dan de huidige regel lang is. Bron.