Skip to content
key 1 6,726 exact key 2 3,236 exact key 3 2,035 exact key 4 1,440 ± 2 key 310 9 ± 937 key 421 17 ± 937 key 840 2 ± 937 key 1491 4 ± 937 bracket, with the truth marked · widest 937 · 3 exact cash register · stationary Zipf · 32 counters the smallest counter is 938
counter-shift3 essays
4 8 16 32 64 128 10 100 10³ 10⁴ n operations (mean of 60 runs) Insertion traffic Merge traffic Insertion cmp Merge cmp traffic crosses solid: reads + writes · dashed: comparisons traffic crosses between n = 12 and 16; comparisons never do
crossover2 essays
decayed windowed 0 60 120 seconds count attributed to key 0 half-life 4 s · window 5.77 s · bursty the same key, two questions
decay-curve4 essays
1,810 3,620 5,429 7,239 0 10,000 20,000 30,000 40,000 arrivals so far count of key 1 in the last 4,096 Misra-Gries, no clock blocks of Misra-Gries the truth, and the ring buffer a heavy hitter that stops · sampled every 500 6,493 claimed, 0 true
departure1 essay
10³ 10⁴ 10 n deepest recursion random already sorted few distinct values the adversary 2 log₂ n introsort, depth factor 2 frames, counted exactly
depth-and-fallback2 essays
0 2 4 6 8 10 12 14 mean 5.71 depth share of the collection ten revisions twelve essays 75,658 characters · 2,966 phrases worst 14, mean 5.71
depth-profile4 essays
H₀ = 3.89 16 64 256 1k 4k 16k window, in symbols bits per symbol 0.0 4.3 8.6 LZSS mean symbols covered per match 4.6 5.1 5.7 6.9 8.7 9.6 model: a window of recent text, no probabilities 2.13 bits/symbol at a window of 16,384
dictionary-growth1 essay
read from the start 40,000 reads a ring of 4,096 keys and 4,096 stamps 184,320 bits read from the end 4,096 reads 792 counters, no stamps 50,688 bits items read same answer: 1×700, 2×341, 3×224… W = 4,096 · φ = 0.02 · stationary Zipf 9.8× fewer reads, same answer
direction-bill1 essay
0 4 8 12 16 20 24 28 32 36 40 44 48 slots from home pale: linear probing · dark: Robin Hood mean 2.384 identical for both worst 48 → 12 var 37 → 7 435 keys, 512 slots, seed 20260811 displacements, counted exactly
displacement-spread2 essays
the floor Merge sort 1.02× Quicksort, first 1.23× Quicksort, random 1.24× Merge sort + cutoff 1.29× Quicksort, median-3 1.32× Shellsort 1.45× Heapsort 1.96× Insertion sort 9.69× Bubble sort 19.26× Selection sort 19.38× floor = log₂(256!) = 1,684 comparisons mean of 16 runs, against a proved bound
distance-to-floor6 essays
equal lengths 5.00 bits 100.0% lengths as one over rank 4.15 bits 83.4% a few long, many short 4.31 bits 86.7% one document holding most of the text 1.69 bits 39.5% log₂ 32 32 documents · 8,192 characters 100.0% to 39.5%
document-array8 essays
4 6 8 12 windows window length spanning a join in no document with a separator English-like · 8 documents 44 invented at m = 12
document-join5 essays
2 · 0 · 1 · 2 0 1 0 1 2 0 6 · 7 · 3 · 2 5 · 0 1 2 0 1 2 2 0 1 0 1 2 1 0 2 rows document first pattern " was t" · 30 occurrences · 7 documents A filled row is the first of its document. Reporting one costs a range minimum; reading every row costs one visit per occurrence. English-like · 8 documents 30 rows · 7 documents
document-listing5 essays
— s i t t i n g — k i t t e n 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 1 2 3 4 5 6 3 3 2 1 2 3 4 5 4 4 3 2 1 2 3 4 5 5 4 3 2 2 3 4 6 6 5 4 3 3 2 3 one unit = one subproblem given a value 56 cells, 56 held at once
dp-grid17 essays
the floor that applies log₂(n!) Merge sort 2.3× 1,682 Shellsort 2.3× 1,714 Merge sort + cutoff 2.6× 1,938 Heapsort 4.2× 3,101 Quicksort, first 6.6× 4,887 Quicksort, random 7.2× 5,291 Quicksort, median-3 7.8× 5,728 Insertion sort 18.5× 13,644 Bubble sort 43.1× 31,820 Selection sort 44.2× 32,640 8 distinct values, n = 256, seeded the two floors are 2.28× apart
entropy-floor2 essays
1 10 100 1,000 0.1 1 10 100 10³ true count of the key relative error heaviest key rarest key 4×64 counters · 8,192 bits · Zipf s = 1.1 · 3,528 distinct keys at 702 positions 4.11% to 34100%
error-against-frequency5 essays
a t g a a t t c a t g a g t g a 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 errors the pattern, left to right · D below least errors needed D, the bound 4 symbols · m = 16 72 ranks · 1 resets
error-bound4 essays
100 10³ 10⁴ errors allowed, k acts 0 1 2 3 index walk the whole table 3,000 characters · m = 16 · 4 symbols no crossing in range
error-budget7 essays
exact -11.2% -3.3% 0.0% 3.3% 11.2% rmse 3.61% worst 9.71% 23 of 60 outside the band 5,120 bits · 60 seeds · relative error of one run predicted ±3.25%
error-spread4 essays
10 100 1,000 100 10³ 10⁴ 10⁵ total length of the pattern set primitive steps the definition from the links the published rule four symbols · m = 10 85.60x apart at 128 patterns
exact-construction4 essays
pattern of 24, 3 errors allowed positions in the text 20,000 candidates proposed 140 candidates verified 140 occurrences 7 pattern 24 · 3 errors · 28,700 cells against 480,000 selectivity 5.0%
filter-funnel3 essays
10 100 10³ 100 10³ 10⁴ 10⁵ n comparisons n log₂ n log₂(n!) Stirling the two routes agree to 5.1e-7 relative exact sum · Stirling
floor-curve6 essays
0.1 1 10 100 10³ 10³ 10⁴ floor, in counts arrivals in the shard, n round-robin — n^1.02 hashed — fit refused residual 2.7% slope 5.2 → 1.19 k = 32 · 40,000 arrivals the table holds 1.33 of a hashed shard's keys and 0.01 of the stream's
floor-regime5 essays
weighted path length Σ wᵢdᵢ — what Huffman minimises cuts taken Σ over the merges damage worst error left chain tree smallest-first largest-first 543k 147k 123k 738k 309 254 259 388 323 148 183 403 Misra-Gries · 32 shards · hashed least path smallest · least damage balanced
fold-order6 essays
dark: with galloping · pale: with the mode removed nearly sorted 33,952 21,373 jumped −37.7% random 95,770 2 jumped +0.0% few distinct values 57,912 41,178 jumped −36.9% n = 8,192, MIN_GALLOP = 7 comparisons, counted exactly
gallop-profile1 essay
100 10³ 10³ 10⁴ 10⁵ 10⁶ 10⁷ V counted work Breadth-first Dijkstra, binary heap Dijkstra, all V queued Bellman–Ford, all passes V from 64 to 2048, sparse, fixed average degree work = scans + visits + relaxations + queue comparisons
graph-growth20 essays
the occurrence at 100 sources 1 of 137 phrases copy from a region that holds it English-like · 4 copies · z = 156 1 covering · 137 copying
grid-propagation4 essays
rank among the boundaries, sorted by the text before them sorted by the text after 0 in the rectangle pattern "ss is un" split after 4 0 end with the left half 0 begin with the right English-like · 2 copies of 512 z = 156 · 0 crossing
grid-rect4 essays
100 10³ 100 10³ 10⁴ 10⁵ 10⁶ n comparisons Insertion Merge Heapsort Quicksort a power law is a straight line here comparisons, counted exactly
growth-curve5 essays
0% 25% 50% 75% 1 2 3 4 5 ×1.125 ×1.25 ×1.5 ×2 ×3 ×4 capacity left unused at the end amortised cost per append 20,000 appends, cost = 1 write + a copy on resize neither end wins
growth-tradeoff2 essays
quicksort on sorted input — comparisons first-element pivot 2,096,128 random pivot 25,318 a search tree built from sorted keys — height binary search tree 2,047 treap 26 a hash table on keys chosen to collide — worst bucket the low bits of the key 2,048 multiply–shift, a at random 10 n = 2,048, bars on a logarithmic scale deterministic above, randomised below
guarantee-under-attack2 essays
forward · wavelet tree 18,377 forward · rank directories 5,037 forward · C table 100 forward · sample marks 8,193 forward · sampled positions 3,598 reverse · wavelet tree 18,377 reverse · rank directories 5,037 reverse · C table 100 reverse · sample marks 8,193 dropped reverse · sampled positions 3,598 dropped 8,192 characters · sampling every 32 16.7% of both halves
half-index4 essays
average 8.0 0 12 24 bucket, 0 to 255 keys in the bucket multiply–shift · ordinary keys worst bucket 16 against 8.0
hash-loads11 essays
10³ 10⁴ 10³ 10⁴ 10⁵ n comparisons bottom-up (Floyd) repeated insertion n from 128 to 65,536, random input, seeded 1.21× between the two at the right-hand edge
heap-build1 essay
suffix array + text 311,296 19.00 b/ch counter array per symbol 5,407,710 330.06 b/ch FM-index, plain 100,947 6.16 b/ch FM-index, compressed 36,804 2.25 b/ch the packed text one bar shaded darker needs the text · English-like sigma 21, sample 64
index-size14 essays
0 100 200 300 10 20 30 distinct symbols in the interval bit-vector ranks the loop: 320 the descent sigma = 32 throughout 32x down to 5.16x
interval-symbols8 essays
Sorted array (binary search) 2 blocks Level order 4 blocks van Emde Boas 2 blocks memory address, left to right · alternating outlines are blocks B = 8, M = 64 (M/B = 8) 4 blocks against 2, for the same 6 comparisons
layout-map3 essays
share of nodes predicted level 1 49.68% · 50.00% level 2 25.29% · 25.00% level 3 12.52% · 12.50% level 4 6.24% · 6.25% level 5 3.08% · 3.13% level 6 1.64% · 1.56% level 7 0.79% · 0.78% level 8 0.34% · 0.39% 20,000 nodes, p = 0.5, seed 5150 worst departure 0.32 points
level-distribution2 essays
algorithm spread of count ⁄ f(n) — 1.0 is exact Timsort Python, Java objects, Rust, Android 1.085 n log n Introsort C++ std::sort 1.125 n log n Pattern-defeating quicksort Rust unstable sort, Boost, libstdc++ 14 1.039 n log n Dual-pivot quicksort Java Arrays.sort, primitives 1.094 n log n tolerance 1.6 fitted n = 256–16,384 comparisons, counted exactly
library-audit1 essay
Timsort 95,770 ships Introsort 130,863 ships pdqsort 114,408 ships Dual-pivot 116,836 ships algorithm comparisons random, n = 8,192 comparisons, counted exactly
library-scoreboard6 essays
10³ 10³ 10⁴ V modelled misses adjacency list CSR array 96% miss 27% miss 64 lines × 8 elements, fully associative, LRU 3.6× between two layouts of one graph
list-against-csr1 essay