Dit artikel onderzoekt de praktische toepassing en prestaties van verschillende algoritmen voor sorteren, hashen en 'sketchen' (probabilistische datastructuren) aan de hand van een dataset van 370.103 unieke Engelse woorden.
De kernpunten uit het artikel zijn:
- Datasetanalyse: Er wordt gewerkt met de
dwyl/english-words repository. De analyse van woordlengtes en het hoge out-of-vocabulary (OOV) percentage bepaalt de keuze voor specifieke datastructuren.
- Computationele Complexiteit: Het artikel legt het verschil uit tussen Big-O, Big-Theta en amortiseerde analyse. Door middel van metingen in Python wordt aangetoond hoe Timsort ($n \log n$) en lijstoperaties (
append vs insert) zich in de praktijk gedragen.
- Algoritmen: Er wordt ingegaan op het belang van gesorteerde arrays voor binair zoeken en er wordt een handmatige implementatie van Quicksort gegeven.
- Probabilistische benaderingen: Een belangrijke conclusie is dat HyperLogLog zeer efficiënt is; het kan de grootte van het vocabulaire schatten met een foutmarge van slechts 2,71 procent met minimale registers.
Sorteren, hashen en sketches op 370.103 woorden
Beschouw dit bericht als een veldgids voor de algoritmen die moderne systemen snel houden. Elke keer dat u een zoekopdracht in een zoekveld typt, is de engine op de achtergrond bezig met sorteren, hashen en sketchen. We zullen elk van deze mechanismen vanaf nul opbouwen, ze meten op echte woorden en zien welke de complexiteit waard zijn.
De dataset
De woordenlijst wordt geleverd als een enkele kolom van kleine letters, ongeveer 21,63 MB in het geheugen. Het ruwe bestand bevat duplicaten en ontbrekende waarden; na het opschonen blijven er 370.103 unieke woorden over. Twee ontbrekende waarden in het ruwe bestand zijn verwijderd. De uiteindelijke vocabulaire bestaat uit 370.103 unieke woorden, zonder dubbele rijen. De woordlengtes vertonen een scheve verdeling naar rechts met een lange staart die voorbij de 15 tekens gaat. Het out-of-vocabulary (OOV) percentage op een holdout van 20 procent bedraagt 1,0, wat betekent dat elk woord in de testset onbekend is. Dat laatste getal is belangrijk: het vertelt ons dat lidmaatschapsstructuren uitsluitend te maken zullen krijgen met nieuwe queries.
Figuur 1 toont de verdeling van de woordlengtes voor de opgeschoonde vocabulaire.
Figuur 1: Woordlengtes clusteren tussen de 3 en 10 tekens en nemen gestaag af op een logaritmische schaal in de lange staart.
Deze vorm bepaalt onze latere keuzes: de lange staart betekent dat tries diepe paden zullen hebben, en het hoge OOV-percentage betekent dat hashtabellen constant met 'misses' te maken zullen krijgen.
Complexiteit
Voordat we iets sorteren, hebben we een taal nodig om over kosten te praten.
- Big-O notatie geeft een bovengrens aan de groei.
- Big-Theta notatie bepaalt de exacte asymptotische klasse.
- Amortiserede analyse meet de kosten over een reeks bewerkingen in plaats van één enkele aanroep.
We meten alle drie op de operaties die in de rest van het bericht worden gebruikt.
De ingebouwde sorteerfunctie bij 50.000 woorden duurt 0,0011 seconden; bij 100.000 duurt het 0,0022 seconden en bij 200.000 seconds 0,0053 seconden. Het verdubbelen van de invoer verdubbelt ongeveer de tijd, wat het kenmerk is van een $n \log n$ algoritme. Timsort, de standaard in Python, bevindt zich in $\text{Big-Theta}(n \log n)$.
List append vertelt een ander verhaal: 200.000 appends worden voltooid in totaal 0,0071 seconden, ongeveer $4\text{e-}08$ seconden per bewerking, wat $\text{O}(1)$ amortiseerd is. List insert op positie nul is het waarschuwingsvoorbeeld. We voegen slechts 5.000 items in—veertig keer minder dan de appends—toch duurt de operatie 0,0019 seconden, wat per bewerking nog steeds langzamer is ($3,8\text{e-}07$ seconden). Dat gat is de kernles: asymptotische analyse voorspelt het werkelijke gedrag wanneer de constanten consistent blijven.
Sorteren
Binair zoeken vereist een gesorteerd array, dus we beginnen daar. We selecteren 5.000 woorden met een vaste seed, sorteren deze en bevestigen dat binair zoeken een bekend woord vindt op index 1234, terwijl het -1 teruggeeft voor een onzinnige reeks tekens. Vervolgens implementeren we de klassieke sorteeralgoritmen handmatig.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
Sorteren, hashen en sketches op 370.103 woorden
Beschouw dit bericht als een veldgids voor de algoritmen die moderne systemen snel houden. Elke keer dat u een zoekopdracht in een zoekveld typt, is de engine op de achtergrond bezig met sorteren, hashen en sketchen. We zullen elk van deze mechanismen vanaf nul opbouwen, ze meten op echte woorden en zien welke de complexiteit waard zijn.
De dataset
De woordenlijst wordt geleverd als een enkele kolom van kleine letters, ongeveer 21,63 MB in het geheugen. Het ruwe bestand bevat duplicaten en ontbrekende waarden; na het opschonen blijven er 370.103 unieke woorden over. Twee ontbrekende waarden in het ruwe bestand zijn verwijderd. De uiteindelijke vocabulaire bestaat uit 370.103 unieke woorden, zonder dubbele rijen. De woordlengtes vertonen een scheve verdeling naar rechts met een lange staart die voorbij de 15 tekens gaat. Het out-of-vocabulary (OOV) percentage op een holdout van 20 procent bedraagt 1,0, wat betekent dat elk woord in de testset onbekend is. Dat laatste getal is belangrijk: het vertelt ons dat lidmaatschapsstructuren uitsluitend te maken zullen krijgen met nieuwe queries.
Figuur 1 toont de verdeling van de woordlengtes voor de opgeschoonde vocabulaire.
Figuur 1: Woordlengtes clusteren tussen de 3 en 10 tekens en nemen gestaag af op een logaritmische schaal in de lange staart.
Deze vorm bepaalt onze latere keuzes: de lange staart betekent dat tries diepe paden zullen hebben, en het hoge OOV-percentage betekent dat hashtabellen constant met 'misses' te maken zullen krijgen.
Complexiteit
Voordat we iets sorteren, hebben we een taal nodig om over kosten te praten.
- Big-O notatie geeft een bovengrens aan de groei.
- Big-Theta notatie bepaalt de exacte asymptotische klasse.
- Amortiserede analyse meet de kosten over een reeks bewerkingen in plaats van één enkele aanroep.
We meten alle drie op de operaties die in de rest van het bericht worden gebruikt.
De ingebouwde sorteerfunctie bij 50.000 woorden duurt 0,0011 seconden; bij 100.000 duurt het 0,0022 seconden en bij 200.000 seconds 0,0053 seconden. Het verdubbelen van de invoer verdubbelt ongeveer de tijd, wat het kenmerk is van een $n \log n$ algoritme. Timsort, de standaard in Python, bevindt zich in $\text{Big-Theta}(n \log n)$.
List append vertelt een ander verhaal: 200.000 appends worden voltooid in totaal 0,0071 seconden, ongeveer $4\text{e-}08$ seconden per bewerking, wat $\text{O}(1)$ amortiseerd is. List insert op positie nul is het waarschuwingsvoorbeeld. We voegen slechts 5.000 items in—veertig keer minder dan de appends—toch duurt de operatie 0,0019 seconden, wat per bewerking nog steeds langzamer is ($3,8\text{e-}07$ seconden). Dat gat is de kernles: asymptotische analyse voorspelt het werkelijke gedrag wanneer de constanten consistent blijven.
Sorteren
Binair zoeken vereist een gesorteerd array, dus we beginnen daar. We selecteren 5.000 woorden met een vaste seed, sorteren deze en bevestigen dat binair zoeken een bekend woord vindt op index 1234, terwijl het -1 teruggeeft voor een onzinnige reeks tekens. Vervolgens implementeren we de klassieke sorteeralgoritmen handmatig.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
Groetjes,