stackcats
How to use a 'two pointer' algorithm in Elixir
I’m learning Elixir with Leetcode.
The Leetcode problem is Valid Triangle Number.
My Rust solution uses two pointers with array
impl Solution {
pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
nums.sort();
let mut ans = 0;
for i in 2..nums.len() {
let mut left = 0;
let mut right = i - 1;
while left < right {
if nums[left] + nums[right] > nums[i] {
ans += right - left;
right -= 1;
} else {
left += 1;
}
}
}
ans as i32
}
}
I got Timeout when I trying to convert this code to Elixir.
defmodule Solution do
@spec triangle_number(nums :: [integer]) :: integer
def triangle_number(nums) do
len = Enum.count(nums)
if len < 3 do
0
else
nums |> Enum.sort |> loop_nums(2, len)
end
end
def loop_nums(nums, i, len) do
if i == len do
0
else
check_intervals(nums, 0, i - 1, i) + loop_nums(nums, i + 1, len)
end
end
def check_intervals(nums, a, b, c) do
cond do
a >= b -> 0
Enum.at(nums, a) + Enum.at(nums, b) > Enum.at(nums, c) -> b - a + check_intervals(nums, a, b - 1, c)
true -> check_intervals(nums, a + 1, b, c)
end
end
end
How to improve the performance?
Thank you.
Most Liked
stefanchrobot
nums is a list, so Enum.at has an O(N) access time. Switching nums to a map:
faster_nums =
nums
|> Enum.sort()
|> Enum.with_index()
|> Map.new(fn {value, index} -> {index, value} end)
and using Map.get or the Access protocol:
faster_nums[a] # instead of Enum.at(nums, a)
should do the trick, although that would be far from perfect. You can consider using Erlang’s array.
Qqwy
Alternatively, you can use a library like Arrays which exposes purely functional arrays which have very good time- and memory-properties, especially for operations such as accessing random elements or modifying random elements.
Depending on the exact array implementation, these run in an amortized O(log10(n)) or O(log32(n)). The difference between this and ‘true’ O(1) is only noticeable at ridiculously large collection sizes (at which point the array will no longer fit in your cache, or possibly in all of your non-swap RAM, which will probably overshadow these differences anyway.)
Of course an implementation in a ‘close to the metal’ language will be even faster and even more predictable (like no GC pauses), but for most situations this difference in efficiency is not worth dwelling on too long, as it is much more likely that your app will be bottlenecked by other things (like e.g. reading from/to files or communicating with external services over a network)
And for programming exercises such as Leetcode, these approaches are most definitely more than fast enough 
.
stefanchrobot
The best approach would be to come up with an algorithm that works well with immutable data structures. But the reality is that it’s going to be extra work since most of the problems of this kind are designed with the assumption that an array with O(1) random access time is the most basic data structure available in any given language. This is just not true for Elixir since it mostly works with tuples (fixed size, O(1) access) or lists (O(1) prepend and O(N) random access).
Using a map got me through all of Advent of Code exercises, so I think it’s a viable solution. But I would be extra careful trying to push that approach for production-ready systems.
Popular in Questions
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
The deployment platform built for Elixir: PaaS ease, VPS control.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
The deployment platform built for Elixir: PaaS ease, VPS control.
Courses that'll move you from confusion to "Aha, now I get it!"