共计 2057 个字符,预计需要花费 6 分钟才能阅读完成。
在 elixir 中罕用的数据结构都是不可变(immutable)的,也就是每次批改实际上是在内存中新建一个数据。不可变数据的益处是能够防止副作用,不便测试,缩小 bug。毛病也很显著,就是速度慢。
例如 advent of code 2020 的第 23 天 Part2 这道题,通过应用可变的数据结构,能够大幅晋升速度。
题目粗心是:给定一个数列,结尾 9 个数是“389125467”,前面是 10 到 1 百万,最初一个数连贯到结尾造成环。以 3 为以后数,执行以下操作 100 百万次 ——“将以后数左边 3 个数拿起,而后在残余的数字里寻找一个指标数,它比以后数小,且值最靠近,如果没有,则返回最大的数。将拿起的 3 个数插入到指标数的左边。以以后数左边的数作为新的以后数。”
在 elixir 里是无奈间接操作链表指针的,但咱们能够用 map 来模仿一个单链表:
defmodule MapList do
def new do
%{}
end
def put(s, a, next) do
Map.put(s, a, next)
end
def find(s, a) do
Map.get(s, a)
end
def exchange(s, a, x) do
Map.get_and_update!(s, a, fn c -> {c, x} end)
end
end
上面是理论的解题逻辑:
def start(label, amount, moves, module) do
label = String.split(label, "", trim: true) |> Enum.map(&String.to_integer/1)
list = module.new()
list =
for {x, n} <- Enum.zip(label, tl(label) ++ [length(label) + 1]), reduce: list do
acc ->
module.put(acc, x, n)
end
list =
for x <- (length(label) + 1)..(amount - 1), reduce: list do
acc ->
module.put(acc, x, x + 1)
end
list = module.put(list, amount, hd(label))
list = move(list, hd(label), amount, moves, module)
a = module.find(list, 1)
b = module.find(list, a)
149_245_887_792 = a * b
end
def move(list, _, _, 0, _), do: list
def move(list, i, max, moves, module) do
a = module.find(list, i)
b = module.find(list, a)
c = module.find(list, b)
t = target(i - 1, [a, b, c], max)
{tr, list} = module.exchange(list, t, a)
{cr, list} = module.exchange(list, c, tr)
list = module.put(list, i, cr)
move(list, cr, max, moves - 1, module)
end
def target(0, picked, max) do
target(max, picked, max)
end
def target(i, picked, max) do
if i in picked do
target(i - 1, picked, max)
else
i
end
end
因为 map 是不可变数据结构,可想而知将其复制数亿次耗时是比拟长的。在 erlang 21 版本后,退出了 :atomics
模块,能够让咱们新建并批改一个全局的数组。能够用它来实现一个可变的单链表。
defmodule Atomics do
def new do
:atomics.new(1_000_000, [])
end
def put(s, a, next) do
:ok = :atomics.put(s, a, next)
s
end
def find(s, a) do
:atomics.get(s, a)
end
def exchange(s, a, x) do
old = :atomics.exchange(s, a, x)
{old, s}
end
end
比拟下两种实现的速度:
def run do
Benchee.run(%{"map" => fn -> start("389125467", 1_000_000, 10_000_000, MapList) end,
"atomics" => fn -> start("389125467", 1_000_000, 10_000_000, Atomics) end
})
end
Name ips average deviation median 99th %
atomics 0.22 4.56 s ±6.09% 4.56 s 4.76 s
map 0.0239 41.76 s ±0.00% 41.76 s 41.76 s
Comparison:
atomics 0.22
map 0.0239 - 9.16x slower +37.20 s
能够看到应用 :atomics
模块后,耗时只有 map 的九分之一左右。
:atomics
也有它的局限性,例如数组的值只能是 64 位的整数。
正文完