bisect Instead of sort() on Every Insert (Python)

from __future__ import annotations
import bisect
import random
import time

random.seed(42)
N = 5_000  # the playground is fast; tune up for real benchmarks
rows = [random.randint(0, 1_000_000) for _ in range(N)]

# SLOW: append, then sort the whole list every time. O(N^2 log N) overall.
slow = []
t0 = time.perf_counter()
for v in rows:
    slow.append(v)
    slow.sort()
slow_ms = (time.perf_counter() - t0) * 1000

# FAST: bisect.insort finds the position in O(log N) and inserts there.
# Total work is O(N^2) for the shifts but the constant factor is far smaller.
fast = []
t0 = time.perf_counter()
for v in rows:
    bisect.insort(fast, v)
fast_ms = (time.perf_counter() - t0) * 1000

assert slow == fast, 'must produce identical sorted output'
print(f'sort-on-every-insert : {slow_ms:6.1f} ms')
print(f'bisect.insort        : {fast_ms:6.1f} ms')
print(f'speedup              : {slow_ms / fast_ms:5.1f}x')

from __future__ import annotations
import bisect
import sys

# bisect.insort gained a `key=` argument in Python 3.10. The playground runs
# 3.8, so we cannot use it directly. The 3.8 workaround: maintain a parallel
# list of keys, bisect THAT, and mirror the index into the data list.

rows = [
    {'user': 'alice', 'score': 88},
    {'user': 'bob',   'score': 42},
    {'user': 'carol', 'score': 95},
    {'user': 'dan',   'score': 71},
]

class SortedByKey:
    def __init__(self, key):
        self._key = key
        self._keys = []
        self._data = []

    def insert(self, item):
        k = self._key(item)
        idx = bisect.bisect_right(self._keys, k)
        self._keys.insert(idx, k)
        self._data.insert(idx, item)

    def __iter__(self):
        return iter(self._data)

    def top(self, n):
        return self._data[-n:][::-1]

best = SortedByKey(key=lambda r: r['score'])
for row in rows:
    best.insert(row)
best.insert({'user': 'eve', 'score': 60})

for entry in best:
    print(entry)

print('top 2:', best.top(2))
print('python:', sys.version.split()[0])

from __future__ import annotations
import bisect

# The two bisect variants differ only on equal keys. Use bisect_left when you
# want the index 'just before' equal keys; bisect_right when you want the index
# 'just after'. The bug I keep solving in code review: counting how many items
# are strictly less than v vs less-than-or-equal.

a = [1, 3, 5, 5, 5, 8, 13]

lt = bisect.bisect_left(a, 5)   # number strictly less than 5
le = bisect.bisect_right(a, 5)  # number less than or equal to 5
print(f'< 5  : {lt}')
print(f'<= 5 : {le}')
print(f'count of 5: {le - lt}')

# Range query: how many are in the closed interval [2, 6]?
lo = bisect.bisect_left(a, 2)
hi = bisect.bisect_right(a, 6)
print(f'count in [2, 6]: {hi - lo}  -> {a[lo:hi]}')

# Insert position with equal keys: left keeps the newcomer at the front of
# the equal run, right at the back.
b_left = a.copy(); bisect.insort_left(b_left, 5)
b_right = a.copy(); bisect.insort_right(b_right, 5)
print('insort_left :', b_left)
print('insort_right:', b_right)