Sorting, hashing, and sketches on 370,103 words

Sign in<br>Subscribe

In Post 2 we built the foundations with Python lists, dicts, sets, and recursion, learning how the language's core containers behave under load. Now we put those tools through their paces on a real dataset: 370,103 English words, one per line, drawn from the dwyl/english-words repository. By the end of this post we will have sorted them six ways, hashed them into four different structures, and sketched them with four probabilistic algorithms, all while tracking what each approach costs in time and memory. The headline: HyperLogLog estimates the vocabulary size with just 2.71 percent error using only 4,096 registers.<br>Think of this post as a field guide to the algorithms that keep modern systems fast. Every time you type a query into a search box, the engine is sorting, hashing, and sketching behind the scenes. We will build each of these mechanisms from scratch, measure them on real words, and see which ones earn their complexity.<br>The dataset<br>The word list arrives as a single column of lowercase strings, about 21.63 MB in memory. The raw file contains duplicates and missing values; cleaning leaves 370,103 unique words. Two missing values appear in the raw file, which we strip and clean away. The vocabulary settles at 370,103 unique words, with no duplicate rows to worry about. Word lengths skew right with a long tail past 15 characters, and the out-of-vocabulary rate on a 20 percent holdout hits 1.0, meaning every word in the test split is unseen. That last number matters: it tells us membership structures will face nothing but novel queries.<br>Figure 1 shows the word-length distribution for the cleaned vocabulary.<br>Figure 1: Word lengths cluster between 3 and 10 characters and fall off steadily on a log scale in the long tail.<br>This shape drives our later choices: the long tail means tries will have deep paths, and the high OOV rate means hash tables will face constant misses.<br>Complexity<br>Before we sort anything, we need a language for talking about cost. Big-O notation gives an upper bound on growth, Big-Theta notation pins the exact asymptotic class, and amortized analysis measures cost across a sequence of operations rather than a single call. We measure all three on the operations the rest of the post uses.<br>The built-in sort on 50,000 words takes 0.0011 seconds, on 100,000 it takes 0.0022, and on 200,000 it takes 0.0053. Doubling the input roughly doubles the time, the signature of an n log n algorithm. Timsort, Python's default, sits in Big-Theta(n log n). List append tells a different story: 200,000 appends complete in 0.0071 seconds total, about 4e-08 seconds per operation, which is O(1) amortized. List insert at position zero is the cautionary tale. We only insert 5,000 items, forty times fewer than the appends, yet the operation takes 0.0019 seconds, still slower per operation at 3.8e-07 seconds. That gap is the whole lesson: asymptotic analysis predicts real behavior when the constants stay honest.<br>Sorting<br>Binary search needs a sorted array, so we start there. We sample 5,000 words with a fixed seed, sort them, and confirm that binary search finds a known word at index 1234 while returning -1 for a nonsense string. Then we implement the classic sorts by hand.<br>def quicksort(arr):<br>if len(arr) pivot]<br>return quicksort(left) + middle + quicksort(right)

This post is for paying subscribers only

Subscribe now<br>Already have an account? Sign in

Read more

Information Theory in One Sitting

In Posts 3 and 4 we built the probabilistic foundations and learned how to update beliefs with Bayes' rule. Now we put that machinery to work on a concrete question: how much information is actually in a piece of text? This post measures that quantity on WikiText-2, a

Statistical tests without the traps

In Post 3 we explored the Adult Census Income dataset through distributions, correlations, and outlier fences, learning to let the data speak before we model it. Now we put that exploratory foundation to work and ask the question every data scientist eventually faces: is the pattern we see real, or

Probability and estimation on census data

In the last post we wrangled the Adult Census Income dataset into a clean, analysis-ready form. Now we turn that clean data into a laboratory for the core ideas of probability and estimation: Bayes' theorem, the distributions that describe real populations, the limit theorems that justify our confidence,

The linear algebra and calculus behind every model

Last time we built our first Python pipeline and learned to load, inspect, and manipulate data. Now we take the next step: every machine learning model, from linear regression to deep neural networks, rests on three pillars: linear algebra, calculus, and convex optimization. We'll build each one from

Powered by Ghost