Julia: プログラムを速くするための定石--その7

オイラーの級数
http://commutative.world.coocan.jp/blog5/2021/09/post-431.html

計算時間を短縮するには，関数化する，ファイル入力しないの他，今回は，

関数に実際に渡されるものに特化した関数定義，引数の精度を見極める。
同じものを何度も計算しない（関数を呼ばない），p^3, p^5 を毎回計算するのは無駄（特に長精度計算の場合）。

ということで，元のプログラムを以下のように書き換えた。

using Primes

function SGN(p) # p は奇数に限られる。 p は Int64 で十分
    if ((p - 1) ÷ 2) % 2 == 0
        return -1
    else
        return 1
    end
end

function h()
    S1 = S2 = S3 = 0
    for p0 in primes(3, 10^10) # 3 以上 10^10 未満の奇数素数が対象
        s = SGN(p0)
        p = Int128(p0)
        S1 += s / p
        p2 = p^2
        S2 += s / (p*p2)    # p^3, p^5 を別途計算するのは無駄
        S3 += s / (p*p2*p2)
    end
    println("Z(1) = $S1")
    println("Z(3) = $S2")
    println("Z(5) = $S3")
end
@time h()

Z(1) = 0.33498102728650697
Z(3) = 0.03225247383350187
Z(5) = 0.003858069415480658
 32.803606 seconds (87 allocations: 5.885 GiB, 0.02% gc time)

元のプログラムの実行時間は 1196.311773 秒だったので，40 倍速近い。
40 倍と言っても 20 分が 30 秒になるのは体感的に随分違う。

文字列の分数式を「分数式」に変換する

文字列として定義（入力）された "353//283286119" のような分数式 を Rational{BigInt} 353//283286119 に変換する。

function Str2Rat(line::String)
    p = 0
    AA = zero(BigInt)
    BB = zero(BigInt)
    for i = firstindex(line):lastindex(line)
        if line[i] == '/'
            p = i
        end
    end
    if p == 0
        A = line
        B = "1"
    else
        A = SubString(line, 1, p - 2)
        B = SubString(line, p + 1, lastindex(line))
    end
    AA = parse(BigInt, A)
    BB = parse(BigInt, B)
    return AA // BB
end

色々と知らない関数がたくさんあるが，仕様だけに基づいて次のように書き換えてみた。

function Str2Rat2(line::String)
    p = findfirst('/', line)
    if isnothing(p)
        parse(BigInt, line) // BigInt(1)
    else
        parse(BigInt, line[1:p - 1]) // parse(BigInt, line[p + 2:end])
    end
end

findfirst() は第1引数が第2引数中になければ nothing を返すことに注意。

両者が同じ結果を返すことを確認。

Str2Rat("13//37") == Str2Rat2("13//37") # true
Str2Rat("353")    == Str2Rat2("353")    # true

ベンチマークテストの結果は，後者は前者の2割ほど速いということだが，そもそも実行時間が 2,300 ns なので，どっちでもよい。
強いて言えば，後者のプログラムのほうがわかりやすいかな?という程度だ。

line="353//283286119"
using BenchmarkTools

t1 = @benchmark Str2Rat(line);
minimum(t1)

BenchmarkTools.TrialEstimate: 
  time:             310.467 ns
  gctime:           0.000 ns (0.00%)
  memory:           448 bytes
  allocs:           19

t2 = @benchmark Str2Rat2(line);
minimum(t2)

BenchmarkTools.TrialEstimate: 
  time:             251.522 ns
  gctime:           0.000 ns (0.00%)
  memory:           304 bytes
  allocs:           13

ちなみに，eval(Meta.parse(line)) でも同じ結果が得られるが，ns が μs になるレベルで，とても遅い。

t3 = @benchmark eval(Meta.parse(line));
minimum(t3)

BenchmarkTools.TrialEstimate: 
  time:             68.375 μs
  gctime:           0.000 ns (0.00%)
  memory:           1.95 KiB
  allocs:           42