4 ms·
> What would be the difference between a "real vector" and a Map with numeric keys? Access in O(1) instead of O(nlogn).
by malkosta 3y ago
> What would be the difference between a "real vector" and a Map with numeric keys?
Access in O(1) instead of O(nlogn).
- brabel 3y agoData is immutable in Erlang. How do you know the runtime does not optimize Maps with numeric keys into arrays?
- cutler 3y agoData is also immutable in Clojure but it still has vectors.
- KingMob 3y agoYeah, but Clojure vectors are actually trees built to be persistent based on ideas from Bagwell's hash array mapped tries (what Clojure maps are), so they're not technically O(1). Both maps and vectors in Clojure are trees, albeit very shallow trees (32-way branching). The difference lies in the interfaces and the lookup methods. (Maps hash keys and use bits to know which subtree to descend, while vectors use index bits.)
- sb8244 3y agoAnother thing with numeric maps is how insert would work. Swapping elements is trivial, but inserting a new one would require rewriting every subsequent entry.