dsbench

A data structures and algorithms toolkit with empirical complexity benchmarks and ASCII visualizations.

This started as my own interview / grad-school-exam review: instead of re-reading textbooks, I implemented every classic structure from scratch and then measured that it actually behaves the way the textbooks say. The benchmark harness fits real timing curves against the textbook growth classes, so "O(n log n)" is a claim you can check.

Features

module	contents
dsbench.linear	stack (running min), circular-buffer queue & deque, linked lists
dsbench.sorting	insertion, selection, bubble, merge, quick, heap sort (key/reverse)
dsbench.hashing	chained and open-addressing hash tables
dsbench.searching	binary search, lower/upper bounds
dsbench.trees	BST: traversals, kth-smallest, LCA
dsbench.balanced	AVL (order statistics), red-black, splay, treap
dsbench.heaps	binary heap, meldable binomial & leftist heaps
dsbench.strings	KMP, Rabin-Karp, Z-function, Manacher, edit distance, LCS
dsbench.trie	prefix tree with ordered expansion and deletion
dsbench.graph	weighted graphs, BFS/DFS, components, cycles, topological sort
dsbench.unionfind	disjoint sets with path compression
dsbench.shortest	Dijkstra, Bellman-Ford, Floyd-Warshall, A*
dsbench.mst	Kruskal, Prim
dsbench.scc	Tarjan strongly connected components
dsbench.bipartite	2-coloring and maximum matching
dsbench.flow	Edmonds-Karp maximum flow
dsbench.skiplist	probabilistic ordered set
dsbench.bench	timing harness + empirical Big-O classification
dsbench.viz	ASCII renderers for trees, heaps, tries, graphs

Visualizations

>>> from dsbench.balanced import AVLTree
>>> from dsbench.viz import render_avl
>>> print(render_avl(AVLTree([5, 3, 8, 2, 4, 7, 9])))
                     5(+0)
                /             \
       3(+0)                       8(+0)
     /      \                    /      \
2(+0)         4(+0)         7(+0)         9(+0)

>>> from dsbench.trie import Trie
>>> from dsbench.viz import render_trie
>>> print(render_trie(Trie(["cat", "car", "card"])))
<root>
`-- c
    `-- a
        +-- r*
        |   `-- d*
        `-- t*

Benchmarks

python -m dsbench.bench --suite sorting

benchmark               sizes           classified     R^2
----------------------------------------------------------
insertion_sort          128..2048       O(n^2)       1.000
selection_sort          128..2048       O(n^2)       1.000
merge_sort              128..2048       O(n log n)   1.000
quick_sort              128..2048       O(n log n)   0.998
heap_sort               128..2048       O(n log n)   0.999

The fitter scales each candidate curve through the origin and keeps the best R^2 - see docs/benchmarking.md for the methodology and caveats.

Quickstart

pip install .            # numpy is the only dependency
python -m pytest         # ~430 tests
python -m dsbench        # demo showcase

Documentation

• docs/binary-search-trees.md
• docs/balanced-trees.md
• docs/string-algorithms.md
• docs/graphs.md
• docs/shortest-paths.md
• docs/benchmarking.md
• docs/complexity-cheatsheet.md
• docs/interview-patterns.md
• runnable examples in examples/

Development

Python 3.9+ with numpy. Tests are plain pytest, all deterministic (seeded RNGs), and fast (<2 s on a laptop).

License

MIT - see LICENSE.