2019-07-12

JuliaでProject Euler(2)

Julia

Problem 2

Juliaで次のように書く。

function e002(N)
    local s = 0
    local a = 1
    local b = 1
    while b <= N
        if b%2 == 0
            s += b
        end
        a, b = b, a+b
    end
    return s
end

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

Pythonのタプルで代入は使える。ちなみに配列は同様にできないらしい。

generator

Fibonacci数列をgeneratorで排出できればきれいに書くことができるが、Juliaでgeneratorを使うには次のように書けばよい。

fibs() = Channel() do c
    local a = 1
    local b = 1
    while true
        push!(c, b)
        a, b = b, a+b
    end
end

function e002a(N)
    local s = 0
    for f in fibs()
        if f > N
            break
        elseif f%2 == 0
            s += f
        end
    end
    return s
end

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

あまりきれいになっていないように思えるが、気のせいだろうか。Juliaにはどうもtakewhileがないようなのだ。takewhileなんか使ったら遅くなるに決まっているからだろうか。
generatorは、ここではcという入れ物を用意して、そこにpushすることで実現しているっぽい。

2019-07-11

JuliaでProject Euler(1)

Julia

JuliaでProject Euler(1)

JuilaというPython対抗っぽい言語があるらしいので試してみる。
PyPyより速いらしい。

準備

ここからGeneric Linux Binaries for x86 64bit をダウンロード。

https://julialang.org/downloads/

$ tar xvfz julia-1.1.1-linux-x86_64.tar.gz

あと、パスを通す

Problem 1

https://projecteuler.net/problem=1

まず、Pythonで次のように書く。

import sys

N = int(sys.argv[1])
s = 0
for n in xrange(1, N):
    if n%3 == 0 or n%5 == 0:
        s += n
print s

これをPython2とPyPyで実行すると、

$ time python2 e001.py 1000000000
233333333166666668

real    1m25.532s
user    1m25.484s
sys     0m0.016s

$ time pypy e001.py 1000000000
233333333166666668

real    0m2.928s
user    0m2.891s
sys     0m0.031s

Juliaに翻訳するとこうなる。

N = parse(Int, ARGS[1])
s = 0
for n in 1:(N-1)
    if n%3 == 0 || n%5 == 0
        global s += n
    end
end

println(s)

まず、parseは文字列を数値に変換する。Intは環境依存で、ここではInt64。
ループや関数にはコロン(:)をつけずに（いつも間違える）、最後にendをつける。

1:N-1はPython2のxrangeみたいなもの。ただし、これで1からN-1まで排出する。

論理演算子のorは||に。こういう記号は排除するのがプログラミング言語の流れだと思っていたのだが。今どきはC++にもand/orが導入されているのに（Microsoftは知らない）。

globalはなくすとs not definedとなってしまう。forの中は別のスコープらしい。globalをつければ、グローバルスコープのsだと解釈されるらしい。

これを実行すると、

$ time julia e001.jl 1000000000
233333333166666668

real    1m41.669s
user    1m41.938s
sys     0m0.313s

Python並みなのだが。
そういえば、Pythonでもglobal変数を参照すると時間がかかるという話があるので、関数化してみた。

import sys

def e001a(N):
    s = 0
    for n in xrange(1, N):
        if n%3 == 0 or n%5 == 0:
            s += n
    return s

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

function e001a(N)
    s = 0
    for n in 1:(N-1)
        if n%3 == 0 || n%5 == 0
            s += n
        end
    end
    return s
end

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

実行すると、

time python2 e001a.py 1000000000
233333333166666668

real    0m53.546s
user    0m53.438s
sys     0m0.031s

time pypy e001a.py 1000000000
233333333166666668

real    0m3.143s
user    0m3.109s
sys     0m0.031s

time julia e001a.jl 1000000000
233333333166666668

real    0m1.642s
user    0m1.797s
sys     0m0.344s

PyPyよりも速くなった。

関数型っぽい書き方もできる。

import sys

def e001(N):
    return sum(n for n in xrange(1, N) if n%3 == 0 or n%5 == 0)

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

同様に、

function e001(N)
    return sum(n for n in 1:N-1 if n%3 == 0 || n%5 == 0)
end

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

実行すると、

$ time pypy e001b.py 1000000000
233333333166666668

real    0m8.691s
user    0m8.641s
sys     0m0.047s

time julia e001b.jl 1000000000
233333333166666668

real    0m2.305s
user    0m2.375s
sys     0m0.516s

遅くなる。

2019-05-11

Project Euler 668

https://projecteuler.net/problem=668

236着。
正答者が多いのは、ごり押しが利くからではないだろうか。普通に各自然数の最大の素数を求めるだけで、PyPyでも1時間くらいで済みそうだ。
この問題はよくある方法でふつうの時間で解ける。10¹⁰は2.6sec、10¹¹でも13sec。なぜ10¹¹にしなかったのだろう。これならごり押しが利きにくいのに。