JuliaでProject Euler(4) - inamori’s diary

Problem 4

Pythonで次のように書く。

import sys

def digits(n):
    ds = []
    while n > 0:
        n, r = divmod(n, 10)
        ds.append(r)
    return ds

def is_palindromic(n):
    ds = digits(n)
    L = len(ds)
    return all(ds[k] == ds[L-k-1] for k in xrange((L+1)/2))

def e004(E):
    max_a = 10**E-1
    max_n = 0
    for a in xrange(max_a, 10**(E-1)-1, -1):
        for b in xrange(max_a, max(a, (max_n+a-1)/a)-1, -1):
            n = a*b
            if is_palindromic(n):
                max_n = n
                break
    return max_n

N = int(sys.argv[1])
print e004(N)

これをそのままJuliaに翻訳する。

function digits(n)
    a = []
    while n > 0
        r = n%10
        n = div(n, 10)
        push!(a, r)
    end
    return a
end

function is_palindromic(n)
    a = digits(n)
    L = length(a)
    for i in 1:div(L+1, 2)
        if a[i] != a[L-i+1]
            return false
        end
    end
    return true
end

function e004(E)
    local max_n = 0
    local max_a = 10^E-1
    for a in max_a:-1:10^(E-1)
        for b in max_a:-1:max(a, div(max_n+a-1, a))
            n = a*b
            if is_palindromic(n)
                max_n = n
                break
            end
        end
    end
    return max_n
end

N = parse(Int, ARGS[1])
println(e004(N))

配列のインデックスは、0ではなく1から始まります。まるで地動説から天動説に逆戻りしたかのようですね。

$ time pypy e004.py 8
9999000000009999

real    0m5.356s
user    0m5.281s
sys     0m0.047s

$ time julia e004.jl 8
9999000000009999

real    0m10.907s
user    0m10.922s
sys     0m0.594s

Juliaが遅いのは、たぶん最初のdigitsの中の、

a = []

で、これだと型が、

Array{Any,1}

で、1次元の配列で要素の型は何でもありとなる。
こういうときは、型を指定するとよい。

    a::Array{Int,1} = []

time julia e004a.jl 8
9999000000009999

real    0m8.420s
user    0m8.516s
sys     0m0.547s

あまり速くならない。
divmodが無いのが効いているのだろうか。

Edit:
PyPyでdivmodをやめたが、速度は変わらなかった。