Stochastic Blog

Sorting, hashing, and sketches on 370,103 words

The Stochastic Blog Team

The Stochastic Blog Team

— 7 min read
Share
Feature figure for Sorting, hashing, and sketches on 370,103 words

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.

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.

The dataset

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.

Figure 1 shows the word-length distribution for the cleaned vocabulary.

Word-length frequency curve

Figure 1: Word lengths cluster between 3 and 10 characters and fall off steadily on a log scale in the long tail.

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.

Complexity

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.

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.

Sorting

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.

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)

Read more