Coordinate compression and ranks

Coordinate compression replaces each value by its rank among the distinct values and keeps their order: the smallest value becomes rank 0 or 1, the next distinct value the next rank, and so on. Ranks let an array, a difference array, a Fenwick tree or a table indexed by value work even when the values reach 10⁹, are negative or are spread far apart, because n values have at most n distinct ranks. Coordinate compression costs one sort, O(n log n), plus one lookup per value. This lesson’s problem is the rank transform itself, replacing every score by its dense rank, and the uses of the ranks come after it.

The problem: rank the contest scores

1. [40, 10, 40, 25] gives [3, 1, 3, 2]: the distinct scores are 10, 25 and 40.
2. [-5, 7, -5, 0, 1000000000] gives [1, 3, 1, 2, 4].
3. [] gives [].

The brute force, and the array that does not fit

For every score, count the distinct scores below it and add 1. That is n × d comparisons for d distinct scores. The other obvious idea, an array with one slot per possible score, does not fit at all:

# Dense ranks by brute force: a score's rank is 1 plus the number of distinct scores below it. Then what an array
# indexed by the scores themselves would need.
import random


def ranks_brute(scores):
    """Returns the ranks and the comparisons made: one per pair of a score and a distinct score."""
    distinct = list(set(scores))
    comparisons = 0
    ranks = []
    for s in scores:
        below = 0
        for d in distinct:
            comparisons += 1
            if d < s:
                below += 1
        ranks.append(below + 1)
    return ranks, comparisons


for scores in ([40, 10, 40, 25], [-5, 7, -5, 0, 1_000_000_000], []):
    print(scores, "->", ranks_brute(scores)[0])

rng = random.Random(2)
for n in (1_000, 2_000):
    _, comparisons = ranks_brute([rng.randint(-10**9, 10**9) for _ in range(n)])
    print(f"n = {n:,} distinct scores: {comparisons:,} comparisons")
print(f"n = 1,000,000 distinct scores: {10**12:,} comparisons")
slots = 2 * 10**9 + 1
print(f"an array with one slot per possible score: {slots:,} slots, {slots * 4 / 10**9:.1f} GB as 32-bit counters")

[40, 10, 40, 25] -> [3, 1, 3, 2]
[-5, 7, -5, 0, 1000000000] -> [1, 3, 1, 2, 4]
[] -> []
n = 1,000 distinct scores: 1,000,000 comparisons
n = 2,000 distinct scores: 4,000,000 comparisons
n = 1,000,000 distinct scores: 1,000,000,000,000 comparisons
an array with one slot per possible score: 2,000,000,001 slots, 8.0 GB as 32-bit counters

The count made 4,000,000 comparisons for 2,000 different scores and would make 10¹² for a million, far beyond a time limit. An array indexed by the score itself needs 2,000,000,001 slots, 8 GB as 32-bit counters, even for a list of five scores.

What to notice

Only the order of the scores matters, never their size, and a list of n scores has at most n distinct values. Put in order once, the distinct values can serve as the index: a score’s rank is its position among them, whatever its magnitude.

Compress with one sort and one lookup Pro: opens with a Pro, Premium or Ultimate pass