3 ms·

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

by brabel 3y ago

peoplefromibiza 3y ago
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
- throwawaymaths 3y ago
  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
  - davydog187 3y ago
    Erlang tuples are contiguous in memory for primitive values https://blog.edfine.io/blog/2016/06/28/erlang-data-representation/ https://blog.edfine.io/blog/2016/06/28/erlang-data-represent...
    - throwawaymaths 3y ago
      Array doesn't guarantee to be put into a single tuple. It might be nested.
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 ago
  Data is immutable in Erlang. How do you know the runtime does not optimize Maps with numeric keys into arrays?
  - cutler 3y ago
    Data is also immutable in Clojure but it still has vectors.
    - KingMob 3y ago
      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.)
- sb8244 3y ago
  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.

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

by brabel 3y ago

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

throwawaymaths 3y ago
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
- davydog187 3y ago
  Erlang tuples are contiguous in memory for primitive values https://blog.edfine.io/blog/2016/06/28/erlang-data-representation/ https://blog.edfine.io/blog/2016/06/28/erlang-data-represent...
  - throwawaymaths 3y ago
    Array doesn't guarantee to be put into a single tuple. It might be nested.

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 ago
Data is immutable in Erlang. How do you know the runtime does not optimize Maps with numeric keys into arrays?
- cutler 3y ago
  Data is also immutable in Clojure but it still has vectors.
  - KingMob 3y ago
    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.)
sb8244 3y ago
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.