Project Euler 681

https://projecteuler.net/problem=681

107着。

フォーラムで解けなかった問題、らしい。記憶になかった。
SymPyを使いながら計算をしたら、きれいな形になった。
それを工夫して組んでみたらやけに遅かったので、素直に組んだらPyPyで4分くらいだった。
どうやったら速くなるのだろう。

JuliaでC++のtemplateのようなものを実現する

Julia

Juliaで例えば、グラフのエッジを逆向きにするグラフを作る関数を書くとする。

function main()
    graph = Dict{Int,Vector{Int}}()
    for v in 1:3
        graph[v] = collect(v+1:4)
    end
    println(graph)
    rev_graph = reverse_graph(graph)
    println(rev_graph)
    println(typeof(rev_graph))
end

function reverse_graph(graph)
    rev_graph = Dict()
    for pair in graph
        println(pair)
        v1 = pair.first
        for v2 in pair.second
            if haskey(rev_graph, v2)
                push!(rev_graph[v2], v1)
            else
                rev_graph[v2] = [v1]
            end
        end
    end
    return rev_graph
end

main()

こうすると、このrev_graphの型は、

Dict{Any,Any}

となってしまう。

Dict()

と書いているから当然だ。
しかし、型を書くのは面倒で馬鹿らしい。第一、型を明示的に書いてしまったら、その型でしかこの関数は使えなくなってしまう。C++のtemplateのようなことはできないのだろうか。
それ以前に、型に別名をつけることはできないのか？
調べてみると、型パラメータというもので実現できることが分かった。

const Graph{T} = Dict{T,Vector{T}}

これで、型を短く書くことができる。次のように使える。

graph = Graph{Int}()

これで、

Dict{Int64,Array{Int64,1}}

という型になる。

const Graph{T} = Dict{T,Vector{T}}

function main()
    graph = Graph{Int}()
    for v in 1:3
        graph[v] = collect(v+1:4)
    end
    println(graph)
    rev_graph = reverse_graph(graph)
    println(rev_graph)
    println(typeof(rev_graph))
end

function reverse_graph(graph::Graph{T})::Graph{T} where {T}
    rev_graph = Graph{T}()
    for pair in graph
        println(pair)
        v1 = pair.first
        for v2 in pair.second
            if haskey(rev_graph, v2)
                push!(rev_graph[v2], v1)
            else
                rev_graph[v2] = [v1]
            end
        end
    end
    return rev_graph
end

main()

AtCoder Beginner Contest 138 E

https://atcoder.jp/contests/abc138/tasks/abc138_e

なんということもない問題だ。この位置にいる時に、この文字は次にどこにあるかをテーブルにしておけばよい。
しかし、Pythonでどうしても時間切れになる。PyPyでもなぜか速くならない。
じゃあC++で、とも思ったが、それでは何の勉強にもならない。仕方なく、Juliaを使うことにした。
しかし、そんなに簡単に書けない。配列のインデックスが0から始まるのが最も大きい。気を付けているつもりでも0でアクセスしている。
それから、Juliaのバージョンは0.5.0だという。手元にあるのは、1.2.0。文字列の中に文字列がどこにあるかをネットで検索すると、searchという関数らしい。しかし、動かない。よく見ると、これは0.6.0での話だった。Juliaはバージョンで全然仕様が違うのだ。ネットには0.6.0の情報が多いようだ。最近日本ではJuliaは流行っていないのだろうか。それはともかく、AtCoderのコードテストでは動いた。
しかし、このコードテストが使いづらいのだ。ファイルを開くでファイルを指定して読み込むと、前のコードが残っていて新しいコードがなかなか反映されない。仕方ないので、ブラウザ上で直して、テキストファイルでも同じ修正をする。
結局、Juliaで悠々と通った。

PythonとPyPyで文字を追加する速度が全然違う

Python PyPy

AlignmentのBacktrackのときに、文字を前に追加しなければならないが、当然後ろに追加して最後に文字列を逆にする方が速いと思える。

しかし、このようなコードで、

import sys
import time

def f_add_to_head(N):
	s = ''
	for _ in range(N):
		s = 'c' + s
	return s

def f_add_to_tail(N):
	s = ''
	for _ in range(N):
		s = s + 'c'
	return s[::-1]

t0 = time.clock()
N = int(sys.argv[1])
f_add_to_head(N)
print >>sys.stderr, time.clock() - t0
t0 = time.clock()
f_add_to_tail(N)
print >>sys.stderr, time.clock() - t0

PythonとPyPyで速度が全然違った。

$ python add_head.py 300000
6.40625
0.015625

$ pypy add_head.py 300000
4.03125
4.0

ここで、pythonは2.7.15で、printを修正したPython3.6.8でも変わらなかった。
Pythonでは、前に追加の場合、O(N^2)より遅く、後ろに追加の場合、O(N)のようだった。PyPyはともにO(N^2)のようだった。