Introduction

Finding the 100 most frequent values in 4 billion numbers is a frequency-counting problem, not a sorting problem. The right design depends less on the row count and more on two practical questions: how many distinct numbers exist, and whether the answer must be exact.

If the distinct value count is small enough, one pass with a frequency table is enough. If the distinct count is huge, you need to partition the work so no single process has to hold every counter at once.

Separate Counting from Ranking

The first optimization is conceptual. You do not need to sort 4 billion inputs. You need to count occurrences and then keep only the top 100 counts.

For a manageable number of distinct values, a streaming counter plus a fixed-size heap is exact and efficient:

1from collections import Counter
2import heapq
3
4
5def top_k_from_file(path, k=100):
6    counts = Counter()
7
8    with open(path, "r", encoding="utf-8") as handle:
9        for line in handle:
10            value = int(line.strip())
11            counts[value] += 1
12
13    heap = []
14    for value, frequency in counts.items():
15        item = (frequency, value)
16        if len(heap) < k:
17            heapq.heappush(heap, item)
18        else:
19            heapq.heappushpop(heap, item)
20
21    return sorted(heap, reverse=True)
22
23
24print(top_k_from_file("numbers.txt", k=5))

This works because the expensive part is storing the frequency table, not storing the top 100 results. The heap stays tiny. The counter is what determines whether this strategy fits in memory.

Partition When the Distinct Count Is Too Large

If the number of unique values is too large for one in-memory counter, split the input into buckets first. The same value must always go to the same bucket, so hashing works well.

1from collections import Counter
2from pathlib import Path
3import heapq
4
5
6def bucketize(input_path, output_dir, bucket_count=64):
7    output_dir = Path(output_dir)
8    output_dir.mkdir(parents=True, exist_ok=True)
9    writers = [open(output_dir / f"bucket-{i}.txt", "w", encoding="utf-8") for i in range(bucket_count)]
10
11    try:
12        with open(input_path, "r", encoding="utf-8") as source:
13            for line in source:
14                value = int(line.strip())
15                bucket_index = hash(value) % bucket_count
16                writers[bucket_index].write(f"{value}\n")
17    finally:
18        for writer in writers:
19            writer.close()
20
21
22def merge_top_k(output_dir, k=100):
23    heap = []
24
25    for bucket_path in Path(output_dir).glob("bucket-*.txt"):
26        counts = Counter()
27        with open(bucket_path, "r", encoding="utf-8") as bucket_file:
28            for line in bucket_file:
29                counts[int(line.strip())] += 1
30
31        for value, frequency in counts.items():
32            item = (frequency, value)
33            if len(heap) < k:
34                heapq.heappush(heap, item)
35            else:
36                heapq.heappushpop(heap, item)
37
38    return sorted(heap, reverse=True)

This design turns one impossible counting task into many smaller exact ones. It also maps cleanly onto distributed systems because each bucket can be processed independently.

Use an Array When the Range Is Small

Sometimes the input volume is huge but the numeric range is tiny. In that case, an array is faster and usually more memory efficient than a hash map.

1def top_k_small_range(values, max_value, k=100):
2    counts = [0] * (max_value + 1)
3
4    for value in values:
5        counts[value] += 1
6
7    ranked = sorted(
8        ((frequency, value) for value, frequency in enumerate(counts) if frequency > 0),
9        reverse=True,
10    )
11    return ranked[:k]
12
13
14print(top_k_small_range([4, 1, 4, 2, 4, 2, 3], max_value=10, k=3))

This works well for ranges such as event codes or bounded identifiers. It is a poor choice when values are sparse across a huge range, because the array would waste memory on values that never appear.

Decide Early Whether Approximation Is Allowed

If the exact top 100 is not required, heavy-hitter algorithms can reduce memory usage dramatically. Techniques such as Misra-Gries or Count-Min Sketch are useful when the goal is to detect the dominant values rather than report exact counts for every candidate.

That is not just an implementation detail. It is a product requirement. If the answer feeds billing, auditing, or a customer-facing report, approximation may be unacceptable. If the answer feeds dashboard exploration or anomaly detection, it may be a perfectly reasonable tradeoff.

Common Pitfalls

The biggest mistake is sorting all 4 billion numbers directly. Sorting solves a different problem and usually costs more CPU, disk, and memory than counting frequencies first.

Another mistake is ignoring distinct cardinality. Four billion rows can still be easy if there are only a few thousand unique values, and still be hard if almost every value is different.

I/O is also a real bottleneck at this scale. A good algorithm can still perform badly if it reads inefficiently, writes too many temporary files, or runs far from the data source.

Finally, do not choose an approximate algorithm by accident. If the result must be exact, partitioning and exact counting are the safer design even when they are operationally heavier.

Summary

• Treat the task as frequency counting followed by top-100 ranking.
• Use a small heap for the final ranking step instead of sorting every candidate.
• Count in memory only if the distinct value set fits comfortably.
• Partition by hash when exact counts do not fit in one process.
• Use dense arrays only when the numeric range is genuinely small.