LL脳がscalaの勉強を始めたよ その53
Scalaコップ本の16章の続きをやってイキマス。今回はリストの１階メソッドについての後半をやっていきますよー
要素の選択：applyとindices
リストの各要素にダイレクトにアクセスするにはapplyメソッドを使いますねー
// 添字３の要素にアクセスします scala> List(1,2,3,4,5).apply(3) res4: Int = 4 // 添字4の要素にアクセスします scala> List(1,2,3,4,5).apply(4) res5: Int = 5 // Listに要素数を指定した場合は暗黙的にapplyメソッドが適用されます scala> List(1,2,3,4,5)(3) res6: Int = 4
実際のところapplyメソッドはdropとheadの組み合わせらしいので添字指定の要素数分のコストが掛かるみたいです。なので配列のようなapply的アクセスはあまりしないらしいとのことですね
List(1,2,3,4,5).apply(3) == List(1,2,3,4,5).drop(3).head
ちなみにListの添字要素はindicesメソッドを使って取り出せるみたいですね
// 添字要素をリスト型で取り出します scala> List("a","b","c","d","e").indices // 該当のリストの添字は次のようになりますネ res8: List[Int] = List(0, 1, 2, 3, 4)
リストのジッパー操作：zip
2つのリストをまとめる操作としてzipメソッドがあるみたいですねー
// 2つのリストの各要素をまとめたタプルを要素とするリストを返します scala> List(1,2,3,4,5).zip(List("a","b","c","d","e")) res9: List[(Int, java.lang.String)] = List((1,a), (2,b), (3,c), (4,d), (5,e))
ちなみにタプル用のペアが作られない要素は捨てられるみたいです
// 対応するペアのない4, 5が捨てられます scala> List(1,2,3,4,5).zip(List("a","b","c")) res10: List[(Int, java.lang.String)] = List((1,a), (2,b), (3,c)) // 対応するペアのないc, d, eが捨てられます scala> List(1,2).zip(List("a","b","c","d","e")) res11: List[(Int, java.lang.String)] = List((1,a), (2,b))
こいつとindicesメソッドを組み合わせるとリストの添字と要素からペアを作ることができます
// 添字と要素のペアから構成されるリストを返します scala> List("a","b","c","d","e").indices zip List("a","b","c","d","e") res12: List[(Int, java.lang.String)] = List((0,a), (1,b), (2,c), (3,d), (4,e))
ただ同じようなことをするならzipWithIndexメソッドを使うのが効率的だそうです
// 結果は同じだけど書くの楽ちん scala> List("a","b","c","d","e").zipWithIndex res13: List[(java.lang.String, Int)] = List((a,0), (b,1), (c,2), (d,3), (e,4))
リストの表示：toStringとmkString
toString
リストを文字列として扱う場合はtoStringメソッドで文字列表現として出力します
// 文字列として表現します scala> List(1,2,3,4,5).toString // "List(1, 2, 3, 4, 5)" という文字列が返ります res14: String = List(1, 2, 3, 4, 5)
mkString
リストの各要素を結合した文字列を取得する場合はmkStringですかねー、mkSringでは結合文字列を指定して要素を結合することができますね
scala> List(1,2,3,4,5).mkString(" + ") res16: String = 1 + 2 + 3 + 4 + 5
ちなみにmkStringで要素結合をする場合はプレフィックスとサフィックスも付けることができるみたいです
// プレフィックス、結合文字、サフィックスを利用しますよ scala> List(1,2,3,4,5).mkString("計算式: ", " + ", " を求めましょう") res22: String = 計算式: 1 + 2 + 3 + 4 + 5 を求めましょう
実際のところパラメーター１個バージョンは次のような多重定義を利用したものっぽいですね
List(1,2,3,4,5).mkString("", <結合文字>, "")
ついでにパラメータなしだと単純に結合します
scala> List(1,2,3,4,5).mkString res24: String = 12345
addString
mkStringの亜種としてはStringBuilderにリスト要素で構築した文字列を追加するaddStringってのもあるみたいです。
StringBuilderは可変長文字列の処理を高速に行うためのクラスみたいです→"参考"
とりあえずサンプル見てみますかねー
// StringBuilderオブジェクトを生成しますよ scala> val buf = new StringBuilder buf: StringBuilder = // リスト構成文字列を追加します scala> List(1,2,3,4,5).addString(buf, " (", ":", ") ") res32: StringBuilder = (1:2:3:4:5) // リスト構成文字列を更に追加します scala> List(1,2,3,4,5).addString(buf, ":") res33: StringBuilder = (1:2:3:4:5) 1:2:3:4:5 // リスト構成文字列をもういっちょ追加します scala> List(1,2,3,4,5).addString(buf, " (", ":", ") ") res34: StringBuilder = (1:2:3:4:5) 1:2:3:4:5 (1:2:3:4:5)
こんな感じで高速に文字列結合ができるっぽいですねー
mkStringやaddStringはIterable(Listのスーパートレイト)から継承したメソッドなので、反復操作出来るコレクション全てで使用できるみたいデス
リストの変換：elements,toArray,copyToArray
リストと配列の変換
リスト ⇔ 配列を相互変換するためにはListのtoArrayやArrayのtoListを使うみたいです。ちなみにコップ本的（まあ一般的にかな？）にListは再帰的データ構造の世界で配列はフラットなデータ構造の世界みたいですね。
んじゃサンプル書いてみますよ
// リストを配列に変換しますよ scala> List(1,2,3,4,5).toArray res38: Array[Int] = Array(1, 2, 3, 4, 5) // 配列をリストに変換しますよ scala> Array(1,2,3,4,5).toList res39: List[Int] = List(1, 2, 3, 4, 5) // リストを配列に変換して再びリストに変換しますよ scala> List(1,2,3,4,5).toArray.toList res40: List[Int] = List(1, 2, 3, 4, 5)
ちなみにちょっと変わった変換としてはcopyToArrayを使ったものですかね。copyToArrayを使うと指定された配列の添字位置から順にリストの要素と置き換えることが出来るみたいです
// こんな配列に対して scala> val arr = Array(1,2,3,4,5,6,7,8,9) arr: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9) // 添字3の位置からリストの要素で置き換えていきますよ scala> List(1,2,3,4,5).copyToArray(arr, 1) scala> arr // 添字3,4,5,6,7の位置のArray要素と置き換えました res56: Array[Int] = Array(1, 2, 3, 1, 2, 3, 4, 5, 9)
ちなみに配列側にリストを突っ込むだけのスペースがないとエラー出まくりです
scala> val arr = Array(1,2,3,4,5,6,7,8,9) arr: Array[Int] = Array(1, 2, 3, 4, 5, 6, 7, 8, 9) // 添字7の位置からコピーすると配列のスペースをオーバーします scala> List(1,2,3,4,5).copyToArray(arr,7) // 配列の要素がたんネーヨエラーがでましたな java.lang.ArrayIndexOutOfBoundsException: 9 at scala.runtime.BoxedIntArray.update(BoxedIntArray.scala:25) at scala.Iterator$class.copyToArray(Iterator.scala:655) at scala.List$$anon$2.copyToArray(List.scala:598) at scala.Iterable$class.copyToArray(Iterable.scala:494) at scala.List.copyToArray(List.scala:452) at .<init>(<console>:6) at .<clinit>(<console>) at RequestResult$.<in...
イテレータでリストにアクセス
elementsメソッドを使うことでイテレータを介してリストにアクセスすることができます。サンプルはこんな感じですかね
// イテレータを生成しますよ scala> val it = List(1,2,3).elements it: Iterator[Int] = non-empty iterator // 次の要素が存在するかチェックします scala> it.hasNext res66: Boolean = true // 次の要素にアクセスします scala> it.next res67: Int = 1 scala> it.hasNext res68: Boolean = true scala> it.next res69: Int = 2 scala> it.hasNext res70: Boolean = true scala> it.next res71: Int = 3 // 次の要素が存在しないです scala> it.hasNext res72: Boolean = false // 次の要素にアクセスしたらエラーでした scala> it.next java.util.NoSuchElementException: next on empty Iterator at scala.List$$anon$2.next(List.scala:603) at .<init>(<console>:6) at .<clinit>(<console>) at RequestResult$.<init>(<console>:3) at RequestResult$.<clinit>(<console>) at RequestResult$result(<console>) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMeth...
サンプル：マージソート
ここまでのリスト知識アレコレをつかってListに対するマージソートを書いてみますよ。マージソートは前回やった挿入ソートよりも効率が良いですねー
マージソートはざっくりいうと次のような手順を再帰的に適用するっすね
- 数列（リストなど）を中央から半分ずつにわけた部分リストを作成
- 各々をソートする
- 2つのソート済みデータ列をマージする
具体的な手順はこんな感じっぽいですね
// ソート対象の数列 5,2,1,7,3,6,4 // 数列を2分割 5,2,1) | 7,3,6,4) // 更に分割 5 | 2,1 | 7,3 | 6,4 // ソレゾレの要素数が2つ以下になったらソート開始 // 要素の比較ルール（とりあえず昇順で）でソートします 5 | 1,2 | 3,7 | 4,6 // 隣り合った数列をマージしてソートします // ＊詳しくは後述 1,2,5 | 3,4,6,7 // 隣り合った数列をマージしてソートします 1,2,3,4,5,6,7
マージしてソートするときも再帰的に処理するみたいですね
// こいつをマージしてソートします 5 | 1, 2 // 先頭要素を比較下結果 // 後半の先頭１の方が小さいので先頭に持ってきます 1 (5)|(2) // 残った物の中で大きい物を選択して 1, 2 (5) // マージ＆ソートを完成しました 1, 2, 5 ////////// // もういっちょマージ＆ソートしてみます 3,7 | 4,6 // 比較ルールで先頭を選抜しますよ(3が小さいので抜き出し) 3 (7)|(4,6) // 残りもんで比較ルールを適用しますよ(4が小さいので抜き出し) 3, 4 (7)|(6) // 更なる残りで比較ルールを適用しますよ(6が小さいので抜き出し) 3, 4, 6, (7) // ソート済み数列を完成 3, 4, 6, 7
実装します
それではマージソートアルゴリズムを実装していきますよ、今回はカリー化を利用して比較ルールも変更できる容認しましょうかねー
// カリー化を使って比較ルールとソート対象リストを別に受け付けるようにしますよ def msort[T](less:(T,T) => Boolean) (xs:List[T]):List[T] = { // ソート比較用メソッドデス def merge(xs:List[T], ys:List[T]):List[T] = (xs, ys)match { // 比較対象のリストの片方が空の場合は残ったほうを返します case (Nil, _) => ys case (_, Nil) => xs // 各々のリストの先頭の値を比較して // 条件に合う方を先頭にしたリストを再帰的に構築します // (残った方に再帰的に同じ処理を繰り返します) case (x :: xs1, y :: ys1) => { if(less(x,y)) x :: merge(xs1, ys) else y :: merge(xs, ys1) } } // リストの真ん中の位置を取得します val n = xs.length / 2 // 要素が1つのみの場合はそのまま返します if (n == 0 ) xs else { // 前半、後半のリストに分けます val (ys, zs) = xs.splitAt(n) // 再帰的に分割したリスト要素を使って比較します // lessはパラメータとして与えられた比較ルールですね merge(msort(less)(ys), msort(less)(zs)) } }
実行結果ですよー
// 実際にうごかしてみます scala> msort((x:Int, y:Int) => x < y)(List(4,0,8,5,3,1)) res78: List[Int] = List(0, 1, 3, 4, 5, 8) // せっかくのカリー化なので昇順ソート関数に専門特化させます scala> val intSort = msort((x:Int, y:Int) => x < y) _ intSort: (List[Int]) => List[Int] = <function> // 専門特化させた関数を実行しますかねー scala> intSort(List(3,78,4,5,8,23,54)) res79: List[Int] = List(3, 4, 5, 8, 23, 54, 78) // 今度は逆順ソート関数に専門特化させます scala> val reverseSort = msort((x:Int, y:Int) => x > y) _ reverseSort: (List[Int]) => List[Int] = <function> // 専門特化させた逆順関数を実行しますかねー scala> reverseSort(List(3,78,4,5,8,23,54)) res80: List[Int] = List(78, 54, 23, 8, 5, 4, 3)
マージソートの計算量
マージソートの（最悪）計算量はn*log(n)になるので挿入ソートよりも効率が【いいみたいです。（挿入ソートはn^2）。ただしランダム数の場合挿入ソートが早い場合もあるとか…
ただ、平均的に考えたらリストのソートとしてはこちらの方がイイかもネ、だそうです
詳しい計算量演算はここに詳しい説明があるのでご参照くださいませ
