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…

Problem 468の計算量を見積もるときにこんな問題が思い浮かびました。 N以下を素因数分解したとき、素因数の個数の平均は？ 例えば、2、3、4 = 22、5なら1個、6 = 2 * 3なら2個とします。logNよりはずっと小さいと思われます。とりあえずコードを書いて調べ…

世界は2乗でできている 自然にひそむ平方数の不思議 (ブルーバックス)作者: 小島寛之出版社/メーカー: 講談社発売日: 2013/08/20メディア: 新書この商品を含むブログ (13件) を見るこの本に、オイラーのバーゼル問題に対する執念が書かれていました。バーゼ…

Problem 226この曲線は高木曲線としても知られています。高木とはもちろん高木貞治のことです。 この問題を解くにあたり、連続性と微分不可能性についての証明を考えたのですが、めんどうなのでここには書きません。 フォーラムに書きました。

Problem 227 フォーラムに書きました。

Problem 220 forumに書きました。

Pythonでは整数は大きくなると勝手に多倍長整数として表すので誤差は出ませんが、浮動小数点数を介すると途端に誤差が発生します。Project Eulerで特に問題になるのは、整数の平方根の計算です。すなわち、 ⌊√n⌋ の計算です。この計算は整数nを浮動小数点数…

Problem 303フォーラムを見てください。

Problem 208デバッグが大変だった。

Problem 202考え方は簡単ですが、コードがなかなか書けなくて。

リストの部分リストを得るとき、つぎのようにします。 a = range(5) # [0, 1, 2, 3, 4] a[1:3] # [1, 2] range(1, 3)に対応しています。同様にステップ幅も指定できます。 a[1:4:2] # [1, 3] a[3:0:-1] # [3, 2, 1] これもrange(1, 4, 2)、range(3, 0, -1)に…

in演算子、便利ですよね。こんな感じです。 a = [ 1, 2, 3 ] print 2 in a # True C#なら、 var a = new int[] { 1, 2, 3 }; Console.WriteLine(a.Contains(2)); // True ちょっとうっとうしい。C++に至っては、 int a[] = { 1, 2, 3 }; std::cout << (std::…

例えば、こんなコードがあるとします。 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.…

Problem 36この問題は、単に2と10の両方の基数で回文数になるかを調べるという単純な方法でも十分速いです。自然数nの回文数の判定はO(logn)の計算量なので、NまででO(NlogN)の計算量です。回文数を生成するほうが速いです。10進で回文数を生成して、2進で回…

Project Eulerでしばしば、○○を満たすN未満の最大の整数を求めよ、といった問題を見かけます。例えば、Problem 26です。この問題を読み替えると、「10がFpの生成元になるN未満の最大の素数を求めよ」とほぼなります。こういう問題は、N-1から順番に整数が題…

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

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

剰余類 まずは剰余類の説明からします。例えば15の剰余で考えます。2と17と32は15で割ると余りが2になります。これらは同じとみなして剰余類と呼びます。 H0 = { …, -15, 0, 15, 30, … } H1 = { …, -14, 1, 16, 31, … } H2 = { …, -13, 2, 17, 32, … } … -13…

分割数というのは、例えば5を自然数で分割することを考えます。同じ数を何度も使ってもよいですが、順序違いは区別しません。そうすると、 5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1の7通りあります。これを p(5)…

昨日のProblem 405に関連するが解くのには必要のない情報。 10e乗の剰余は、Pythonにはpow関数が用意されて簡単に計算できます。例えば、3の1010乗の123456789の剰余は、 pow(3, 10 ** 10, 123456789)で求められます。しかし、指数が大きくなってくると段々…

Problem 169 コードはフォーラムに。

エラトステネスのようなリストを使う計算はPythonでは非常に遅いですが、Numpyを使うと速くなります。http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-pythonに書かれてあるprimesfrom2toという関数です。 import nu…

Problem 389これは確率計算をする問題なので、いつものように母関数の計算をすることになります。しかし、多項式をリストとして計算すると、Pythonは非常に遅いんですよね。そんなとき、NumPyを使うと劇的に速くなります。ダウンロードはこのあたりから。 ht…