Hatena::ブログ(Diary)

純粋関数型雑記帳 このページをアンテナに追加 RSSフィード Twitter

このページはHaskellを愛でるページです。
日刊形式でHaskellなどについての記事をだらだらと掲載しとります。
2004 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 07 | 08 | 09 | 11 |
2007 | 03 | 04 | 05 | 07 | 08 | 09 | 12 |
2008 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 03 | 05 | 06 | 09 | 10 | 11 | 12 |
2010 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 12 |
2011 | 01 | 02 | 05 |
本体サイト

2009年09月09日(水) ICFP Programming Contest 2009

[]ICFP Programming Contest 2009 ICFP Programming Contest 2009を含むブックマーク ICFP Programming Contest 2009のブックマークコメント

すっかり文章を書くのを忘れてたのをICFPが終わって思い出したので、社内向けに作ったスライドを張ってお茶を濁す。書き換えたい部分もあるが面倒なのでオリジナルまま。

動画。手振れがひどい。なかなか辛い回り方をしているなあ。

2009年09月08日(火) 競技プログラミング in Scala

素人なのであてにはならないと思いますが。

[Scala]競技プログラミング in Scala  [Scala]競技プログラミング in Scalaを含むブックマーク  [Scala]競技プログラミング in Scalaのブックマークコメント

Scalaで競技プログラミングを行う際に気をつけることの列挙。

なぜScalaなのか?

  • 速い
  • 静的型付
  • 字面がC++よりましなのでC++よりは速く書けるであろうという期待
  • 同じ理由でJavaよりは速く書けるであろうという期待
  • OCamlよりも基本的なライブラリが充実しているので速く書けるであろうという期待
  • Haskelは配列を弄繰り回すような場合にコードが冗長になる傾向があるのでそういう場合に比較して速く書けるであろうという期待

プログラム全体の構造

Scalaプログラムの実行方法には二通りある

注意すべきは、どちらの方法をとるかで書くべきプログラムが変わることである。scalaコマンドで直接実行する場合、トップレベルに書かれた式が実行される。scalacコマンドコンパイルする場合、トップレベルには定義しかかけない。つまり、クラスを作らなければならない。コードは次のようになる。

object A extends Application{
  ... hoge hoge
}

直接実行する場合、クラス定義しただけでは実行されないので、これとは逆にクラス定義してはいけない。

書くべきコードコンパイルする場合のほうが多い。また、実行させるのに必要なコマンドも長くなる(さらに悪いことに、コンパイルした場合、ラムダ式に応じて匿名の.classファイルが大量に生成される傾向にある)。あえてコンパイルする理由があるとすれば実行速度だろう。しかし、私の見たところによると、コンパイルして実行速度が速くなるということはなかった。直接実行する場合も内部的にはきっちりコンパイルして実行しているようだ(たぶんそうなので、直接実行する場合にもscalacする場合と同じぐらい起動に時間がかかる)。このことを鑑みるに、競技プログラミングであえてscalacを行う理由はない。プログラムトップレベルに書き、scalaコマンドで実行するのが良い。

入出力

典型的な競技プログラミング課題標準入力からテストセットを入力し、結果を標準出力に書き出す必要がある。Scala入力をするにはいくつかの方法がある。

  • java.io.以下のBufferedReaderなどを使う
  • scala.io.Sourceを使う
  • java.util.Scannerを使う

一つ目の方法は旧来のJavaで一般的な方法だが、冗長に過ぎる。scala.io.Sourceはインターフェースが使いにくい。Java1.5以上であればScannerを使うのがよろしい。

出力はSystem.outを使う方法と、scalaの標準ライブラリを使う方法がある。前者は、単にSystem.out.とタイプするのが面倒なこと(これはimportすればよいのだが)に加え、JavaクラスであるObject引数をとる関数にはscalaの暗黙の型変換がうまく働かないという問題がある。

System.out.printf("%d\n", 123) // NG
System.out.printf("%d\n", int2Integer(123)) // OK

この理由から、scala組み込みのを使うべきである。

printf("%d\n", 123) // OK

なお、scalaprint/printlnには任意個の引き数が渡せて、その場合にはタプルの出力と同じになるので、デバッグに便利である。

データ構造

newでの生成は初期値が指定できない上に要素の型を指定しなくてはならず大変使いにくい。コンパニオンオブジェクトのfromFunctionが便利。

val aa = Array(1, 2, 3) // リテラル
val bb = Array.fromFunction(i=>...)(n) // 添え字で初期化できる
val cc = Array.fromFunction(_=> -1)(n) // 初期値が決まっているなら
val dd = Array.make(n, -1) // これでもいい
val ee = Array.fromFunction((i, j)=>...)(n, m) // 多次元配列も
val ff = Array.make(n, Array.make(m, -1)) // これはだめ

普通リスト

の二つのtraitがある。前者は順序を保障しない。後者は保障する。実装しているクラスは次のとおり

    • scala.collection.immutable.HashMap extends Map
    • scala.collection.immutable.ListMap extends Map
    • scala.collection.immutable.TreeMap extends SortedMap
    • scala.collection.immutable.TreeHashMap extends Map
    • scala.collection.immutable.UnbalancedTreeMap extends Map
    • scala.collection.immutable.IntMap extends Map
    • scala.collection.immutable.LongMap extends Map
    • scala.collection.mutable.HashMap extends Map
    • scala.collection.mutable.LinkedHashMap extends Map
    • scala.collection.mutable.OpenHashMap extends Map

などがある。たくさんあるが、

    • immutable.ListMapと、immutable.UnbalancedTreeMapは存在価値が不明
    • immutable.TreeHashMapはHashMapでいい
    • mutable.LinkedHashMapとOpenHashMapはmutable.HashMapでいい

おおよそ次のような基準で選ぶと良い。

    • 順序付ならimmutable.TreeMap一択
    • キーが整数かつ非負で順序つきならimmutable.IntMap or LongMap
      • これらはunsignedに順序が付くようなので、非負の数しか入れないならSortedMapとして使える
      • HashMapよりは遅いがTreeMapよりはだいぶ速い
    • パフォーマンスが気になるならmutable.HashMap
    • それ以外ならimmutable.HashMap
      • (実際のところimmutable.HashMapは十分速い)

なお、scala.collection.immutable.Mapとmutable.Mapコンパニオンオブジェクトはそれぞれimmutable.HashMapとmutable.HashMapを生成する。

mapと同様に順序付きとそうでないものの二つのtraitがある。

    • scala.collection.immutable.HashSet extends Set
    • scala.collection.immutable.ListSet extends Set
    • scala.collection.immutable.TreeSet extends SortedSet
    • scala.collection.mutable.HashSet extends Set
    • scala.collection.mutable.LinkedHashSet extends Set

なぜかmapよりもバリエーションが少ない。IntMap相当のものがないことを除けば、選定基準はMapと同じでいいだろう。

  • MultiMap

基本的にMap[A, Set[B] ]で扱う。便利のためにそのようなTraitがscala.collection.mutable.MultiMapに用意されている(なぜかmutableだけ)。

val x = new HashMap[Int, Set[Int] ] with MultiMap[Int, Int] // こうすると
x.add(1, 2)
x.add(1, 3)
x.entryExists(1, (_ = 2))
x.remove(1, 2) // こういうメソッドが使える

当然ながらimmutableにはくっつけられない。

キーも値も重複するものを許すものは用意されていない。

  • MultiSet

特に用意されているものはない。Map[A, Int] などで出現回数を数えるぐらいだろうか。

  • PriorityQueue

scala.collection.mutableにある。比較関数は変えられない。

小技

val sc = new java.util.Scanner(System.in)
val a, b, c = sc.nextInt() // a, b, c の順に整数が三つ読み込まれる
val arr = Array.fromFunction(_=>sc.readInt())(n) // arr(0) .. arr(n-1) に順に整数が読み込まれる
val mat = Array.fromFunction((_,_)=>sc.readInt())(n, m) // arr(0)(0) .. arr(0)(m-1) .. arr(n-1)(m-1) に順に整数が読み込まれる
val words = sc.nextLine() split " +"
  • ジェネレータは一回しか評価されない
for (caseno <- 1 to sc.nextInt()){
  ...
  printf("Case #%d: ...", caseno, ...)
}
  • パーザコンビネータが標準でついてるので、使えるようにしておくべし

気をつけること

型推論が弱いので、要所要所で型を書いてやる必要がある。書く必要がある場所の判定にはScala型推論アルゴリズムを熟知している必要があるので、Programming in Scalaには、コンパイラに怒られたらその都度注釈を入れよ、の様に書いてあった。しかし、いちいちそれでは時間をロスするので、注釈が必ず必要な簡単な場所は覚えておく。

  • for式の型

for式でyieldすると、最初のジェネレータと同じ型のコレクションが返る。ListならList、ArrayならArrayであるが、SetだとSetになって、要素がつぶれてしまうことがあるので注意。