Comparing Julia and Python for basic operations

General Usage Performance
1

Hi there Julia community!,

I’m quite new to the language and I’m falling in love more and more with it every day :slight_smile:

In order to improve my knowledge, I’m revisiting Project Euler problems, which I’ve done in Python, with Julia and, so far, Julia code is waaay faster than Python (who knew! :D)
But I’m getting problems with the following problem that runs in 4.6 s while the Python version runs in 2.4 s. Both versions are almost identical

Julia version

function Problem12()
    #=
     The sequence of triangle numbers is generated by adding the natural
    numbers. So the 7th triangle number would be:
    1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

    The first ten terms would be:
    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

    Let us list the factors of the first seven triangle numbers:

     1: 1
     3: 1,3
     6: 1,2,3,6
    10: 1,2,5,10
    15: 1,3,5,15
    21: 1,3,7,21
    28: 1,2,4,7,14,28

    We can see that 28 is the first triangle number to have over five divisors.

    What is the value of the first triangle number to have over five hundred
    divisors?
    =#

    function num_divisors(n)
        res = floor(sqrt(n))
        divs = []
        for i in 1:res
            if n%i == 0
                append!(divs,i)
            end
        end
        if res^2 == n
            pop!(divs)
        end
        return 2*length(divs)
    end

    triangle = 0
    for i in Iterators.countfrom(1)
        triangle += i
        if num_divisors(triangle) > 500
            return string(triangle)
        end
    end
end

Python version (for comparison)

import itertools
from math import sqrt, floor


# Returns the number of integers in the range [1, n] that divide n.
def num_divisors(n):
    end = floor(sqrt(n))
    divs = []
    for i in range(1, end + 1):
        if n % i == 0:
            divs.append(i)
    if end**2 == n:
        divs.pop()
    return 2*len(divs)


def compute():
    triangle = 0
    for i in itertools.count(1):
        # This is the ith triangle number, i.e. num = 1 + 2 + ... + i =
        # = i*(i+1)/2
        triangle += i
        if num_divisors(triangle) > 500:
            return str(triangle)
1 Like
2

One simple speed-up is to replace this line by res = floor(Int, sqrt(n)), as otherwise floor returns a Float64.

On a side note, I wonder if your num_divisors function is correct, as it returns 2 for 9 instead of 3 (unless I have the wrong definition of “divisors”). A fix could be to not pop! when res^2 == n, but instead to substract 1 to the returned result.

2 Likes
3

Thx for your answer!
I’ve made a couple of changes (I’m not interested in the divisors themselves, just in the number of them) and now the code runs in 0.12 s :smiley:

    function num_divisors(n)
        #res = floor(sqrt(n))
        res = floor(Int, sqrt(n))
        divs = 0#[]
        for i = 1:res
            if n % i == 0
                divs += 1
                #append!(divs, i)
            end
        end
        if res^2 == n
            divs -= 1
            #pop!(divs)
        end
        return 2 * divs #length(divs)
    end

Regarding the validity of the function, I guess that it’s correct as it gives the solution as good in Project Euler.

4

With the “validity” change I suggested, the answer to Problem12 stays the same.

5

One additional remark:

This creates an array with Any Type, analogue to a Python List. Operations on this list are very slow for the same reason as in Python - for every operation the element type must be detected dynamically.
The performance is much better if you specify the data type of the list in advance, e.g.
divs = Int[].

6 Likes
6

Maybe not faster, but isn’t isqrt(n) more robust?

3 Likes
7

Yes, but I think the robustness issue applies to n > maxintfloat() which is about 9 000 000 000 000 000.

1 Like
8

You still have the same mistake in your code. You’re subtracting one from divs, where you should be subtracting it from the 2*divs that is returned.
Here’s a shorter version, that’s even faster on my machine (using isqrt, as @DNF suggested):

function num_divisors2(n)
    r = isqrt(n)
    2 * count(n % i == 0 for i in 1:r) - (r^2 == n)
end

not sure why this is faster than a straight loop.

1 Like
9

Thx a lot! As you said, it runs a bit faster and does less allocations :smiley: