Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Optimising a julia one-liner to make it as fast as python

Tags:

python

julia

I have written a simple one-liner in julia to solve a little maths problem: find a two digit number, A and a three digit number B such that their product, A x B is a five digit numbers and every digit from 0 to 9 appears exactly once among the numbers A, B and A x B. For example,

54 x 297 = 16,038

Here is my julia code which finds all the possible solutions:

println(filter(l -> length(unique(reduce(vcat, (map(digits, l))))) == 10, [[x, y, x*y] for x in Range(10:99), y in Range(100:999)]))

It solves the problem but then I tried in python and came up with this:

print filter(lambda y: len(set(''.join([str(x) for x in y])))==10, [[x, y, x*y] for x in range(10, 99) for y in range(100, 999)])

Timing them both, I was surprised to find that the python code ran more than twice as fast as the julia code. Any suggestions for a faster approach for the julia code (preferably keeping it to a one-liner)?

Aside: I know I can improve both with a quick tweak of the ranges to range(12, 98) and range(102, 987).

Update

Moving beyond one-liners, I've taken the advice that loops can be faster than lists, so I compared the following alternatives:

Julia

ans = Array{Tuple{Int32, Int32, Int32}}(0)
for x in 12:98 
  for y in 102:987
    if length(unique(digits(x+y*100+x*y*100_000)))==10 push!(ans, (x, y, x*y) end
  end
end
println(ans)

Python

ans = []
for x in range(12,98): 
  for y in range(102,987):
    if len(set(str(x+y*100+x*y*100000)))==10:
      ans.append((x, y, x*y))
print ans

The python code runs much faster (even if I change the code for both to simply print out the results in the loop rather than collect them in a list). I was expecting better performance from julia.

Also, in case you are interested, the complete list of solutions is

39 x 402 = 15,678
27 x 594 = 16,038
54 x 297 = 16,038
36 x 495 = 17,820
45 x 396 = 17,820
52 x 367 = 19,084
78 x 345 = 26,910
46 x 715 = 32,890
63 x 927 = 58,401
like image 607
seancarmody Avatar asked Apr 18 '16 12:04

seancarmody


1 Answers

@simd for x in 10:99 for y in 100:999 length(unique(digits(x+y*100+x*y*100_000)))==10 && println(x,'*',y,'=',x*y) end end

In my computer this code is about 3x the speed of the origin one. (0.223902 seconds vs 0.680781 seconds)

The key is to "avoid unnecessary arrays". Use for loops or tuple when possible

like image 161
张实唯 Avatar answered Nov 11 '22 21:11

张实唯