[topic] 情報オリンピック2007年度国内本選問題2
Posted feedbacks - Scala
うーん、このコードをJavaに移植すると30倍速いんだけど…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | object P2 extends Application {
val s1 = readLine.toArray
val s2 = readLine.toArray
val len = new Array[Array[int]](s1.length, s2.length)
var max = 0
for(i <- 0 until s1.length) {
val c1 = s1(i)
for(j <- 0 until s2.length) {
val prev = if(i > 0 && j > 0) len(i-1)(j-1) else 0
len(i)(j) = if(c1 == s2(j)) prev + 1 else 0
max = Math.max(max, len(i)(j))
}
}
println(max)
}
|
関数型言語の良さを生かしたコードになりました。ちょっと感動！参照透過性を使っています。
1 2 3 4 5 6 7 8 9 10 11 | object P2_2 extends Application {
val s1 = readLine.toList
val s2 = readLine.toList
def lcs(s1:List[char], prev:List[int], max:int):int = {
if (s1.isEmpty) return max
val c1 = s1.head
val next = List.map2(s2, 0 :: prev)((c2, p) => if (c1 == c2) p + 1 else 0)
lcs(s1.tail, next, next.foldLeft(max)(Math.max(_, _)))
}
println(lcs(s1, List.make(s2.length, 0), 0))
}
|
遅くなる理由として次の2点があると思います。
- 非常に繰り返し回数の多いループにおいて forを使用していること(forは無名関数 を引数に取るメソッド呼び出しの構文糖なので 遅い)
- objectのすぐ内側で変数を定義しているため、 それらがフィールドになってしまっている (フィールドの参照はローカル変数の参照に 比べて遅い)
コードは汚くなりますが、元のコードを改造して 以下のようにすることで、自分の環境 (Athlon 64 3000+, Windows XP Professional, JDK 1.6.0)において、Javaに 移植した場合にかなり近い性能が出ることを 確認できました。ここで、
- { }で囲むことによって、s1やs2などをローカル 変数にすることで高速化
- 組み込みのループ構文であるwhileを使うことで 高速化
しているのがポイントです。一般的にはそれほど 気を使う必要は無いと思いますが、この問題の ようにループの回数が非常に多い場合には 有効なテクニックかと思います。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | object P2Tune extends Application {
{
val s1 = readLine.toArray
val s2 = readLine.toArray
val len = new Array[Array[int]](s1.length, s2.length)
var max = 0
var i = 0
while(i < s1.length) {
val c1 = s1(i)
var j = 0
while(j < s2.length) {
val prev = if(i > 0 && j > 0) len(i-1)(j-1) else 0
len(i)(j) = if(c1 == s2(j)) prev + 1 else 0
max = Math.max(max, len(i)(j))
j += 1
}
i += 1
}
println(max)
}
}
|
yukoba #5778() Rating0/0=0.00
中高生向けの情報オリンピック国内本選2007年度問題2です。
「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。本問では、制限時間1秒、メモリ制限64MBとなっています。
出題時はサンプルデータのみが公開され、採点は、採点データによる、自動採点にて行われます。
実際のコンテストでは、予選通過者48名が対象となっていて、100点満点中38点以上とった、16名が本選通過です。
[ reply ]