Hi everybody,
I am currently benchmarking languages to write a kakuro solver in. I am not
really familiar with Julia but ported the small algorithm I had written in
Lisp and PyPy to Julia nevertheless. Unfortunately Julia's performance is
really bad and I'm reaching out to the community to find out whether it's
due to my coding or not.
Here's the code in Julia:
function decompose(val, num)
function sub(num, tot, res, pos, allres)
if val==tot && num==0
union(allres, res)
elseif tot<val && num>0 && !isempty(pos)
sub(num-1, tot+pos[1], union(copy(res),pos[1]), pos[2:end], sub(num,
tot, res, pos[2:end], allres))
else
allres
end
end
sub(num, 0, Int16[], 1:(max(num, 10))-1, Array[])
end
for i in 1:45
for j in 2:20
res = decompose(i, j)
end
end
It takes roughly 13.4 seconds on my computer.
The equivalent Python code
def decompose(val, num):
def sub(num, tot, res, pos, allres):
if tot == val and num == 0:
return allres+res
elif tot < val and num != 0 and pos:
return sub(num-1, tot+pos[0], res+[pos[0]], pos[1:], sub(num,
tot, res, pos[1:], allres))
else:
return allres
return sub(num, 0, [], range(1, max(num, 10)), [])
if __name__ == "__main__":
for i in range(1, 46):
for j in range(2,21):
res = decompose(i,j)
is 1.4 seconds and the Lisp
defun decompose (val num)
(labels ((sub (num tot res pos allres)
(cond
((and (= tot val) (zerop num)) (cons (reverse res) allres))
((and (< tot val) (not (zerop num)) (not (null pos)))
(sub (1- num) (+ tot (car pos)) (cons (car pos) res) (cdr
pos)
(sub num tot res (cdr pos) allres)))
(t allres))))
(reverse (sub num 0 nil (loop for i from 1 below (max num 10) collect
i) nil))))
(time
(loop for val from 1 below 46 do
(loop for num from 2 below 21 do
(let ((res (decompose val num)))))))
is 0.5 seconds.
Any hints to make the Julia code perform better?
Regards,
-Patrick
