View Source Aja.Vector (Aja v0.6.4)
Fast persistent vector with efficient appends and random access.
Persistent vectors have been introduced by Clojure as an efficient alternative to lists.
Many operations for Aja.Vector
run in effective constant time (length, random access, appends...),
unlike linked lists for which most operations run in linear time.
Functions that need to go through the whole collection like map/2
or foldl/3
are as often fast as
their list equivalents, or sometimes even slightly faster.
Vectors also use less memory than lists for "big" collections (see the Memory usage section).
Make sure to read the Efficiency guide section to get the best performance out of vectors.
Erlang's :array
module offer similar functionalities.
However Aja.Vector
:
- is a better Elixir citizen: pipe-friendliness,
Access
behaviour,Enum
/Inspect
/Collectable
protocols - is heavily optimized and should offer higher performance in most use cases, especially "loops" like
map/2
/to_list/1
/foldl/3
- mirrors most of the
Enum
module API (together withAja.Enum
) with highly optimized versions for vectors (Aja.Enum.join/1
,Aja.Enum.sum/1
,Aja.Enum.random/1
...) - supports negative indexing (e.g.
-1
corresponds to the last element) - optionally implements the
Jason.Encoder
protocol ifJason
is installed
Note: most of the design is inspired by
this series of blog posts describing
the Clojure implementation, but a branching factor of 16 = 2 ^ 4
has been picked instead of 32 = 2 ^ 5
.
This choice was made following performance benchmarking that showed better overall performance
for this particular implementation.
Examples
iex> vector = Aja.Vector.new(1..10)
vec([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
iex> Aja.Vector.append(vector, :foo)
vec([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, :foo])
iex> vector[3]
4
iex> Aja.Vector.replace_at(vector, -1, :bar)
vec([1, 2, 3, 4, 5, 6, 7, 8, 9, :bar])
iex> 3 in vector
true
Access behaviour
Aja.Vector
implements the Access
behaviour.
iex> vector = Aja.Vector.new(1..10)
iex> vector[3]
4
iex> put_in(vector[5], :foo)
vec([1, 2, 3, 4, 5, :foo, 7, 8, 9, 10])
iex> {9, updated} = pop_in(vector[8]); updated
vec([1, 2, 3, 4, 5, 6, 7, 8, 10])
Convenience vec/1
and vec_size/1
macros
The Aja.Vector
module can be used without any macro.
The Aja.vec/1
macro does however provide some syntactic sugar to make
it more convenient to work with vectors of known size, namely:
- pattern match on elements for vectors of known size
- construct new vectors of known size faster, by generating the AST at compile time
Examples:
iex> import Aja
iex> vec([1, 2, 3])
vec([1, 2, 3])
iex> vec([1, 2, var, _, _, _]) = Aja.Vector.new(1..6); var
3
iex> vec(first ||| last) = Aja.Vector.new(0..99_999); {first, last}
{0, 99999}
The Aja.vec_size/1
macro can be used in guards:
iex> import Aja
iex> match?(v when vec_size(v) > 99, Aja.Vector.new(1..100))
true
Convenience +++/2
operator
The Aja.+++/2
operator can make appending to a vector more compact by aliasing Aja.Vector.concat/2
:
iex> import Aja
iex> vec([1, 2, 3]) +++ vec([4, 5])
vec([1, 2, 3, 4, 5])
Pattern-matching and opaque type
An Aja.Vector
is represented internally using the %Aja.Vector{}
struct. This struct
can be used whenever there's a need to pattern match on something being an Aja.Vector
:
iex> match?(%Aja.Vector{}, Aja.Vector.new())
true
Note, however, that Aja.Vector
should be considered an opaque type: its struct internal fields
must not be accessed directly (even if not enforced by dialyzer because of pattern-matching).
As discussed in the previous section, vec/1
makes it
possible to pattern match on size and elements as well as checking the type.
Memory usage
Vectors have a small overhead over lists for smaller collections, but are using far less memory for bigger collections:
iex> memory_for = fn n -> [Enum.to_list(1..n), Aja.Vector.new(1..n)] |> Enum.map(&:erts_debug.size/1) end
iex> memory_for.(1)
[2, 32]
iex> memory_for.(10)
[20, 32]
iex> memory_for.(100)
[200, 151]
iex> memory_for.(10_000)
[20000, 11371]
If you need to work with vectors containing mostly the same value, Aja.Vector.duplicate/2
is highly efficient both in time and memory (logarithmic).
It minimizes the number of actual copies and reuses the same nested structures under the hood:
iex> Aja.Vector.duplicate(0, 10_000) |> :erts_debug.size()
117
iex> Aja.Vector.duplicate(0, 10_000) |> :erts_debug.flat_size() # when shared over processes / ETS
11371
Even a 1B x 1B matrix of the same element costs virtually nothing!
big_n = 1_000_000_000
0 |> Aja.Vector.duplicate(big_n) |> Aja.Vector.duplicate(big_n) |> :erts_debug.size()
539
Efficiency guide
If you are using vectors and not lists, chances are that you care about performance. Here are a couple notes about how to use vectors in an optimal way. Most functions from this module are highly efficient, those that are not will indicate it in their documentation.
But remember the golden rule: in case of doubt, always benchmark.
Avoid prepending
Appending is very efficient, but prepending is highly inefficient since the whole array needs to be reconstructed.
DON'T
Aja.Vector.prepend(vector, :foo)
DO
[:foo | list] # use lists
Aja.Vector.append(vector, :foo)
Avoid deletions
This implementation of persistent vectors has many advantages, but it does
not support efficient deletion, with the exception of the last element that
can be popped very efficiently (Aja.Vector.pop_last/1
, Aja.Vector.delete_last/1
).
Deleting close to the end of the vector using Aja.Vector.delete_at/2
or
Aja.Vector.pop_at/3
is still fairly fast, but deleting near the beginning needs
to reconstruct most of the vector.
If you need to be able to delete arbitrary indexes, chances are you should consider
an alternative data structure.
Another possibility could be to use sparse arrays, defining nil
as a deleted value
(but then the indexing and size won't reflect this).
DON'T
Aja.Vector.pop_at(vector, 3)
Aja.Vector.delete_at(vector, 3)
pop_in(vector[3])
DO
Aja.Vector.pop_last(vector)
Aja.Vector.delete_last(vector)
Aja.Vector.delete_at(vector, -3) # close to the end
Aja.Vector.replace_at(vector, 3, nil)
Successive appends
If you just need to append all elements of an enumerable, it is more efficient to use
Aja.Vector.concat/2
or its alias Aja.+++/2
than successive calls to Aja.Vector.append/2
:
DON'T
Enum.reduce(enumerable, vector, fn val, acc -> Aja.Vector.append(acc, val) end)
DO
Aja.Vector.concat(vector, enumerable)
vector +++ enumerable
Prefer Aja.Enum
and Aja.Vector
to Enum
for vectors
The Aja.Enum
module reimplements (nearly) all functions from the Enum
module to offer
optimal performance when operating on vectors, and should be used over Enum
functions whenever possible
(even if Aja.Vector
implements the Enumerable
and Collectable
protocols for convienience):
DON'T
Enum.sum(vector)
Enum.to_list(vector)
Enum.reduce(vector, [], fun)
Enum.into(enumerable, %Aja.Vector.new())
Enum.into(enumerable, vector)
DO
Aja.Enum.sum(vector)
Aja.Enum.to_list(vector) # or Aja.Vector.to_list(vector)
Aja.Enum.reduce(vector, [], fun) # or Aja.Vector.foldl(vector, [], fun)
Aja.Vector.new(enumerable)
Aja.Enum.into(enumerable, vector)
# or Aja.Vector.concat(vector, enumerable)
# or vector +++ enumerable
Although it depends on the function, you can expect a ~10x speed difference.
for
comprehensions are actually using Enumerable
as well, so
the same advice holds:
DON'T
for value <- vector do
do_stuff()
end
If using it in EEx templates, you might want to cast it to a list:
for value <- Aja.Vector.to_list(vector) do
do_stuff()
end
Exceptions: Enum
optimized functions
Enum.member?/2
is implemented in an efficient way, so in/2
is optimal:
DO
33 in vector
Slicing optimization
Slicing any subset on the left on the vector using methods from Aja.Vector
is
extremely efficient as the vector internals can be reused:
DO
Aja.Vector.take(vector, 10) # take a positive amount
Aja.Vector.drop(vector, -20) # drop a negative amount
Aja.Vector.slice(vector, 0, 10) # slicing from 0
Aja.Vector.slice(vector, 0..-5) # slicing from 0
Aja.Vector
and Aja.Enum
Aja.Enum
mirrorsEnum
and should return identical results, therefore many functions would return listsAja.Vector
mirrorsEnum
functions that are returning lists, but returns vectors insteadiex> vector = Aja.Vector.new(1..5) iex> Aja.Enum.reverse(vector) [5, 4, 3, 2, 1] iex> Aja.Vector.reverse(vector) vec([5, 4, 3, 2, 1]) iex> Aja.Enum.map(vector, & (&1 * 7)) [7, 14, 21, 28, 35] iex> Aja.Vector.map(vector, & (&1 * 7)) vec([7, 14, 21, 28, 35])
Additional notes
If you need to work with vectors containing mostly the same value, use
Aja.Vector.duplicate/2
(more details in the Memory usage section).If you work with functions returning vectors of known size, you can use the
Aja.vec/1
macro to defer the generation of the AST for the internal structure to compile time instead of runtime.Aja.Vector.new([%{foo: a}, %{foo: b}]) # structure created at runtime vec([%{foo: a}, %{foo: b}]) # structure AST defined at compile time
Summary
Functions
Appends a value
at the end of a vector
.
Finds the element at the given index
(zero-based).
Finds the element at the given index
(zero-based).
Appends all values from an enumerable
at the end of a vector
.
Returns a copy of the vector
where all consecutive duplicated elements are collapsed to a single element.
Returns a copy of the vector
where all consecutive duplicated elements are collapsed to a single element.
(Inefficient) Returns a copy of vector
without the value at the specified index
.
(Inefficient) Returns a copy of vector
without the value at the specified index
.
Removes the last value from the vector
and returns the updated vector.
Removes the last value from the vector
and returns the updated vector.
Drops the amount of elements from the vector
.
Drops elements at the beginning of the vector
while fun
returns a truthy value.
Duplicates the given element n
times in a vector.
Finds the element at the given index
(zero-based), and returns it in a ok-entry.
If the index
does not exist, returns :error
.
Filters the vector
, i.e. return a new vector containing only elements
for which fun
returns a truthy (neither false
nor nil
) value.
Returns the first element in the vector
or default
if vector
is empty.
Maps the given fun
over vector
and flattens the result.
Folds (reduces) the given vector
from the left with the function fun
.
Requires an accumulator acc
.
Folds (reduces) the given vector
from the right with the function fun
.
Requires an accumulator acc
.
Gets the value from key and updates it, all in one pass.
Intersperses separator
between each element of the vector
.
Returns the last element in the vector
or default
if vector
is empty.
Returns a new vector where each element is the result of invoking fun
on each corresponding element of vector
.
Maps and intersperses the vector
in one pass.
Invokes the given fun
to each element in the vector
to reduce
it to a single element, while keeping an accumulator.
Returns a new empty vector.
Creates a vector from an enumerable
.
Creates a vector from an enumerable
via the given transform
function.
(Inefficient) Returns and removes the value at the specified index
in the vector
.
(Inefficient) Returns and removes the value at the specified index
in the vector
.
Removes the last value from the vector
and returns both the value and the updated vector.
Removes the last value from the vector
and returns both the value and the updated vector.
(Inefficient) Prepends value
at the beginning of the vector
.
Filters the vector
, i.e. return a new vector containing only elements
for which fun
returns a falsy (either false
or nil
) value.
Populates a vector of size n
by calling generator_fun
repeatedly.
Returns a copy of vector
with a replaced value
at the specified index
.
Returns a copy of vector
with a replaced value
at the specified index
.
Returns the vector
in reverse order.
Returns the vector
in reverse order, and concatenates the tail
(enumerable).
Applies the given function to each element in the vector
, storing the result
in a vector and passing it as the accumulator for the next computation.
Applies the given function to each element in the vector
, storing the result
in a vector and passing it as the accumulator for the next computation.
Returns a new vector with the elements of vector
shuffled.
Returns the number of elements in vector
.
Returns a subset of the given vector
by index_range
.
Returns a subset of the given vector
, from start_index
(zero-based)
with amount number
of elements if available.
Sorts the vector
in the same way as Enum.sort/1
.
Sorts the vector
in the same way as Enum.sort/2
.
Sorts the vector
in the same way as Enum.sort_by/3
.
Splits the vector
into two vectors, leaving amount
elements in the first one.
Splits vector
in two at the position of the element for which fun
returns a falsy value
(false
or nil
) for the first time.
Splits the vector
in two vectors according to the given function fun
.
Takes an amount
of elements from the beginning or the end of the vector
.
Takes amount
random elements from vector
.
Takes the elements from the beginning of the vector
while fun
returns a truthy value.
Converts the vector
to a list.
Returns a copy of the vector without any duplicated element.
Returns a copy of the vector without elements for which the function fun
returned duplicate elements.
Opposite of zip/2
. Extracts two-element tuples from the given vector
and groups them together.
Returns a copy of vector
with an updated value at the specified index
.
Returns a copy of vector
with an updated value at the specified index
.
Returns the vector
with each element wrapped in a tuple alongside its index.
Zips corresponding elements from two vectors into one vector of tuples.
Zips corresponding elements from two vectors into a new vector,
transforming them with the zip_fun
function as it goes.
Types
@type index() :: integer()
@type t(value) :: internals(value)
The type of an Aja.Vector
with elements of the type value
.
It should be considered opaque even though it isn't enforced by dialyzer to enable pattern-matching.
@type value() :: term()
Functions
Appends a value
at the end of a vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new() |> Aja.Vector.append(:foo)
vec([:foo])
iex> Aja.Vector.new(1..5) |> Aja.Vector.append(:foo)
vec([1, 2, 3, 4, 5, :foo])
Finds the element at the given index
(zero-based).
Returns default
if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.at(555)
556
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.at(1_000)
nil
Finds the element at the given index
(zero-based).
Raises an Aja.Vector.IndexError
if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.at!(555)
556
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.at!(-10)
991
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.at!(1_000)
** (Aja.Vector.IndexError) out of bound index: 1000 not in -1000..999
@spec concat(t(val), Enumerable.t()) :: t(val) when val: value()
Appends all values from an enumerable
at the end of a vector
.
Runs in effective linear time in respect with the length of enumerable
,
disregarding the size of the vector
.
Examples
iex> Aja.Vector.new(1..5) |> Aja.Vector.concat(10..15)
vec([1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15])
iex> Aja.Vector.new() |> Aja.Vector.concat(10..15)
vec([10, 11, 12, 13, 14, 15])
Returns a copy of the vector
where all consecutive duplicated elements are collapsed to a single element.
Elements are compared using ===/2
.
If you want to remove all duplicated elements, regardless of order, see uniq/1
.
Examples
iex> Aja.Vector.new([1, 2, 3, 3, 2, 1]) |> Aja.Vector.dedup()
vec([1, 2, 3, 2, 1])
iex> Aja.Vector.new([1, 1, 2, 2.0, :three, :three]) |> Aja.Vector.dedup()
vec([1, 2, 2.0, :three])
Returns a copy of the vector
where all consecutive duplicated elements are collapsed to a single element.
The function fun
maps every element to a term which is used to determine if two elements are duplicates.
Examples
iex> vector = Aja.Vector.new([{1, :a}, {2, :b}, {2, :c}, {1, :a}])
iex> Aja.Vector.dedup_by(vector, fn {x, _} -> x end)
vec([{1, :a}, {2, :b}, {1, :a}])
iex> vector = Aja.Vector.new([5, 1, 2, 3, 2, 1])
iex> Aja.Vector.dedup_by(vector, fn x -> x > 2 end)
vec([5, 1, 3, 2])
(Inefficient) Returns a copy of vector
without the value at the specified index
.
Returns the vector
untouched if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in linear time. Its usage is discouraged, see the Efficiency guide.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> Aja.Vector.delete_at(vector, 4)
vec([1, 2, 3, 4, 6, 7, 8])
iex> Aja.Vector.delete_at(vector, -9)
vec([1, 2, 3, 4, 5, 6, 7, 8])
(Inefficient) Returns a copy of vector
without the value at the specified index
.
Raises an Aja.Vector.IndexError
if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in linear time. Its usage is discouraged, see the Efficiency guide.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> Aja.Vector.delete_at!(vector, 4)
vec([1, 2, 3, 4, 6, 7, 8])
iex> Aja.Vector.delete_at!(vector, -9)
** (Aja.Vector.IndexError) out of bound index: -9 not in -8..7
Removes the last value from the vector
and returns the updated vector.
Leaves the vector
untouched if empty.
Runs in effective constant time.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> Aja.Vector.delete_last(vector)
vec([1, 2, 3, 4, 5, 6, 7])
iex> Aja.Vector.delete_last(Aja.Vector.new())
vec([])
Removes the last value from the vector
and returns the updated vector.
Raises an Aja.Vector.EmptyError
if empty.
Runs in effective constant time.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> Aja.Vector.delete_last!(vector)
vec([1, 2, 3, 4, 5, 6, 7])
iex> Aja.Vector.delete_last!(Aja.Vector.new())
** (Aja.Vector.EmptyError) empty vector error
Drops the amount of elements from the vector
.
If a negative amount
is given, the amount of last values will be dropped.
Time complexity is:
- linear when
amount
is positive, as the vector needs to be reconstructed. - effective constant time when
amount
is negative, as the vector structure can be shared
Examples
iex> Aja.Vector.new(0..15) |> Aja.Vector.drop(10)
vec([10, 11, 12, 13, 14, 15])
iex> Aja.Vector.new(0..5) |> Aja.Vector.drop(0)
vec([0, 1, 2, 3, 4, 5])
iex> Aja.Vector.new(0..10) |> Aja.Vector.drop(-5)
vec([0, 1, 2, 3, 4, 5])
@spec drop_while(t(val), (val -> as_boolean(term()))) :: t(val) when val: value()
Drops elements at the beginning of the vector
while fun
returns a truthy value.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..10) |> Aja.Vector.drop_while(fn x -> x < 7 end)
vec([7, 8, 9, 10])
iex> Aja.Vector.new([1, true, %{}, nil, "abc"]) |> Aja.Vector.drop_while(fn x -> x end)
vec([nil, "abc"])
@spec duplicate(val, non_neg_integer()) :: t(val) when val: value()
Duplicates the given element n
times in a vector.
n
is an integer greater than or equal to 0
.
If n
is 0
, an empty list is returned.
Runs in logarithmic time regarding n
. It is very fast and memory efficient
(see Memory usage).
Examples
iex> Aja.Vector.duplicate(nil, 10)
vec([nil, nil, nil, nil, nil, nil, nil, nil, nil, nil])
iex> Aja.Vector.duplicate(:foo, 0)
vec([])
Finds the element at the given index
(zero-based), and returns it in a ok-entry.
If the index
does not exist, returns :error
.
Supports negative indexing from the end of the vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.fetch(555)
{:ok, 556}
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.fetch(1_000)
:error
iex> Aja.Vector.new(1..1_000) |> Aja.Vector.fetch(-1)
{:ok, 1000}
See Aja.Vector.at!/2
.
@spec filter(t(val), (val -> as_boolean(term()))) :: t(val) when val: value()
Filters the vector
, i.e. return a new vector containing only elements
for which fun
returns a truthy (neither false
nor nil
) value.
Runs in linear time.
Examples
iex> vector = Aja.Vector.new(1..100)
iex> Aja.Vector.filter(vector, fn i -> rem(i, 13) == 0 end)
vec([13, 26, 39, 52, 65, 78, 91])
Returns the first element in the vector
or default
if vector
is empty.
Runs in actual constant time.
Examples
iex> Aja.Vector.new(1..10_000) |> Aja.Vector.first()
1
iex> Aja.Vector.new() |> Aja.Vector.first()
nil
@spec flat_map(t(val), (val -> t(mapped_val))) :: t(mapped_val) when val: value(), mapped_val: value()
Maps the given fun
over vector
and flattens the result.
This function returns a new vector built by concatenating the results
of invoking fun
on each element of vector
together.
Runs in linear time.
Examples
iex> Aja.Vector.new(0..4) |> Aja.Vector.flat_map(fn i -> List.duplicate(i, i) end)
vec([1, 2, 2, 3, 3, 3, 4, 4, 4, 4])
Folds (reduces) the given vector
from the left with the function fun
.
Requires an accumulator acc
.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..10) |> Aja.Vector.foldl(0, &+/2)
55
iex> Aja.Vector.new(1..10) |> Aja.Vector.foldl([], & [&1 | &2])
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Folds (reduces) the given vector
from the right with the function fun
.
Requires an accumulator acc
.
Unlike linked lists, this is as efficient as foldl/3
. This can typically save a call
to Enum.reverse/1
on the result when building a list.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..10) |> Aja.Vector.foldr(0, &+/2)
55
iex> Aja.Vector.new(1..10) |> Aja.Vector.foldr([], & [&1 | &2])
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
@spec get_and_update(t(v), index(), (v -> {returned, v} | :pop)) :: {returned, t(v)} when v: value(), returned: term()
Gets the value from key and updates it, all in one pass.
See Access.get_and_update/3
for more details.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> {6, updated} = Aja.Vector.get_and_update(vector, 5, fn current_value ->
...> {current_value, current_value && current_value * 100}
...> end); updated
vec([1, 2, 3, 4, 5, 600, 7, 8])
iex> {nil, updated} = Aja.Vector.get_and_update(vector, 8, fn current_value ->
...> {current_value, current_value && current_value * 100}
...> end); updated
vec([1, 2, 3, 4, 5, 6, 7, 8])
iex> {4, updated} = Aja.Vector.get_and_update(vector, 3, fn _ -> :pop end); updated
vec([1, 2, 3, 5, 6, 7, 8])
iex> {nil, updated} = Aja.Vector.get_and_update(vector, 8, fn _ -> :pop end); updated
vec([1, 2, 3, 4, 5, 6, 7, 8])
Intersperses separator
between each element of the vector
.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..6) |> Aja.Vector.intersperse(nil)
vec([1, nil, 2, nil, 3, nil, 4, nil, 5, nil, 6])
Returns the last element in the vector
or default
if vector
is empty.
Runs in constant time (actual, not effective).
Examples
iex> Aja.Vector.new(1..10_000) |> Aja.Vector.last()
10_000
iex> Aja.Vector.new() |> Aja.Vector.last()
nil
Returns a new vector where each element is the result of invoking fun
on each corresponding element of vector
.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..10) |> Aja.Vector.map(&(&1 * &1))
vec([1, 4, 9, 16, 25, 36, 49, 64, 81, 100])
@spec map_intersperse( t(val), separator, (val -> mapped_val) ) :: t(mapped_val | separator) when val: value(), separator: value(), mapped_val: value()
Maps and intersperses the vector
in one pass.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..6) |> Aja.Vector.map_intersperse(nil, &(&1 * 10))
vec([10, nil, 20, nil, 30, nil, 40, nil, 50, nil, 60])
@spec map_reduce(t(val), acc, (val, acc -> {mapped_val, acc})) :: {t(mapped_val), acc} when val: value(), mapped_val: value(), acc: any()
Invokes the given fun
to each element in the vector
to reduce
it to a single element, while keeping an accumulator.
Returns a tuple where the first element is the mapped vector and the second one is the final accumulator.
The function, fun
, receives two arguments: the first one is the
element, and the second one is the accumulator. fun
must return
a tuple with two elements in the form of {result, accumulator}
.
Examples
iex> vector = Aja.Vector.new([1, 2, 3])
iex> {new_vec, 6} = Aja.Vector.map_reduce(vector, 0, fn x, acc -> {x * 2, x + acc} end)
iex> new_vec
vec([2, 4, 6])
For example, if with_index/2
was not implemented, you could implement it as follows:
iex> vector = Aja.Vector.new([1, 2, 3])
iex> Aja.Vector.map_reduce(vector, 0, fn x, i -> {{x, i}, i + 1} end) |> elem(0)
vec([{1, 0}, {2, 1}, {3, 2}])
@spec new() :: t()
Returns a new empty vector.
Examples
iex> Aja.Vector.new()
vec([])
@spec new(Enumerable.t()) :: t()
Creates a vector from an enumerable
.
Runs in linear time.
Examples
iex> Aja.Vector.new(10..25)
vec([10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25])
@spec new(Enumerable.t(), (v1 -> v2)) :: t(v2) when v1: value(), v2: value()
Creates a vector from an enumerable
via the given transform
function.
Examples
iex> Aja.Vector.new(1..10, &(&1 * &1))
vec([1, 4, 9, 16, 25, 36, 49, 64, 81, 100])
@spec pop_at(t(val), index(), default) :: {val | default, t(val)} when val: value(), default: term()
(Inefficient) Returns and removes the value at the specified index
in the vector
.
Returns the vector
untouched if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in linear time. Its usage is discouraged, see the Efficiency guide.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> {5, updated} = Aja.Vector.pop_at(vector, 4); updated
vec([1, 2, 3, 4, 6, 7, 8])
iex> {nil, updated} = Aja.Vector.pop_at(vector, -9); updated
vec([1, 2, 3, 4, 5, 6, 7, 8])
(Inefficient) Returns and removes the value at the specified index
in the vector
.
Raises an Aja.Vector.IndexError
if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in linear time. Its usage is discouraged, see the Efficiency guide.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> {5, updated} = Aja.Vector.pop_at!(vector, 4); updated
vec([1, 2, 3, 4, 6, 7, 8])
iex> Aja.Vector.pop_at!(vector, -9)
** (Aja.Vector.IndexError) out of bound index: -9 not in -8..7
Removes the last value from the vector
and returns both the value and the updated vector.
Leaves the vector
untouched if empty.
Runs in effective constant time.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> {8, updated} = Aja.Vector.pop_last(vector); updated
vec([1, 2, 3, 4, 5, 6, 7])
iex> {nil, updated} = Aja.Vector.pop_last(Aja.Vector.new()); updated
vec([])
Removes the last value from the vector
and returns both the value and the updated vector.
Raises an Aja.Vector.EmptyError
if empty.
Runs in effective constant time.
Examples
iex> vector = Aja.Vector.new(1..8)
iex> {8, updated} = Aja.Vector.pop_last!(vector); updated
vec([1, 2, 3, 4, 5, 6, 7])
iex> {nil, updated} = Aja.Vector.pop_last!(Aja.Vector.new()); updated
** (Aja.Vector.EmptyError) empty vector error
(Inefficient) Prepends value
at the beginning of the vector
.
Runs in linear time because the whole vector needs to be reconstructuded, and should be avoided.
Examples
iex> Aja.Vector.new() |> Aja.Vector.prepend(:foo)
vec([:foo])
iex> Aja.Vector.new(1..5) |> Aja.Vector.prepend(:foo)
vec([:foo, 1, 2, 3, 4, 5])
@spec reject(t(val), (val -> as_boolean(term()))) :: t(val) when val: value()
Filters the vector
, i.e. return a new vector containing only elements
for which fun
returns a falsy (either false
or nil
) value.
Runs in linear time.
Examples
iex> vector = Aja.Vector.new(1..12)
iex> Aja.Vector.reject(vector, fn i -> rem(i, 3) == 0 end)
vec([1, 2, 4, 5, 7, 8, 10, 11])
Populates a vector of size n
by calling generator_fun
repeatedly.
Examples
# Although not necessary, let's seed the random algorithm
iex> :rand.seed(:exrop, {1, 2, 3})
iex> Aja.Vector.repeat(&:rand.uniform/0, 3)
vec([0.7498295129076106, 0.06161655489244533, 0.7924073127680873])
Returns a copy of vector
with a replaced value
at the specified index
.
Returns the vector
untouched if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new(1..8) |> Aja.Vector.replace_at(5, :foo)
vec([1, 2, 3, 4, 5, :foo, 7, 8])
iex> Aja.Vector.new(1..8) |> Aja.Vector.replace_at(8, :foo)
vec([1, 2, 3, 4, 5, 6, 7, 8])
iex> Aja.Vector.new(1..8) |> Aja.Vector.replace_at(-2, :foo)
vec([1, 2, 3, 4, 5, 6, :foo, 8])
Returns a copy of vector
with a replaced value
at the specified index
.
Raises an Aja.Vector.IndexError
if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new(1..8) |> Aja.Vector.replace_at!(5, :foo)
vec([1, 2, 3, 4, 5, :foo, 7, 8])
iex> Aja.Vector.new(1..8) |> Aja.Vector.replace_at!(-2, :foo)
vec([1, 2, 3, 4, 5, 6, :foo, 8])
iex> Aja.Vector.new(1..8) |> Aja.Vector.replace_at!(8, :foo)
** (Aja.Vector.IndexError) out of bound index: 8 not in -8..7
Returns the vector
in reverse order.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..12) |> Aja.Vector.reverse()
vec([12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
@spec reverse(t(val), Enumerable.t()) :: t(val) when val: value()
Returns the vector
in reverse order, and concatenates the tail
(enumerable).
Runs in linear time.
Examples
iex> Aja.Vector.new(1..5) |> Aja.Vector.reverse(100..105)
vec([5, 4, 3, 2, 1, 100, 101, 102, 103, 104, 105])
Applies the given function to each element in the vector
, storing the result
in a vector and passing it as the accumulator for the next computation.
Uses the first element in the vector
as the starting value.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..10) |> Aja.Vector.scan(&+/2)
vec([1, 3, 6, 10, 15, 21, 28, 36, 45, 55])
Applies the given function to each element in the vector
, storing the result
in a vector and passing it as the accumulator for the next computation.
Uses the given acc
as the starting value.
Runs in linear time.
Examples
iex> Aja.Vector.new(1..10) |> Aja.Vector.scan(100, &+/2)
vec([101, 103, 106, 110, 115, 121, 128, 136, 145, 155])
Returns a new vector with the elements of vector
shuffled.
See Enum.shuffle/1
for notes on implementation and random seed.
Examples
# Although not necessary, let's seed the random algorithm
iex> :rand.seed(:exrop, {1, 2, 3})
iex> Aja.Vector.new([1, 2, 3]) |> Aja.Vector.shuffle()
vec([3, 1, 2])
iex> Aja.Vector.new([1, 2, 3]) |> Aja.Vector.shuffle()
vec([1, 3, 2])
@spec size(t()) :: non_neg_integer()
Returns the number of elements in vector
.
Runs in constant time.
Examples
iex> Aja.Vector.new(10_000..20_000) |> Aja.Vector.size()
10001
iex> Aja.Vector.new() |> Aja.Vector.size()
0
Returns a subset of the given vector
by index_range
.
Works the same as Enum.slice/2
, see its documentation for more details.
Runs in linear time regarding the size of the returned subset.
Examples
iex> Aja.Vector.new(0..100) |> Aja.Vector.slice(80..90)
vec([80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90])
iex> Aja.Vector.new(0..100) |> Aja.Vector.slice(-40..-30//1)
vec([61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71])
iex> Aja.Vector.new([:only_one]) |> Aja.Vector.slice(0..1000)
vec([:only_one])
@spec slice(t(val), index(), non_neg_integer()) :: t(val) when val: value()
Returns a subset of the given vector
, from start_index
(zero-based)
with amount number
of elements if available.
Works the same as Enum.slice/3
, see its documentation for more details.
Runs in linear time regarding the size of the returned subset.
Examples
iex> Aja.Vector.new(0..100) |> Aja.Vector.slice(80, 10)
vec([80, 81, 82, 83, 84, 85, 86, 87, 88, 89])
iex> Aja.Vector.new(0..100) |> Aja.Vector.slice(-40, 10)
vec([61, 62, 63, 64, 65, 66, 67, 68, 69, 70])
iex> Aja.Vector.new([:only_one]) |> Aja.Vector.slice(0, 1000)
vec([:only_one])
Sorts the vector
in the same way as Enum.sort/1
.
Examples
iex> Aja.Vector.new(9..1) |> Aja.Vector.sort()
vec([1, 2, 3, 4, 5, 6, 7, 8, 9])
@spec sort( t(val), (val, val -> boolean()) | :asc | :desc | module() | {:asc | :desc, module()} ) :: t(val) when val: value()
Sorts the vector
in the same way as Enum.sort/2
.
See Enum.sort/2
documentation for detailled usage.
Examples
iex> Aja.Vector.new(1..9) |> Aja.Vector.sort(:desc)
vec([9, 8, 7, 6, 5, 4, 3, 2, 1])
@spec sort_by( t(val), (val -> mapped_val), (val, val -> boolean()) | :asc | :desc | module() | {:asc | :desc, module()} ) :: t(val) when val: value(), mapped_val: value()
Sorts the vector
in the same way as Enum.sort_by/3
.
See Enum.sort_by/3
documentation for detailled usage.
Examples
iex> vector = Aja.Vector.new(["some", "kind", "of", "monster"])
iex> Aja.Vector.sort_by(vector, &byte_size/1)
vec(["of", "some", "kind", "monster"])
iex> Aja.Vector.sort_by(vector, &{byte_size(&1), String.first(&1)})
vec(["of", "kind", "some", "monster"])
Splits the vector
into two vectors, leaving amount
elements in the first one.
If amount
is a negative number, it starts counting from the back to the beginning of the vector
.
Runs in linear time.
Examples
iex> vector = Aja.Vector.new([1, 2, 3])
iex> Aja.Vector.split(vector, 2) |> inspect()
"{vec([1, 2]), vec([3])}"
iex> Aja.Vector.split(vector, 10) |> inspect()
"{vec([1, 2, 3]), vec([])}"
iex> Aja.Vector.split(vector, 0) |> inspect()
"{vec([]), vec([1, 2, 3])}"
iex> Aja.Vector.split(vector, -1) |> inspect()
"{vec([1, 2]), vec([3])}"
iex> Aja.Vector.split(vector, -5) |> inspect()
"{vec([]), vec([1, 2, 3])}"
Splits vector
in two at the position of the element for which fun
returns a falsy value
(false
or nil
) for the first time.
It returns a two-element tuple with two vectors of elements. The element that triggered the split is part of the second vector.
Is basically performing take_while/2
and drop_while/2
at once.
Runs in linear time.
Examples
iex> {taken, dropped} = Aja.Vector.new(1..10) |> Aja.Vector.split_while(fn x -> x < 7 end)
iex> taken
vec([1, 2, 3, 4, 5, 6])
iex> dropped
vec([7, 8, 9, 10])
Splits the vector
in two vectors according to the given function fun
.
Returns a tuple with the first vector containing all the elements in vector
for which applying fun
returned a truthy value, and a second vector with all
the elements for which applying fun
returned a falsy value (false
or nil
).
Returns the same result as filter/2
and reject/2
at once, but only walks the
vector
once and calls fun
exactly once per element.
Runs in linear time.
Examples
iex> vector = Aja.Vector.new(1..12)
iex> {filtered, rejected} = Aja.Vector.split_with(vector, fn i -> rem(i, 3) == 0 end)
iex> filtered
vec([3, 6, 9, 12])
iex> rejected
vec([1, 2, 4, 5, 7, 8, 10, 11])
Takes an amount
of elements from the beginning or the end of the vector
.
If a positive amount
is given, it takes the amount elements from the beginning of the vector
.
If a negative amount
is given, the amount of elements will be taken from the end.
If amount is 0, it returns the empty vector.
Time complexity is:
- effective constant time when
amount
is positive, as the vector structure can be shared - linear when
amount
is negative, as the vector needs to be reconstructed.
Examples
iex> Aja.Vector.new(0..100) |> Aja.Vector.take(10)
vec([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
iex> Aja.Vector.new([:only_one]) |> Aja.Vector.take(1000)
vec([:only_one])
iex> Aja.Vector.new(0..10) |> Aja.Vector.take(-5)
vec([6, 7, 8, 9, 10])
@spec take_random(t(val), non_neg_integer()) :: t(val) when val: value()
Takes amount
random elements from vector
.
Note that, unless amount
is 0
or 1
, this function will
traverse the whole vector
to get the random sub-vector.
If amount
is more than the vector
size, this is equivalent to shuffling the vector
:
the returned vector cannot be bigger than the original one.
See Enum.random/1
for notes on implementation and random seed.
Runs in linear time (except for amount <= 1
, which is effective constant time).
Examples
# Although not necessary, let's seed the random algorithm
iex> :rand.seed(:exrop, {1, 2, 3})
iex> Aja.Vector.new(1..10) |> Aja.Vector.take_random(2)
vec([7, 2])
iex> Aja.Vector.new([:foo, :bar, :baz]) |> Aja.Vector.take_random(100)
vec([:bar, :baz, :foo])
@spec take_while(t(val), (val -> as_boolean(term()))) :: t(val) when val: value()
Takes the elements from the beginning of the vector
while fun
returns a truthy value.
Runs in linear time regarding the size of the returned subset.
Examples
iex> Aja.Vector.new(1..100) |> Aja.Vector.take_while(fn x -> x < 7 end)
vec([1, 2, 3, 4, 5, 6])
iex> Aja.Vector.new([1, true, %{}, nil, "abc"]) |> Aja.Vector.take_while(fn x -> x end)
vec([1, true, %{}])
Converts the vector
to a list.
Runs in linear time.
Examples
iex> Aja.Vector.new(10..25) |> Aja.Vector.to_list()
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
iex> Aja.Vector.new() |> Aja.Vector.to_list()
[]
Returns a copy of the vector without any duplicated element.
The first occurrence of each element is kept.
Examples
iex> Aja.Vector.new([1, 1, 2, 1, 2, 3, 2]) |> Aja.Vector.uniq()
vec([1, 2, 3])
Returns a copy of the vector without elements for which the function fun
returned duplicate elements.
The first occurrence of each element is kept.
Examples
iex> vector = Aja.Vector.new([x: 1, y: 2, z: 1])
vec([x: 1, y: 2, z: 1])
iex> Aja.Vector.uniq_by(vector, fn {_x, y} -> y end)
vec([x: 1, y: 2])
Opposite of zip/2
. Extracts two-element tuples from the given vector
and groups them together.
It takes a vector
with elements being two-element tuples and returns a tuple with two vectors,
each of which is formed by the first and second element of each tuple, respectively.
This function fails unless vector
only contains tuples with exactly two elements in each tuple.
Runs in linear time.
iex> {vector1, vector2} = Aja.Vector.new([{1, :a}, {2, :b}, {3, :c}]) |> Aja.Vector.unzip()
iex> vector1
vec([1, 2, 3])
iex> vector2
vec([:a, :b, :c])
Returns a copy of vector
with an updated value at the specified index
.
Returns the vector
untouched if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new(1..8) |> Aja.Vector.update_at(2, &(&1 * 1000))
vec([1, 2, 3000, 4, 5, 6, 7, 8])
iex> Aja.Vector.new(1..8) |> Aja.Vector.update_at(8, &(&1 * 1000))
vec([1, 2, 3, 4, 5, 6, 7, 8])
iex> Aja.Vector.new(1..8) |> Aja.Vector.update_at(-1, &(&1 * 1000))
vec([1, 2, 3, 4, 5, 6, 7, 8000])
Returns a copy of vector
with an updated value at the specified index
.
Raises an Aja.Vector.IndexError
if index
is out of bounds.
Supports negative indexing from the end of the vector
.
Runs in effective constant time.
Examples
iex> Aja.Vector.new(1..8) |> Aja.Vector.update_at!(2, &(&1 * 1000))
vec([1, 2, 3000, 4, 5, 6, 7, 8])
iex> Aja.Vector.new(1..8) |> Aja.Vector.update_at!(-1, &(&1 * 1000))
vec([1, 2, 3, 4, 5, 6, 7, 8000])
iex> Aja.Vector.new(1..8) |> Aja.Vector.update_at!(-9, &(&1 * 1000))
** (Aja.Vector.IndexError) out of bound index: -9 not in -8..7
@spec with_index(t(val), index()) :: t({val, index()}) when val: value()
@spec with_index(t(val), (val, index() -> mapped_val)) :: t(mapped_val) when val: value(), mapped_val: value()
Returns the vector
with each element wrapped in a tuple alongside its index.
May receive a function or an integer offset.
If an integer offset
is given, it will index from the given offset
instead of from zero.
If a function
is given, it will index by invoking the function for each
element and index (zero-based) of the vector
.
Runs in linear time.
Examples
iex> vector = Aja.Vector.new(["foo", "bar", "baz"])
iex> Aja.Vector.with_index(vector)
vec([{"foo", 0}, {"bar", 1}, {"baz", 2}])
iex> Aja.Vector.with_index(vector, 100)
vec([{"foo", 100}, {"bar", 101}, {"baz", 102}])
iex> Aja.Vector.with_index(vector, fn element, index -> {index, element} end)
vec([{0, "foo"}, {1, "bar"}, {2, "baz"}])
Zips corresponding elements from two vectors into one vector of tuples.
The size of the returned vector is the one of the smallest of the input vectors.
Runs in linear time.
iex> Aja.Vector.zip(Aja.Vector.new([1, 2, 3]), Aja.Vector.new([:a, :b, :c]))
vec([{1, :a}, {2, :b}, {3, :c}])
iex> Aja.Vector.zip(Aja.Vector.new(0..100), Aja.Vector.new([:a, :b, :c]))
vec([{0, :a}, {1, :b}, {2, :c}])
@spec zip_with(t(val1), t(val2), (val1, val2 -> val3)) :: t(val3) when val1: value(), val2: value(), val3: value()
Zips corresponding elements from two vectors into a new vector,
transforming them with the zip_fun
function as it goes.
The corresponding elements from each vector are passed to the
provided 2-arity zip_fun
function in turn.
Runs in linear time.
iex> Aja.Vector.zip_with(Aja.Vector.new([1, 2, 3]), Aja.Vector.new([:a, :b, :c]), &{&2, &1})
vec([a: 1, b: 2, c: 3])
iex> Aja.Vector.zip_with(Aja.Vector.new(0..100), Aja.Vector.new([:a, :b, :c]), &{&2, &1})
vec([a: 0, b: 1, c: 2])