Blog

Soms hebben we wat gedachten, deze schrijven we dan hier op.

Het genereren van veel willekeurige unieke strings

Een klant had een interessant probleem. Ze wilden een bestand met 220 miljoen unieke strings van 8 karakters lang, uit een bepaalde reeks. Een van de eisen was dat de distributie zo goed mogelijk was, dus een geshuffelde lijst van 220 miljoen opeenvolgende elementen ging het hem niet worden. En dubbele nummers mochten absoluut niet voorkomen.

De klant had het zelf al geprobeerd, maar de oplossing was te zwaar en voldeed uiteindelijk niet. Hier was dus een creatieve aanpak voor nodig.

Als je aan een dergelijk probleem denkt, denk je natuurlijk automatisch aan Donald Knuth. Zijn random sampling algoritme leek me een perfecte kandidaat om dit probleem aan te pakken. Het algoritme is in de basis (in pseudocode):

int n = 220000000;
int result[n];
for (int i = max; i > 0; i--)
{     
    const int random = getrandom() % i;

    if (random < n)
    {
      const int candidateValue = max - i;
      result[--n] = candidatevalue;
    }
}

Dat wil dus zeggen: loop het hele bereik af, en besluit willekeurig per element of je hem pakt of niet. Het leuke aan dit algoritme is, is dat je de kans dat random < n zo manipuleert dat je aan het einde gegarandeerd n elementen hebt gepakt.

Vervolgens zit je nog met de strings. Ze waren 8 karakters lang, en de reeks van geldige karakters was 24 lang. Dus, er waren 24^8 = 110075314176 mogelijke combinaties. Dit is minder dan in
een 64 bit int past, dus het bovengenoemde algoritme was hier perfect op toepasbaar. En met 8*220.000.000 kost het 'maar' 1,8 GB aan RAM. We hoefden alleen aan het eind de getallen nog even door een soort van base-24 encoder te halen.

Maar daar houden we niet op. Het bereik 0 tot 220.000.000 kan je heel makkelijk opdelen in stukken. Vervolgens kan je elke core van je CPU een deel laten genereren. Nog even een sorteer + uniekcontrole (plus hershuffle) aan het einde om er zeker van te zijn dat je geen dubbele hebt, en je hebt een tool die binnen enkele minuten de gewenste data genereert: