Method
cache-friendly
Articles
DS
Data structure
Dynamic array
An array that grows by itself: access by index in O(1), appending to the end in O(1) amortised.
O(1) amortised per append
2 problems
DS
Data structure
B-tree
A tree with hundreds of keys in a page-sized node: a search among a billion keys reads five pages.
O(log n) comparisons, O(log_B n) page reads
2 problems
GRA
Technique
Storing a graph
Matrix, lists, edge list and CSR: memory, speed, and which questions each form answers cheaply.
neighbours of a vertex: O(n) for the matrix, O(deg) for lists and CSR; is there an edge: O(1) for the matrix, O(deg) for lists
2 problems
TEC
Technique
Cache-friendly data
The same algorithm, a different order of memory accesses: tiling, padded rows and laying data out by field.
the same big O
1 problem
Problems
Often together
array 3 classic 3 in production 3 interviews 2 matrix 2 amortized 1 tree 1 search tree 1 databases 1 external memory 1 searching 1 range queries 1