ScalaでProject Euler（28）

Problem 14

メモ化

配列を用意して一度計算したらそこに記憶していくとよいです。非常に速くなります。
配列を用意するので範囲が大きくなればその分大きなメモリが必要になりますが、そのときはメモ化の範囲を狭くするんでしょうね。

Benchmark

Benchmarkはこんな感じで使います。

import scala.testing.Benchmark

object TestCollatz extends Benchmark {
    def run() = solve
}

def solve() = ...

println (TestCollatz2.runBenchmark(5))

こうすると5回それぞれの実行時間をmsで返します。

List(1290, 1074, 1054, 996, 960)

だいたい最初は時間がかかるみたいですね。

import scala.testing.Benchmark

object TestCollatz extends Benchmark {
    def run() = solve
}

object Collatz {
    val memo = new Array[Int](M)
    
    def clear() = {
        for(n <- 0 to M - 1) memo(n) = 0
    }
    
    def f(n :Long) :Int =
        if(n == 1)
            1
        else if(n % 2 == 0)
            1 + apply(n / 2)
        else
            1 + apply(n * 3 + 1)
    
    def apply(n :Long) :Int =
        if(n < M && memo(n.toInt) > 0)
            memo(n.toInt)
        else {
            val m = f(n)
            if(n < M)
                memo(n.toInt) = m
            m
        }
}

def solve() = {
    Collatz.clear
    val a = Iterator.range(N / 2, N).map(n => (Collatz(n), n))
    println (a.max._2)
}

val N = 1e7.toInt
val M = 1e6.toInt
println (TestCollatz.runBenchmark(5))