I tried to use Dictionares instead of the basic Dict, but keeping the same structure, in this elegant script by @Daniel_Gonzalez that solves the problem of the AOC 2024 d11, but I got no improvements.
I don’t know if the failure is due to a clumsy application of the Dictionares.jl package or if the script needs to be changed to take advantage of the package’s features.
I hope someone else will succeed in doing so.
one SOL od d11 AOC 2024
const NO_STONE = -1 # folks, we're writing old school C today
stones = split(readlines("2024/inputs/day11.txt") |> only, " ") .|> x -> parse(Int, x)
number_of_digits(x) = floor(Int, log10(x)) + 1
function blink(stone::Integer)
stone == 0 && return (1, NO_STONE)
n = number_of_digits(stone)
iseven(n) && return divrem(stone, 10^(n ÷ 2))
(stone * 2024, NO_STONE)
end
function solve(stones, n)
d = Dict{Int64,Int64}()
for s ∈ stones
d[s] = 1
end
for _ in 1:n
d_n = Dict{Int64,Int64}()
for (s, n) ∈ d
for s2 ∈ blink(s)
s2 == NO_STONE && continue
if haskey(d_n, s2)
d_n[s2] += n
else
d_n[s2] = n
end
end
end
d = d_n
end
sum(values(d))
end
solve(stones, 25)
solve(stones, 75)
For those who want to try, I leave the input to use in the tests
Since the posters above seem to suggest that Dictionaries.jl is faster for iteration but possibly slower for random access, it’s normal to not expect a speedup for your code which involves random access of the d_n Dict.
Having said that, the following part your code could potentially be made faster if the code can be rewritten to take advantage of a token API for avoiding repeated hash computations:
Another version of solve saving hash calculation using mergewith!:
using OrderedCollections
function solve(stones, n)
d_new = Dict{Int,Int}()
d_old = Dict(stones .=> 1)
for _ in 1:n
for (s, n) ∈ d_old
t1, t2 = blink(s)
mergewith!(+, d_new,
t2 == NO_STONE ? LittleDict((t1,),(n,)) :
LittleDict((t1,t2),(n,n)))
end
d_old, d_new = d_new, d_old
empty!(d_new)
end
sum(values(d_old))
end
I apologize for bringing up these old messages, but for me, and perhaps for others too, they are of current interest.
I tried to use the instructions of the update function!() but I get no improvements.
Maybe I apply it wrong
julia> function solve(stones, n)
d = Dict{Int64,Int64}()
for s ∈ stones
d[s] = 1
end
for _ in 1:n
d_n = Dict{Int64,Int64}()
for (s, n) ∈ d
for s2 ∈ blink(s)
s2 == NO_STONE && continue
index = Base.ht_keyindex2!(d_n, s2)
if index > 0
@inbounds d_n.vals[index] += n # = func(dict.vals[index])
else
@inbounds Base._setindex!(d_n, n, s2, -index)
end
# if haskey(d_n, s2)
# d_n[s2] += n
# else
# d_n[s2] = n
# end
end
end
d = d_n
end
sum(values(d))
end
solve (generic function with 1 method)
julia> solve(stones, 25)
197357
julia> solve(stones, 75)
234568186890978
julia> @btime solve(stones, 25) # 260 us
635.100 μs (9800 allocations: 496.95 KiB)
197357
julia> @btime solve(stones, 75) # 12ms
29.340 ms (590514 allocations: 23.42 MiB)
234568186890978
In the case of this script, using get!() does not improve the situation.
julia> function solve(stones, n)
d = Dict{Int64,Int64}()
for s ∈ stones
d[s] = 1
end
for _ in 1:n
d_n = Dict{Int64,Int64}()
for (s, n) ∈ d
for s2 ∈ blink(s)
s2 == NO_STONE && continue
d_n[s2] = n + get!(d_n, s2, 0)
# index = Base.ht_keyindex2!(d_n, s2)
# if index > 0
# @inbounds d_n.vals[index] += n # = func(dict.vals[index])
# else
# @inbounds Base._setindex!(d_n, n, s2, -index)
# end
# if haskey(d_n, s2)
# d_n[s2] += n
# else
# d_n[s2] = n
# end
end
end
d = d_n
end
sum(values(d))
end
solve (generic function with 1 method)
julia> @btime solve(stones, 25) # 260 us
593.500 μs (8490 allocations: 476.48 KiB)
197357
julia> @btime solve(stones, 75) # 12ms
26.786 ms (345428 allocations: 19.68 MiB)
234568186890978