Sorting, Hashing, and Sketches on 370,103 Words

Following our work in Post 2—where we established the groundwork using recursion and Python's native sets, dicts, and lists to see how they handle stress—it is time to apply those concepts to a tangible dataset.

We are utilizing a collection of 370,103 English words (sourced from the dwyl/english-words repository), with each word occupying its own line.

🎯 Objectives

Our goal is to stress-test these tools through the following:

• Sort the dataset using six different methods.
• Organize the words into four distinct hashing structures.
• Approximate the data using four probabilistic sketching algorithms.
• Quantify the time and memory overhead for every approach.

The Key Takeaway: Using only 4,096 registers, the HyperLogLog algorithm can estimate the total vocabulary size with a remarkably low error rate of just $2.71\%$.

This analysis serves as a field guide to the algorithms powering modern high-speed systems. Whether it's a search engine query or a database lookup, these mechanisms of sorting, hashing, and sketching are operating beneath the surface. We will reconstruct these from the ground up to determine which complexities are truly justified.

---

📊 The Dataset

The raw data consists of a single column of lowercase strings, totaling approximately 21.63 MB in memory. The preparation process involved removing duplicates and missing values.

Key Statistics:

• Final Count: 370,103 unique words.
• Distribution: Word lengths are right-skewed, with a significant "long tail" extending beyond 15 characters.
• OOV Rate: On a 20% holdout set, the Out-of-Vocabulary rate is $1.0$.

This implies that any membership structure we build will encounter exclusively novel queries during testing.

Figure 1: Word lengths primarily cluster between 3 and 10 characters, decaying on a log scale.

Impact: This specific distribution means that tries will encounter deep paths, and hash tables will frequently experience misses.

---

⏱️ Computational Complexity

To evaluate our algorithms, we utilize three primary lenses of analysis:

1. Big-O Notation ($O$): Defines the asymptotic upper bound.
2. Big-Theta Notation ($\Theta$): Pinpoints the exact asymptotic class.
3. Amortized Analysis: Calculates the average cost of an operation over a long sequence.

Empirical Performance Measurements

We tested the built-in Python sort and list appends to verify these theories:

The data shows that doubling the input for sorting roughly doubles the time, confirming the $n \log n$ signature. The gap between append and insert highlights that while asymptotic analysis is vital, the constants matter in real-world execution.

---

🔠 Sorting

Because binary search requires a sorted array to function, sorting is our first priority. We validated this by sampling 5,000 words (using a fixed seed), sorting them, and confirming that a search for a known word at index 1234 succeeded, while a nonsense string returned -1.

Below is the implementation of the quicksort algorithm used:

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)

---

📚 Related Explorations

• Subproblems & Search: Building on Post 6, we examine overlapping subproblems and string manipulation.
• Information Theory: Expanding on Posts 3 & 4, we use Bayes' rule to measure information density in the WikiText-2 dataset.
• Statistical Traps: Using the Adult Census Income dataset to distinguish real patterns from noise.
• Probability & Estimation: Turning census data into a lab for limit theorems and probability distributions.