The genesis of my question is this problem from Leetcode.
I want a data structure that keeps values sorted without iterating over the whole structure on each update. I thought using a gb_tree would do the trick, but the implementation I came up with is actually slower than the naive recursive implementation I did using a list as the data structure. I suspect my gb_trees implementation is inefficient for logic reasons rather than structure reasons but can’t figure it out on my own. Are gb_trees a good structure for this use case? If so how might I improve my approach? If not, what alternatives would be better suited to the task?
List implementation (~275ms runtime):
def last_stone_weight(stones) do
stones
|> Enum.sort(:desc)
|> smash_sorted()
end
def smash_sorted([stone]), do: stone
def smash_sorted([x, y | stones]) do
[ abs(x-y) | stones]
|> Enum.sort(:desc)
|> smash_sorted()
end
gb_trees implementation (~400ms runtime):
def last_stone_weight(stones) do
stones
|> to_gb_tree()
|> smash_heaviest_pair()
end
def to_gb_tree(stones) do
stones
|> Enum.reduce(:gb_trees.empty(), fn stone, tree -> update_or_insert(stone, tree) end)
end
def smash_heaviest_pair(tree) do
if :gb_trees.is_empty(tree) do
0
else
{a, count, new_tree} = :gb_trees.take_largest(tree)
case count do
2 -> smash_heaviest_pair(new_tree)
1 -> if :gb_trees.is_empty(new_tree) do
a
else
smash(a, new_tree) |> smash_heaviest_pair()
end
n -> :gb_trees.update(a, count - 2, tree) |> smash_heaviest_pair()
end
end
end
def smash(a, tree) do
{b, count, new_tree} = :gb_trees.take_largest(tree)
case count do
1 -> update_or_insert(a - b, new_tree)
n -> update_or_insert(a - b, :gb_trees.enter(b, n - 1, tree))
end
end
def update_or_insert(key, nil), do: update_or_insert(key, :gb_trees.empty())
def update_or_insert(key, tree) do
case :gb_trees.lookup(key, tree) do
{_, val} -> :gb_trees.update(key, val + 1, tree)
:none -> :gb_trees.enter(key, 1, tree)
end
end
