Hello everyone, I’d like to know if is possible to execute all “populary known” algorithms in elixir. I’m asking that because most of algorithms use arrays for example and as far as I known elixir does not implement those so my question is if is possible to implement such algorithms with the same performance as in those languages that implement such data-structures.
Algorithms designed around mutable datastructures will not translate directly into Elixir, nor will they perform the same. If you’re trying to get things done in Elixir this generally isn’t an issue as it just pushes you to reframe the problem into something more amenable to immutable datastructures, which gets you some side benefits along the way.
If your goal is to practice algorithms on mutable datastructures however then I’d pick a language that has those natively.
5 Likes
Possible to implement - yes. Will these perform equally well as in other languages? It depends on the algorithm. If such algorithm requires random access structures that can be cheaply updated, then implementing them in performant manner in Elixir will be hard, but you still will be able to do so (as per Church-Turing thesis).
2 Likes
I don’t think I get it. Talking about leetcode problems some of them has big O constraints and the solution to achieve such constraint is to use specific data structures those sometimes dont exist in functional languages so those kind of problems cant be solved in a “good time complexity”?
Complexity analysis is always constrained. For example in C++ you can do:
auto l = std::list{1,2,3,4,5};
std::cout << std::binary_search(l.begin(), l.end(), 1) << '\n';
[link]
And it will have O(n log n) “real” complexity despite the fact that std::binary_search is (by the standard) defined to have O(log n) complexity (the reason why there is such complexity and how C++ standard committee slipped that stuff there is left for the curious reader).
If you’re just doing it for educational purposes, sure. I came across a project like that in ruby a while back - implementations of pure ruby data structures like a red-black tree, a priority queue, etc. If you want actually useful data structures though, you’ll need to build them in C / C++ or something similar and then import the library as a nif.
Ok, I’m curious… 
If an array is already sorted, how is binary searching it not O(log n)?
Is it because in your example it’s a list and not an array where elements can be accessed in constant time?
Indeed. Because it is list, and advancing iterator over list is O(n) not O(1)
3 Likes
