LL脳がscalaの勉強を始めたよ その66
Scalaコップ本も19章に入っていきますよー、19章は型のパラメーター化についてです。型のパラメーター化ってのは、型を作るYO!って解釈でいいですかね？
今回は型のパラメーター化について関数型待ち行列クラスを例に見ていきますかねー
関数型待ち行列
関数型待ち行列の特徴
とりあえずサンプルとなる関数型待ち行列についてです。関数型待ち行列は次の３つの操作を持つデータ構造とのことデス。
関数型待ち行列はイミュータブルな構造なので、appendによる要素の追加処理は新しい待ち行列を生成することになるの必要がありますね。
Listを使った実装
上記関数型待ち行列の特徴はリスト構造に似ているのですが、リストでの連結操作::が先頭に要素を結合するのに対して関数型待ち行列はappendで末尾に結合する部分が異なりますね。
ただし、リストにはリスト同士を結合する:::メソッドがあったのでこいつを利用した単純な実装を試してみますかね
class SlowAppendQueue[T](elems:List[T]){ // headはList.headを利用 def head = elem.head // tailもList.tailから生成 // イミュータブルなので新しいオブジェクトを返します def tail = new SlowAppendQueue(elems.tail) // appendでは追加する要素をリストとして // ::: メソッドで結合してやりますね def append(x:T) = new SlowAppendQueue(elems ::: List(x)) }
…ただし上記実装ではappend演算で待ち行列の要素数に比例した実行時間が必要になるみたいです。なのでappendを高速に行うために、逆順にしたリストの要素を渡すようにする実装を考えてみます。
// elems の要素を逆順したものをsmeleを利用します val smele = elems.reverse class SlowHeadQueue[T](elems:List[T]){ // 末尾を取ってくれば先頭要素のはず def head = smele.last // 末尾以外を取ればtailの動作になるハズ def tail = new SlowHeadQueue(smele.init) // 連結処理をつかって高速にできるはず def append(x:T) = new SlowHeadQueue( x :: smele ) }
逆順を利用するもののappend処理自体は要素数に比例しない高速性を手にれてやりましたよ…ただhead, tailは要素数分の処理時間が必要になりますね(´・ω・｀)
脱線、脱線
…ところで若干コストはかかるけど、こういうふうにすれば順序気にしなくてよくね？と思ったのでちょろっと
class SlowHeadQueue[T](elems:List[T]){ // elems の要素を逆順したsmeleを生成 val smele = elems.reverse // 末尾を取ってくれば先頭要素のはず def head = smele.last // 末尾以外を取ればtailの動作になるハズを逆転 def tail = new SlowHeadQueue(smele.init.reverse) // 連結処理をつかって高速にして逆順 def append(x:T) = new SlowHeadQueue((x :: smele).reverse) }
まあ、先の課題もあるだろうから…なんだろうけども(´・ω・｀)
以上、閑話休題
上記2つの例を上手く組み合わせればいいじゃないか
2つの実装に向き不向きがあるのだから正順、逆順の2つの待ち行列で処理すればよくね？っていうのが次の実装みたいです。
class Queue[T]( // 待ち行列の正順リスト private val leading:List[T], // 待ち行列の逆順リスト private val trailing:List[T] ){ // 2つのリストの同期をとる処理です private def mirror = { if(leading.isEmpty) new Queue(trailing.reverse, Nil) else this } // 同期をとった正順リストから先頭要素を取りますデス def head = mirror.leading.head // 同期をとった正順リストからtailを // 逆順リストはそのままの待ち行列を返します def tail = { val q = mirror new Queue(q.leading.tail, q.trailing) } // 逆順リストについて先頭（待ち行列的には末尾）に要素を追加します def append(x:T) = new Queue(leading, x :: trailing) }
…確かに内部的な（メソッドのための）構成はこれで矛盾はないし、計算量も抑えられるんだろうけども…leadingとtrailingの同期が常に取れているわけではないし、他のメソッドを付け加えるときの呼び出しも若干めんどくさいなぁ(´・ω・｀)
とりあえずこんな感じでどうだろう(´・ω・｀)
思いつきで書いてみたものの…reverseで結構コストかかるなぁ。呼出は楽でいいのかもだけども(´・ω・｀)
class Queue[T]( leads:List[T]){ private val leading:List[T] = leads private val trailing:List[T] = leads.reverse // 2つのリストの同期をとる処理です private def mirror_lead = new Queue(trailing.reverse, trailing) private def mirror_trail = new Queue(leading, leading.reverse) // 同期をとった正順リストから先頭要素を取りますデス def head = leading.head // 同期をとった正順リストからtailを // 逆順リストはそのままの待ち行列を返します def tail = new Queue(leading.tail) // 逆順リストについて先頭（待ち行列的には末尾）に要素を追加します def append(x:T) = new Queue((x :: trailing).reverse) }
ただ上のオレオレ実装はクラスの考え方に偏ってる気がするので...型ってことをベースにするともっと違うのかも…と思ってみたり(´・ω・｀)とりあえず先に進んでみてからだな
