4 ms·
Which data structures do you miss most?
by samth 5y ago
Which data structures do you miss most?
- evdubs 5y agoSorted data structures :) [Balancing] Binary Search Trees as a standard that is available in many languages; B-Trees if memory locality is important; Skip Lists if there is data structure sharing between real threads and something like a Concurrent Balancing Binary Search Tree would have too much lock contention. I have looked over the `data-red-black` library; I wish its interface was richer with `map`, `filter`, retrieving a range of values, partitioning/sliding over key-value pairs, and all the other generic sequence operations that hopefully Rhombus can enable for different underlying data structures.
- soegaard 5y agoSkip Lists: https://docs.racket-lang.org/data/skip-list.html https://docs.racket-lang.org/data/skip-list.html These functional red/black-trees have `map` and `filter`: https://docs.racket-lang.org/functional-data-structures/Red-Black_Trees.html https://docs.racket-lang.org/functional-data-structures/Red-... AVL-trees: https://docs.racket-lang.org/avl/index.html https://docs.racket-lang.org/avl/index.html I would be surprised if someone hasn't made a B-tree implementation already. As bonus: Another red/black-tree implementation (imperative): https://github.com/soegaard/little-helper/blob/master/planet/galore.plt/2/2/private/raw-red-black-tree-set.scm https://github.com/soegaard/little-helper/blob/master/planet...