← ClaudeAtlas

data-structure-selectionlisted

Choosing data structures from the operation mix: dictionaries and ordered maps, priority queues, sequences, range-query structures, spatial and vector indexes, persistent structures and graph representations, with asymptotic costs, cache and allocation constants, concrete per-language library picks (2026), adversarial-key defences and a benchmark-to-confirm step. Load when picking, reviewing or replacing a container, index or in-memory structure.
rustcircle/c101 · ★ 0 · Data & Documents · score 65
Install: claude install-skill rustcircle/c101
# Data structure selection Pick by operation mix, then by constants, then by availability, then measure. The hub `cs-foundations` section 5 has the short table; storage engines (LSM vs B+tree) stay there. Graph algorithms are in `graph-algorithms`, sketches in `randomized-algorithms-sketches`. ## 1. Selection procedure 1. **List operations** with frequencies, data size, key type and distribution (uniform, Zipf, sequential, adversarial) and latency targets (mean vs p99). 2. **Derive required complexities**: e.g. 10^5 updates/s and 10^3 range queries/s over 10^7 keys rules out O(n) per query. 3. **Shortlist** 2-3 candidates from the tables below. 4. **Compare constants**: a cache miss costs ~100 ns (vs ~1 ns for an L1 hit); one allocation ~20-100 ns plus fragmentation; pointer-chasing structures pay a miss per node, so a B-tree with 16-64 keys per node beats a red-black tree at equal O(log n). 5. **Check availability**: a maintained library beats a hand-rolled structure unless profiling proves otherwise. 6. **Microbenchmark** on realistic sizes and distributions (section 11), then decide. RUM conjecture: of **R**ead cost, **U**pdate cost and **M**emory overhead you can optimise two at the expense of the third (B-tree: reads; LSM: updates; sorted array: memory and reads). Say which two you chose. ## 2. Dictionaries and sets | Structure | Insert | Lookup | Delete | Ordered ops | Notes | |---|---|---|---|---|---| | hash table, chaining | O(1) exp | O(1) exp |