読者です 読者をやめる 読者になる 読者になる

ScalaでimmutableなPriorityQueueを作ってみたよ

Programming Scala Algorithm

みんな大好きScalaですが、immutableなPriorityQueueが標準で無かったので試しに作ってみました。想定バージョンはScala 2.7.7です。

Immutable PriorityQueue in Scala — Gist

データ構造

今回は優先順位つきキューの実装に、Leftist Heapというヒープを使いました。これは左側の高さが右側よりもやや高くなるようにヒープを調整するもので、「Purely Functional Data Structures」ではかなり先頭のほうで紹介されている簡単なデータ構造です。だいたいの操作をO(log n)でやります。

ちなみにヒープというのは、親の要素が子よりも小さいような木構造のことです。

クラス構成

TreeSetやQueueの実装を見ながら、よりシンプルなクラス構成にしてみたらこうなりました。

関数型チックなデータ構造を作るときは、Scalaでは、「抽象クラスを用意して複数のケースクラスに継承させる」という手法がよく使える気がします。

  • object PriorityQueue…ヒープ管理用の補助メソッドと、公開用のユーティリティーメソッドを用意しました。
  • class PriorityQueue[A]…ヒープです。EmptyとTreeの2つのサブクラスが実装する抽象クラスです。Seq[A]を継承します。
  • package priorityqueue
    • case class Empty[A]…空のヒープです。
    • case class Tree[A]…分岐です。自身の要素と2つのサブヒープを持ちます。

ヒープとして必要なmergeとかを実装したら、あとはSeq[A]を継承させて、必要なlength,apply,elementsなんかを実装しました。

で完成。

あと

Vimに飽きたのでちょっとEmacsを使ってみました。慣れない。

某氏から1k円で譲り受けたオライリーEmacs本を見ながらやっていきます。