Frequency stack and a constant-time counter

A maximum frequency stack is a stack whose pop() removes the value that occurs most often on it, and among values that occur equally often, the one pushed most recently. A constant-time counter is its sibling: it counts keys up and down and can name a key with the most or the fewest counts, each call in O(1). Both appear wherever a system must keep serving “the most requested” while requests keep arriving: song requests, trending tags, busy pages. Counting on every call is correct and quadratic overall. The rest of this opening sets out an original request-box problem, counts what its brute force costs, and names the observation behind both O(1) designs.

The problem: a DJ’s request box

The box is a frequency stack with songs as its values. Six requests, for waltz, salsa, waltz, salsa, tango and waltz, followed by six plays, give waltz, salsa, waltz, tango, salsa and waltz. The second play settles a tie: waltz and salsa both have two slips left, and salsa’s second slip is newer. In a second test, requests for jive and polka and one play give polka.

The brute force: count every slip on every play

Keep the slips in a list. Each play() counts the slips of every song and remembers each song’s newest slip, then takes out the winner’s newest slip. A request costs O(1), but a play reads every slip still in the box. The slowest test makes n requests and then plays them all:

"""The first design that comes to mind: keep every slip in a list, and on each play() count the slips of every song
to find the winner. The answers are right; this program counts the slips each play() reads on the slowest test.
"""


class ScanBox:
    def __init__(self):
        self.slips = []  # songs in the order their slips arrived
        self.reads = 0

    def request(self, song):
        self.slips.append(song)

    def play(self):
        count, newest = {}, {}
        for i, song in enumerate(self.slips):
            self.reads += 1
            count[song] = count.get(song, 0) + 1
            newest[song] = i
        best = max(count, key=lambda s: (count[s], newest[s]))  # most slips, then the newest slip
        del self.slips[newest[best]]  # take that song's newest slip out of the box
        return best


box = ScanBox()
for song in ["waltz", "salsa", "waltz", "salsa", "tango", "waltz"]:
    box.request(song)
print("example:", [box.play() for _ in range(6)])

# The slowest test: n requests spread over 100 songs, then n plays, each of which reads every slip left.
for n in (500, 1_000, 2_000):
    box = ScanBox()
    for i in range(n):
        box.request(f"song-{i % 100}")
    for _ in range(n):
        box.play()
    print(f"n = {n:,}: {n:,} plays read {box.reads:,} slips")

n = 100_000
print(f"n = {n:,}: {n:,} plays would read {n * (n + 1) // 2:,} slips")

example: ['waltz', 'salsa', 'waltz', 'tango', 'salsa', 'waltz']
n = 500: 500 plays read 125,250 slips
n = 1,000: 1,000 plays read 500,500 slips
n = 2,000: 2,000 plays read 2,001,000 slips
n = 100,000: 100,000 plays would read 5,000,050,000 slips

n plays read about n²/2 slips: 5 × 10⁹ at n = 10⁵, some eight minutes of CPython.

What to notice

Number each song’s slips: its first slip, its second, and so on. A song with c slips holds exactly one slip of each number from 1 to c. The song to play always has the highest number in use, and among the songs that have it, the newest slip with that number wins. So group the slips by number, keep each group in arrival order, and the answer is the newest slip of the highest group. Three designs build on this:

• A stack per count level keeps each group as a stack and remembers the highest level in use.
• A heap of (count, arrival) entries pushes one entry per slip and pops the largest.
• A constant-time counter links its count buckets in a list, so increments, decrements and both extremes are O(1).

Stacks per count level, step by step Pro: opens with a Pro, Premium or Ultimate pass