ScalaでProject Euler（11）

Problem 4

時間計測

この問題で2通りの解法を示しましたが、どちらが速いでしょう。時間計測はこんな感じです。

val t0 = System.currentTimeMillis
val N = 3
val M = pow(10, N)
println (palindrome(N).filter(is_product).head)
println ((System.currentTimeMillis - t0) + "ms")

大きな桁数まで計算するために必要な部分はIntをLongに修正しました。

桁数	回文数→積	積→回文数
3	359	422
4	1750	422
5	143547	532

単位はmsです。積の判定が雑だからこういう結果になるのでしょうね。速い方法はこのあたりにも書いています。
ついでにPythonとも比べてみましょう。この問題は比較しにくいので、単にPriorityQueueの性能を見るコードにします（コードは下）。
Scalaは1900ms、Pythonは13000msくらいでした。ちなみにScalaは300msくらいのオーバーヘッドがあるようです。

import Stream.cons
import scala.collection.mutable.PriorityQueue

def pow(n :Int, e :Int) :Int =
    if(e == 0) 1 else n * pow(n, e - 1)

def product_stream(pq :PriorityQueue[(Long,Int,Int)]) :Stream[Long] = {
    val (p, m, n) = pq.dequeue
    pq.enqueue((m.toLong * (n - 1), m, n - 1))
    if(m == n)
        pq.enqueue(((m - 1).toLong * (m - 1), m - 1, m - 1))
    cons(p, product_stream(pq))
}

val t0 = System.currentTimeMillis
val N = 3
val M = pow(10, N) - 1
val pq = new PriorityQueue[(Long,Int,Int)]
pq.enqueue((M.toLong * M, M, M))
println (product_stream(pq).filter(10000 >).head)
println ((System.currentTimeMillis - t0) + "ms")

from itertools import *
from Queue import PriorityQueue
import time

def gen_product(pq):
    while True:
        p, m, n = pq.get()
        pq.put((-m * (n - 1), m, n - 1))
        if m == n:
            pq.put((-(m - 1) * (m - 1), m - 1, m - 1))
        yield -p

t0 = time.clock()
N = 3
M = 10 ** N - 1
pq = PriorityQueue()
pq.put((-M * M, M, M))
print next(ifilter(lambda n: n < 10000, gen_product(pq)))
print time.clock() - t0