Euler project - P 164

General Usage Performance
21

I agree that using randomness makes this difficult since you want an exact result and randomness doesn’t really lend itself towards that.

Yes, implementation can be tricky. I suggest starting with the most straight forward implementation you can think of and only optimize after you have confirmed that the algorithm is correct/promising and you need the increase in speed.

I will also remind you that you only care about the total count, not which numbers make up that count.
I think most other things, including finding out if your idea is on the right track or not, should be in your hands. If you have a Julia specific question I’m sure we can help you out. Best of luck!

22

When we think recursion we often think top to bottom like 5! = 54! etc. The other way to think of it is to build from bottom to top e.g. 0! = 1, 1 = 10!, 2 = 21! = 2, 3 = 32! = 3 * 2 = 6 etc.

23

For Haskell you can find a very elegant solution here:
https://wiki.haskell.org/Euler_problems/161_to_170#Problem_164
Probably you have to invest some time for understanding the details as the program has no explanations. However it should be easy to transform this solution into a Julia program.

24

BTW my solution is about 40 lines long and not as fast others but just think that it can be very fast! Hope that will be the encourage to spur you on!

image

25

Please don’t post solutions out of respect for the project euler maintainers.

26

@xiaodai: agreed.

27

got the hint!

28

I think everyone gets essentially the same solution, after some reflection. But I noticed something weird with Julia. I wrote the following line inside my definition of the function P that solves the problem (I don’t give here the full code, because of the rules of the Euler project):

   beta[i, j] = sum(alpha[j, 1 : 12-i-j])

and got this benchmark:

  julia> using BenchmarkTools
  julia> @btime P(20);
  64.186 μs (993 allocations: 115.05 KiB)

These numerous allocations are due to the usage of the function sum, they disappear if I replace it by the explicit loop:

  beta[i, j] = 0
  for k in 1 : 12-i-j
     beta[i, j] += alpha[j, k]
  end

Benchmark:

julia> @btime P(20);
  12.315 μs (3 allocations: 2.55 KiB)

I understand the phenomenon, but I think it’s sad.

29

Yes, I agree it’s very sad that array slices allocate in Julia. I occasionally revert to Fortran for array-heavy codes for this exact reason. But let’s hope that some day this issue could be resolved. At the moment, you can use views or generators.

beta[i, j] = sum( view(alpha, j, 1:12-i-j) )
# OR
beta[i, j] = sum( alpha[j, k] for k in 1:12-i-j )
30

A less intrusive way of using views is with the macros @view / @views

@views beta[i, j] = sum(alpha[j, 1 : 12-i-j])
beta[i, j] = sum(@view alpha[j, 1 : 12-i-j])
31

@Seif_Shebl and @baggepinnen : thanks ! For the record, here is a benchmark for code modified along your suggestions; with:

  beta[i, j] = sum(@view alpha[j, 1 : 12-i-j])

I get:

  julia> using BenchmarkTools
  julia> @btime P(20);
  22.883 μs (993 allocations: 64.42 KiB)

Memory allocations are less expensive, but don’t disappear (the line of code I’m talking about is indeed executed 18*55 = 990 times, and there are three obvious allocations in my code, e.g. when matrices alpha, beta are defined).

Solution with generator is worse:

  beta[i, j] = sum(alpha[j, k] for k in 1 : 12-i-j)

gives:

  julia> @btime P(20);
  28.449 μs (1983 allocations: 64.42 KiB)

(I don’t understand why the number of allocations is twice the preceeding one, whereas the amount of memory allocated is the same).