Hacker News Reader

Comment by brabel | Hacker News Reader

What would be the difference between a "real vector" and a Map with numeric keys?

Maps are hashtables, Vectors are a contiguous area of memory where each element can be access by index referring to a specific address in that memory.

Vectors are usually also homogeneous about the data they hold, because each element should occupy the same fixed amount of memory, such as i*item_size gievs you back the offset of the element i in memory.

Anyway, in Elixir you can use the Erlang's :array module

I'm pretty sure erlangs :array is just a skin over tuple, so it's ~O(1) but not contiguous. might be O(log n) for dynamic arrays. The only truly array datatype in Erlang is :atomics

Erlang tuples are contiguous in memory for primitive values https://blog.edfine.io/blog/2016/06/28/erlang-data-represent...

Array doesn't guarantee to be put into a single tuple. It might be nested.

> What would be the difference between a "real vector" and a Map with numeric keys?

Access in O(1) instead of O(nlogn).

Data is immutable in Erlang. How do you know the runtime does not optimize Maps with numeric keys into arrays?

Data is also immutable in Clojure but it still has vectors.

Yeah, 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.)

Another thing with numeric maps is how insert would work. Swapping elements is trivial, but inserting a new one would require rewriting every subsequent entry.

Reply on news.ycombinator.com