AlignmentのBacktrackのときに、文字を前に追加しなければならないが、当然後ろに追加して最後に文字列を逆にする方が速いと思える。しかし、このようなコードで、 import sys import time def f_add_to_head(N): s = '' for _ in range(N): s = 'c' + s ret…

Problem 490で作ったごり押しコードをg++でコンパイルして動かしてみた。バージョンは4.8.4-2らしい。このコードは本当に四則演算しか行っていない、STLも使っていない単純なものである。さすがにこれは速くならないと思ったら、 Win(MSVC) 2208s Ubuntu(g++)…

メモリの使用量を見てみる。 まずはlistから。 #!/usr/bin/python import time a = [ n + 1 for n in xrange(10 ** 7) ] time.sleep(10) Python(Win) 160MB PyPy(Win) 40MB Python(Ubuntu) 320MB PyPy(Ubuntu) 80MBint64だから倍になるのはわかる。 #!/usr/b…

32ビットを超える整数UbuntuのPythonが速かったが、そうでない場合はどうだろう。簡単な例で確かめてみる。 #!/usr/bin/python import sys import time def H(n): return sum(n / k for k in xrange(1, n + 1)) t0 = time.clock() print H(10 ** 8) print >>…

PyPyは、たいていの場合Pythonのコードそのものを動かしてもPythonより数倍速くなる。単純な計算ならC++並みに速くなる。 しかし、辞書を扱う部分が主になると途端に遅くなり、Pythonより遅くなる。 UbuntuのPython/PyPyではどうなるのか調べてみた。 #!/usr…

以前に、WindowsがBashをサポートする、という記事があった。これがあればPythonが速くするはずだ。なぜなら、Windows版のPythonは32ビットを超えると多倍長整数とされてしまうが、LinuxのPythonなら64ビットまでならint扱いになるはずだからだ。ここで、Pyt…

例えば、こんなコードがあるとします。 def divs1(N): return [ N / n for n in xrange(1, N + 1) ] N = 10 ** 8 print sum(div1(N)) 内包表記ですね。これを間違ってもappendを使って次のように書いてはいけません。 def divs2(N): a = [] for n in xrange(…

例えば素因数分解を与えて約数を全て列挙するコードを書きます。こんな感じでしょうか。 def pows(n, e): yield 1 q = 1 for _ in xrange(e): q *= n yield q def divisors(fs): if not fs: yield 1 else: p, e = fs[0] qs = pows(p, e) for n in divisors(f…

Problem 1を考えます。ふつうに書くとこんな感じです。 N = 10 ** 8 # オリジナルは1000 print sum(n for n in xrange(1, N) if n % 3 == 0 or n % 5 == 0) この問題はプログラマを関数型に導くためのものなのです。 これを動かすと、Pythonで13秒、PyPyで3.…

PyPyは同じソースを動かしてもPythonよりたいてい速いのですが、遅くなることもあります。その対処法がいくつかあるので紹介していきます。今回はリストのソートです。こんなコードを動かしてみます。 from itertools import * import time def gen_S(): S =…

「これまでで最大の素数」を発見 << WIRED.jp久しぶりに新たなメルセンヌ素数が発見されたようです。メルセンヌ数は、 Mn = 2n - 1 という形をしているのですが、なぜこの形の素数を求めようとするかというと、非常に高速な素数判定法があるからです。さて、…