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)のようだった。

Project Euler 669

https://projecteuler.net/problem=669

203着。
久しぶりにやった。
変わった問題だが、すぐになんとなくわかる。
でも、そこからは怪しい。解けるんだけど、本当にこれでいいのか。
きっちり検証すれば正しいかどうかわかるが、そうしなくてもなんとなく解ける。

秀丸で開いたファイルのフォルダにUbuntuを開いて移動する

これは、昔からコマンドプロンプトでよくやっていた。例えばPythonのコードを書いて、さあ実行しようという時に、コマンドプロンプトを起動して、Change Directoryする。しかし、わざわざ分かっているディレクトリに手動で移動するのは面倒ではないか。

コマンドプロンプトには/Kというオプションがあって、そのあとに書かれたコマンドをコマンドプロンプトを開いた後に実行する。なので、

cmd.exe /k cd dicrectory

とすれば、コマンドプロンプトが起動してそのディレクトリに移動する。

TeraTermには起動時にマクロを実行する機能があって、ログインして、子サーバにSSHでログインして、Sambaで開いていたファイルのフォルダにChange Directoryするようにしていた。

しかし、Windows 10のUbuntuは簡単にはうまくいかない。今回一念発起してその機能を実現させたので紹介する。

秀丸マクロ

JScriptで書かれたスクリプトをWindows Script Hostで実行する。その際、秀丸のファイルのフォルダをdirectory2で拾って、引数にする。

パスの変更

例えば、Windowsの「C:\Users\user」というパスはUbuntu上では「/mnt/c/Users/user」となるので、この変換を行う。

function convert_windows_dir_into_Linux_dir(dir) {
	var v = dir.split("\\");
	v[0] = "/mnt/" + v[0].charAt(0).toLowerCase();
	return v.join("/");
}

Ubuntuの実行

Ubuntuの実行はstartコマンドでおこなう。

var Shell = WScript.CreateObject("WScript.Shell");
var command = "cmd.exe /c start ubuntu";
Shell.Run(command, 1, true);

Ubuntuが開いたらChange Directoryしたいが、やり方がわからない。しょうがないので、クリップボードを使ってペーストする。

clipというコマンドがあるので、そこに流し込む。例えばコマンドプロンプトで、

echo abc| clip

と打つと、クリップボードに"abc\n"が貼り付けられる（どうしても改行コード込みになってしまうようだ）。これを利用して、

Shell.Exec("cmd /c echo cd " + Linux_dir + "| cmd /c clip");

として、Linux形式に変換したディレクトリをクリップボードに貼り付ける。
このあと、SendKeysでそのディレクトリをUbuntuに貼り付けられるようにUbuntuの設定を変更する。Ubuntuを開いて、左上をクリックして「プロパティ」から設定画面を表示させる。

「編集オプション」の「Ctrlキー ショートカットを有効にする」をチェックすればよさそうだが、なぜかそれではうまくいかない。ここでは、「Ctrl+Shift+C/Vをコピー/貼り付けとして使用する」をチェックする。

そうして、SendKeysを使う。

WScript.Sleep(1000);
Shell.SendKeys("+^V");

この秀丸マクロをショートカットキーに登録しておけばよいだろう。
サクラエディタ等でも同様に可能だと思われる。

JuliaでProject Euler(22)

Problem 42

https://projecteuler.net/problem=42

function read_names(path)
    open(path, "r") do fp
        for line in eachline(fp)
            return [ s[2:length(s)-1] for s in split(line, ",") ]
        end
    end
end

function is_square(n)
    return Int(floor(sqrt(n)))^2 == n
end

function is_triangle(n)
    # x^2 + x = 2n
    # x = (-1 + sqrt(1 + 8n)) / 2
    return is_square(1 + 8n)
end

function word_score(word)
    return sum(Int(c)-Int('A')+1 for c in word)
end

function read_words(path)
    open(path, "r") do fp
        for line in eachline(fp)
            return [ replace(s, "\"" => "") for s in split(line, ",") ]
        end
    end
end

function e042(path)
    words = read_words(path)
    return sum(1 for word in words if is_triangle(word_score(word)))
end

path_names = ARGS[1]
println(e042(path_names))

Float64をInt64に変換するとき、わざわざ小数点以下が0の浮動小数点数にしてからでないと変換できない。

replaceの引数は、文字列と文字列ではなく、文字列のPair。古いバージョンだと違うので注意。

JuliaでProject Euler(21)

Problem 33

https://projecteuler.net/problem=33

分数は、次のように書く。

julia> f = 4//6
2//3

julia> typeof(f)
Rational{Int64}

julia> numerator(f)
2

julia> denominator(f)
3

JuliaでProject Euler(20)

Problem 25

https://projecteuler.net/problem=25

function add(v1, v2)
    if length(v1) > length(v2)
        return add(v2, v1)
    end
    v3::Array{Int} = []
    carry = 0
    for k in 1:length(v1)
        n = v1[k] + v2[k] + carry
        carry = div(n, 10)
        d = n % 10
        push!(v3, d)
    end
    
    for l in length(v1)+1:length(v2)
        n = v2[l] + carry
        carry = div(n, 10)
        d = n % 10
        push!(v3, d)
    end
    if carry > 0
        push!(v3, carry)
    end
    return v3
end

fibs() = Channel() do c
    a, b = [1], [1]
    push!(c, a)
    while true
        a, b = b, add(a, b)
        push!(c, b)
    end
end

function e025(N)
    x = first(Iterators.filter(x -> length(x[2]) == N, enumerate(fibs())))
    return x[1]
end

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

fibsの部分は次のようにも書ける。

function fibs(c::Channel)
    a, b = [1], [1]
    push!(c, a)
    while true
        a, b = b, add(a, b)
        push!(c, b)
    end
end

function e025(N)
    x = first(Iterators.filter(x -> length(x[2]) == N,
                            enumerate(Channel(c -> fibs(c)))))
    return x[1]
end

関数っぽくなるが、だいぶ長くなる。

JuliaでProject Euler(19)

Problem 22

https://projecteuler.net/problem=22

function read_names(path)
    open(path, "r") do fp
        for line in eachline(fp)
            return [ s[2:length(s)-1] for s in split(line, ",") ]
        end
    end
end

function name_score(name)
    return sum(Int(c)-Int('A')+1 for c in name)
end

function e022(path)
    names = sort(read_names(path))
    return sum(k*name_score(name) for (k, name) in enumerate(names))
end

path_names = ARGS[1]
println(e022(path_names))

ファイルを読むのは上のよう。Pythonに似ているといえば似ている。