Is there a faster alternative to Enum.at
? Basically, something in O(1)
Enum.at
is as fast as the underlying container is able to access certain elements.
For lists, this is not very fast, indeed being O(n)
(linear time).
However, alternative containers exist that implement the Enum
protocol, which allow O(log(n))
(logarithmic-time) or O(1)
(constant-time) (either ‘real’ or ‘amortized’) access to random elements.
See for instance the arrays library.
There are many, but which one to use is strongly-coupled to what operations you need to be efficient:
-
if you want sparse data (most indexes don’t have anything in them), you could use a
Map
ofindex
→value
. This wastes space with keys, but hasO(log(n))
access for more than 32 elements. -
if you have arrays of fixed size (not too large), then tuples are very fast (
elem
is constant-time) to read. Updating is expensive, and resizing is as well - both copy every pointer in the structure. -
if you’re converting an algorithm that uses zero-based indexing into a block of memory to simulate some other data structure (ie, a queue / a stack / a circular list), a better data structure may help. For instance, the Erlang
:queue
module allows amortized-constant-time pushing and popping from either end.