Hi Patrick, The biggest difference here is how `res` and `allres` are updated. In python version you say 'res+[pos[0]]' which creates a new list with the value appended, but in the Julia version you use `union(copy(res),pos[1])`. The union function will hash all the values in res and pos[1] to ensure there are no duplicates, so it's considerably slower that what's happening in the python or lisp version. If I change those `union` calls to `push!`, it's more closely resembles what the python version is doing, and reduces the run time to about 0.5 seconds for me.
You could also try using a linked list like the one in the DataStructures package to avoid copying `res` whenever you add a value to it, which would bring it inline with the lisp version, and could be faster. On Sunday, October 18, 2015 at 6:49:45 PM UTC-7, Patrick Useldinger wrote: > > 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 >
