# Vector
A vector for Elixir backed by Erlang's built-in
[array](http://erlang.org/doc/man/array.html), providing fast
random access, implementing [Access](https://hexdocs.pm/elixir/Access.html), [Enumerable](https://hexdocs.pm/elixir/Enumerable.html), [Collectable](https://hexdocs.pm/elixir/Collectable.html), and [Inspect](https://hexdocs.pm/elixir/Inspect.html).
[](https://travis-ci.org/ckampfe/vector)
## Installation
This package is [available on Hex](https://hex.pm/packages/array_vector), and can be installed
by adding `array_vector` to your list of dependencies in `mix.exs`:
```elixir
def deps do
[{:array_vector, "~> 0.2"}]
end
```
## Use
For examples and use, see [the documentation](https://hexdocs.pm/array_vector/Vector.html).
## Development
```elixir
$ mix run benchmark.exs
```
## Rationale
You may want to use this library if:
- you have large, ordered data
- you want to perform lots of random lookups and updates
- you want `Access`, `Collectable`, and `Enumerable`, and `Inspect` semantics
- you'd rather use an immutable collection than `ETS`
Elixir's List and Map are great, but they are targeted at linear access and
random, unordered access, respectively.
Vector is for when you want both ordered operations and sublinear lookup/updates.
## Limitations
From the [array](http://erlang.org/doc/man/array.html) documentation:
```
The representation is not documented and is subject to change without notice.
Notice that arrays cannot be directly compared for equality.
```
As such, any equality comparison will be linear time. I'll probably get around to implementing a `Vector.equals?/2` operation at some point. You can always do `Vector.to_list(x) === Vector.to_list(y)` at the expense of converting the underlying `array` to a `list`.
## Benchmark results
Microbenchmarks are generally trash. This is mostly just to confirm that things are working as expected.
See `benchmark.exs` for details.
```
Operating System: macOS
CPU Information: Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz
Number of Available Cores: 8
Available memory: 17.179869184 GB
Elixir 1.4.5
Erlang 20.0
Benchmark suite executing with the following configuration:
warmup: 5.00 s
time: 10.00 s
parallel: 1
inputs: none specified
Estimated total run time: 15.00 min
Benchmarking list new 1000000...
Benchmarking vector to_list 10000...
Benchmarking vector update 1000000...
Benchmarking list update 1000000...
Benchmarking vector lookup 100000...
Benchmarking vector reverse 10000...
Benchmarking vector lookup 1000000...
Benchmarking vector new from list 1000...
Benchmarking vector map + 1 1000...
Benchmarking vector new raw initialize 1000...
Benchmarking vector new raw initialize 1000000...
Benchmarking list reverse 10000...
Benchmarking list reverse 1000...
Benchmarking vector lookup 10000000...
Benchmarking list lookup 10000...
Benchmarking list map + 1 100000...
Benchmarking list lookup 10000000...
Benchmarking vector update 10000000...
Benchmarking list map + 1 1000000...
Benchmarking vector map + 1 10000000...
Benchmarking vector new from list 100000...
Benchmarking list reverse 1000000...
Benchmarking list map + 1 10000000...
Benchmarking vector new raw initialize 100000...
Benchmarking vector update 10000...
Benchmarking vector lookup 10000...
Benchmarking list reverse 10000000...
Benchmarking vector new from list 10000000...
Benchmarking list lookup 1000000...
Benchmarking vector new from list 1000000...
Benchmarking list new 10000000...
Benchmarking vector new from list 10000...
Benchmarking list lookup 100000...
Benchmarking vector map + 1 1000000...
Benchmarking vector to_list 100000...
Benchmarking vector map + 1 100000...
Benchmarking list update 100000...
Benchmarking vector new raw initialize 10000...
Benchmarking list map + 1 1000...
Benchmarking vector update 100000...
Benchmarking list update 10000000...
Benchmarking vector to_list 10000000...
Benchmarking list new 1000...
Benchmarking list new 10000...
Benchmarking vector map + 1 10000...
Benchmarking vector reverse 1000000...
Benchmarking vector reverse 100000...
Benchmarking list map + 1 10000...
Benchmarking list reverse 100000...
Benchmarking vector to_list 1000000...
Benchmarking list new 100000...
Benchmarking vector reverse 1000...
Benchmarking vector new raw initialize 10000000...
Benchmarking list lookup 1000...
Benchmarking list update 1000...
Benchmarking vector lookup 1000...
Benchmarking vector update 1000...
Benchmarking vector to_list 1000...
Benchmarking list update 10000...
Benchmarking vector reverse 10000000...
Name ips average deviation median
vector lookup 1000 6464726.41 0.155 μs ±274.26% 0.140 μs
vector new raw initialize 1000 5860396.12 0.171 μs ±195.76% 0.160 μs
vector lookup 10000 5466636.03 0.183 μs ±170.40% 0.170 μs
vector new raw initialize 10000 5312765.81 0.188 μs ±175.05% 0.170 μs
vector new raw initialize 100000 4887599.30 0.20 μs ±164.90% 0.190 μs
vector lookup 100000 4500313.00 0.22 μs ±114.90% 0.20 μs
vector new raw initialize 10000000 4193030.45 0.24 μs ±106.02% 0.22 μs
vector lookup 1000000 4034980.36 0.25 μs ±70.77% 0.23 μs
vector new raw initialize 1000000 3837327.86 0.26 μs ±3299.96% 0.20 μs
vector lookup 10000000 3228157.67 0.31 μs ±472.50% 0.28 μs
vector update 1000 2255899.67 0.44 μs ±48.03% 0.41 μs
vector update 10000 1910655.87 0.52 μs ±26.15% 0.48 μs
vector update 100000 1488714.34 0.67 μs ±795.60% 0.60 μs
vector update 1000000 1311684.48 0.76 μs ±70.97% 0.67 μs
vector update 10000000 861867.99 1.16 μs ±7100.42% 1.00 μs
list lookup 1000 538176.92 1.86 μs ±159.90% 1.70 μs
list reverse 1000 327210.85 3.06 μs ±43.49% 2.50 μs
list update 1000 196502.89 5.09 μs ±24.80% 4.70 μs
vector to_list 1000 57372.83 17.43 μs ±79.76% 16.00 μs
vector new from list 1000 40466.37 24.71 μs ±30.47% 23.00 μs
list new 1000 35675.23 28.03 μs ±50.50% 25.00 μs
list reverse 10000 24634.15 40.59 μs ±75.05% 25.00 μs
vector map + 1 1000 18064.10 55.36 μs ±19.92% 53.00 μs
list lookup 10000 15703.65 63.68 μs ±32.76% 59.00 μs
list map + 1 1000 11953.95 83.65 μs ±22.92% 78.00 μs
vector reverse 1000 11173.90 89.49 μs ±21.14% 85.00 μs
list update 10000 6083.59 164.38 μs ±16.87% 160.00 μs
vector to_list 10000 4949.35 202.05 μs ±21.69% 183.00 μs
vector new from list 10000 3404.03 293.77 μs ±36.33% 264.00 μs
list new 10000 3118.23 320.70 μs ±21.48% 311.00 μs
list reverse 100000 2532.00 394.94 μs ±79.38% 232.00 μs
list lookup 100000 1928.03 518.66 μs ±18.65% 476.00 μs
vector map + 1 10000 1583.21 631.63 μs ±22.54% 573.00 μs
list map + 1 10000 1177.98 848.91 μs ±15.72% 834.00 μs
vector reverse 10000 829.62 1205.38 μs ±23.93% 1081.00 μs
list update 100000 650.67 1536.88 μs ±7.08% 1514.00 μs
vector to_list 100000 529.95 1886.97 μs ±14.25% 1995.00 μs
list new 100000 319.84 3126.58 μs ±15.82% 3276.00 μs
vector new from list 100000 254.60 3927.78 μs ±28.77% 3527.00 μs
list lookup 1000000 169.87 5886.73 μs ±14.93% 5439.00 μs
vector map + 1 100000 158.98 6290.27 μs ±12.13% 5924.00 μs
list reverse 1000000 100.69 9931.31 μs ±46.44% 9099.00 μs
list map + 1 100000 88.38 11315.04 μs ±16.46% 11164.50 μs
vector reverse 100000 71.16 14052.05 μs ±15.67% 13752.00 μs
list lookup 10000000 65.54 15257.65 μs ±11.04% 14829.00 μs
list update 1000000 32.93 30370.29 μs ±6.21% 29811.00 μs
vector to_list 1000000 32.03 31224.72 μs ±25.98% 29335.00 μs
vector new from list 1000000 23.83 41962.28 μs ±26.28% 36328.00 μs
list update 10000000 16.47 60719.26 μs ±21.23% 61108.00 μs
list new 1000000 13.97 71566.26 μs ±4.32% 71299.00 μs
vector map + 1 1000000 13.73 72812.56 μs ±12.65% 69022.00 μs
list map + 1 1000000 8.18 122219.85 μs ±12.67% 119922.50 μs
list reverse 10000000 6.64 150527.52 μs ±45.15% 135144.00 μs
vector reverse 1000000 6.55 152588.91 μs ±15.31% 143807.50 μs
vector to_list 10000000 3.54 282089.33 μs ±21.21% 270121.50 μs
list new 10000000 1.80 555152.33 μs ±38.68% 512246.00 μs
vector new from list 10000000 1.71 583588.88 μs ±15.54% 616824.00 μs
vector map + 1 10000000 1.18 848710.67 μs ±14.01% 822347.00 μs
list map + 1 10000000 0.72 1384228.88 μs ±14.75% 1378561.50 μs
vector reverse 10000000 0.57 1740072.50 μs ±9.61% 1773625.00 μs
Comparison:
vector lookup 1000 6464726.41
vector new raw initialize 1000 5860396.12 - 1.10x slower
vector lookup 10000 5466636.03 - 1.18x slower
vector new raw initialize 10000 5312765.81 - 1.22x slower
vector new raw initialize 100000 4887599.30 - 1.32x slower
vector lookup 100000 4500313.00 - 1.44x slower
vector new raw initialize 10000000 4193030.45 - 1.54x slower
vector lookup 1000000 4034980.36 - 1.60x slower
vector new raw initialize 1000000 3837327.86 - 1.68x slower
vector lookup 10000000 3228157.67 - 2.00x slower
vector update 1000 2255899.67 - 2.87x slower
vector update 10000 1910655.87 - 3.38x slower
vector update 100000 1488714.34 - 4.34x slower
vector update 1000000 1311684.48 - 4.93x slower
vector update 10000000 861867.99 - 7.50x slower
list lookup 1000 538176.92 - 12.01x slower
list reverse 1000 327210.85 - 19.76x slower
list update 1000 196502.89 - 32.90x slower
vector to_list 1000 57372.83 - 112.68x slower
vector new from list 1000 40466.37 - 159.76x slower
list new 1000 35675.23 - 181.21x slower
list reverse 10000 24634.15 - 262.43x slower
vector map + 1 1000 18064.10 - 357.88x slower
list lookup 10000 15703.65 - 411.67x slower
list map + 1 1000 11953.95 - 540.80x slower
vector reverse 1000 11173.90 - 578.56x slower
list update 10000 6083.59 - 1062.65x slower
vector to_list 10000 4949.35 - 1306.18x slower
vector new from list 10000 3404.03 - 1899.14x slower
list new 10000 3118.23 - 2073.21x slower
list reverse 100000 2532.00 - 2553.21x slower
list lookup 100000 1928.03 - 3353.03x slower
vector map + 1 10000 1583.21 - 4083.29x slower
list map + 1 10000 1177.98 - 5487.96x slower
vector reverse 10000 829.62 - 7792.43x slower
list update 100000 650.67 - 9935.48x slower
vector to_list 100000 529.95 - 12198.75x slower
list new 100000 319.84 - 20212.50x slower
vector new from list 100000 254.60 - 25392.00x slower
list lookup 1000000 169.87 - 38056.09x slower
vector map + 1 100000 158.98 - 40664.90x slower
list reverse 1000000 100.69 - 64203.19x slower
list map + 1 100000 88.38 - 73148.61x slower
vector reverse 100000 71.16 - 90842.68x slower
list lookup 10000000 65.54 - 98636.52x slower
list update 1000000 32.93 - 196335.65x slower
vector to_list 1000000 32.03 - 201859.25x slower
vector new from list 1000000 23.83 - 271274.66x slower
list update 10000000 16.47 - 392533.43x slower
list new 1000000 13.97 - 462656.32x slower
vector map + 1 1000000 13.73 - 470713.27x slower
list map + 1 1000000 8.18 - 790117.92x slower
list reverse 10000000 6.64 - 973119.20x slower
vector reverse 1000000 6.55 - 986445.55x slower
vector to_list 10000000 3.54 - 1823630.36x slower
list new 10000000 1.80 - 3588907.95x slower
vector new from list 10000000 1.71 - 3772742.46x slower
vector map + 1 10000000 1.18 - 5486682.26x slower
list map + 1 10000000 0.72 - 8948660.97x slower
vector reverse 10000000 0.57 - 11249092.65x slower
```
