Is there any guide or site that tells us the complexities of all the different built-in functions of the different elixir modules?
For example, if lets say I had a list [1,2,3,4,5] and I wanted to convert this to a tuple, then I have to use the function List.to_tuple([1,2,3,4,5]). Now, what is the time complexity of this to_tuple method? Is it O(n) or O(1) or something else?
Also, a completely random question but is it entirely impossible to do a binary search in elixir in O(log(n)) time complexity and O(1) space complexity?
It’s possible to do binary search in Elixir in O(log(n)) time, but you would need to use a Tuple for that, and usually, Tuple’s aren’t meant to be used as an enumerable. You can find many examples of binary search in Elixir here.
Technically we could have them, but only if there would be any guarantees about that. As Erlang provides no complexity guarantees about functions like erlang:list_to_tuple/1 we cannot provide such information as part of the documentation, as it would became part of the contract between language developers and language users, and as I said before - no-one is willing to limit the VM developers with such contract.
There’s no guide I’m aware of; the best approaches are thinking hard, source code examination and measurement.
Thinking hard, constructing a tuple from every element of the list requires seeing every element of the list. The only way to see element N of a list is to visit the previous N-1 elements, so at minimumlist_to_tuple must be O(N).
On the source code front, List.to_tuple calls :erlang.list_to_tuple directly, which is implemented in C:
The important part happens on lines 3865-3869; the list passed in is iterated over and element pointers are copied to the tuple’s memory one-at-a-time: therefore the algorithm is definitely O(N).
Note that this is much much better than a naive implementation that uses Tuple.append recursively, because that function has to copy every pointer at every intermediate step plus allocate a new tuple, as shown in:
The :gb_trees module in Erlang stdlib and the paper it’s based on are a good place to start investigating this kind of thing.
@hauleth, why do you say “only if there would be any guarantees about that”? Why does Erlang provides “no complexity guarantees”? What does that mean?
