LL脳がscalaの勉強を始めたよ その59

scala


Scalaコップ本17章の続きをやっていきますよー、前回は集合とマップの概要をやったので今回は続きをやっていきますねー

デフォルトの集合とマップ

普段使用するSet()やscala.collection.mutable.Map()などはファクトリーメソッドによってオブジェクトが生成されるのですが、このように提供される集合やマップの実装は高速な照合アルゴリズムを使用するため要素の検索が高速らしいです。ちなみに照合アルゴリズムは主にハッシュテーブルを利用したもの…とか

実際にどのような流れでオブジェクトが生成されるかをザザッと見ていきますかねー

ミュータブルな場合

scala.collection.mutable.Set()やscala.collection.mutable.Map()のファクトリーメソッドは、scala.collection.mutable.HashSetやscala.collection.mutable.HashMapを返すみたいです。このHashSetやHashMapは内部でハッシュテーブルを使っているみたいですねー

イミュータブルな場合

イミュータブルな集合やマップは引数として渡した要素数によって、ファクトリーメソッドから返されるクラスが変わるみたいです。

例えばscala.collection.immutable.Set()だとこんな感じです

また、scala.collection.immutable.Map()だとこんな感じだとか

各実装クラスはお互いに協力しあって最大限のパフォーマンスを出し合うそうです。例えばMap1に要素を追加するとMap2が返され、Map4から要素を取り除くとMap3が呼び出されるみたいな…そんなふうにして速度を確保してるのだとか…言語設計ってすげーな(´・ω・｀)

ソートされた集合とマップ

通常の集合やマップだと追加された順（もしくは構築時の定義順）で要素の順序が決まってしまうのですが、きちんとソートして使いたいYO!ってときにはSortedSetやSortedMapトレイトを使う方法があるみたいです。

SortedSetやSortedMapトレイトはTreeSet(要素の順を管理する)やTreeMap(キーの順序を管理する)クラスによって、赤黒木を使って実装されているみたいです。なおwikipedia:赤黒木は最悪時間計算量がO(log n)とかいうめちゃめちゃ効率的な木構造実装みたいですね…詳細はあとで確認しようっと(´・ω・｀)

とりあえずSortedSetやSortedMapトレイトの大元になる（？）TreeSetとTreeMapをためしてみますかねー。ちなみにTreeSetとTreeMapはimmutable版しかないそうですよ

まずはTreeSetを使ってみます

// インポートです
scala> import scala.collection.immutable.TreeSet
import scala.collection.immutable.TreeSet

// 順序管理集合を定義してみますよ
scala> val ts = TreeSet(9,3,1,8,0,2,7,4,6,5)
// 整数昇順で管理されております
ts: scala.collection.immutable.SortedSet[Int] = Set(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

// 文字型で順序管理集合を定義です
scala> val cs = TreeSet('f', 'u', 'n')
// こちらも昇順で並んでおります
cs: scala.collection.immutable.SortedSet[Char] = Set(f, n, u)

次にTreeMapを使ってみますね

// インポートしますよ
scala> import scala.collection.immutable.TreeMap
import scala.collection.immutable.TreeMap

// キー順序管理マップを定義してみますよ
scala> var tm = TreeMap(3->'x', 1->'x', 4->'x')
// キーが昇順で管理されております
tm: scala.collection.immutable.SortedMap[Int,Char] = Map(1 -> x, 3 -> x, 4 -> x)

// 要素を追加してみますね
scala> tm += (2->'x')
// 確認です 
scala> tm
// きちんとキーが昇順で管理されまった
res1: scala.collection.immutable.SortedMap[Int,Char] = Map(1 -> x, 2 -> x, 3 -> x, 4 -> x)

とりあえず順序性を使ったIteratorでゴニョゴニョしたい場合はここらへんを利用するのがよさそうですねー

...ところで通常の集合やマップの要素の順序はOrderedトレイトで定義されるらしいので、使いたい場合はSortedSetやSortedMapトレイトをミックスインするか、修道の要素型やマップのキー型を暗黙のうちに型変換できるものにしないとイケないとのことです…ちょっぴりめんどくさいかも(´・ω・｀)

同期する集合とマップ

スレッドセーフなマップが必要な場合はマップの実装にSyncronizedMapトレイトをミックスインすればいいらしいです…うん、若干あやふやなwikipedia:スレッドセーフってのはこんな感じで、ざっくりいうと「マルチスレッドで動かしても問題が起こらないこと」って解釈で良いかしら？

ちなみにスレッドセーフの判断基準として、wikipedia的にこんな要素があったら危険とのことです

  • 広域変数やヒープにアクセスしているかどうか
  • グローバルな制限のあるリソース（ファイル、プロセスなど）を確保・解放しているかどうか
  • 参照やポインタによる間接アクセスをしているかどうか
  • 明確な副作用があるかどうか

(´ε｀；)ｳｰﾝ…マルチスレッドプログラミングをしたことのない身だとイマイチ実感がないのだけども、言葉だけ覚えておけばあとでやるときに役に立つだろう(｀・ω・´)と開き直って先に進みますよー

SynchronizedMapトレイト

とりあえずSynchronizedMapを使用するサンプルとして、HashMapにSynchronizedMapをミックスインしてみますよ

// mutableなMapやSynchronizedMap, HashMapをインポートしますよ
import scala.collection.mutable.{Map, SynchronizedMap, HashMap}
// Map生成用オブジェクトです。生成されるのは空マップです
object MapMaker {
  // マップを作成するメソッドです。キーも値もString型ですな
  // またパラメータとして要素は取らないデス
  def makeMap: Map[String, String] = {
    // MapはHashMapを使って実装します
    // HashMapにSynchronizedMapトレイトをミックスインしますよ
    // どちらもString -> String型ですね
    new HashMap[String, String] with SynchronizedMap[String, String] {
      // 存在しないキーを指定された場合に戻す値を定義します
      override def default(key:String) = "何を知りたいの？"
    }
  }
}

//// 実行してみますよ
// 空マップを生成しますよ
scala> val m = MapMaker.makeMap         
m: scala.collection.mutable.Map[String,String] = Map()

// 要素を複数追加します
scala> m ++ List("Hello"->"World", "Good"->"Morning", "Sir"->"Sir")
res11: scala.collection.mutable.Map[String,String] = Map(Sir -> Sir, Good -> Morning, Hello -> World)

// キー指定で要素を取り出します
scala> m("Hello")
res12: String = World

// 存在しない要素にアクセスして、デフォルト値を取り出します
scala> m("Hi")   
res13: String = 何を知りたいの？

// 新しい要素を追加します
scala> m += ("Hi"->"Bye")
// 追加した要素にアクセスしてみますよー
scala> m("Hi")
res15: String = Bye
SynchronizedSetトレイト

ついでにSynchronizedSetトレイトのミックスインも試してみますかね。HashSetにミックスインしたものをイロイロといじってみますよー

// ミュータブルグループをインポートしますよ
scala> import scala.collection.mutable
import scala.collection.mutable

// HashSetにSynchronizedSetトレイトをミックスインした
// Setオブジェクトを生成しますよ
scala> val synchroSet = new mutable.HashSet[Int] with mutable.SynchronizedSet[Int]
synchroSet: scala.collection.mutable.HashSet[Int] with scala.collection.mutable.SynchronizedSet[Int] = Set()

// Setに複数の値を追加してみますよー
scala> synchroSet ++ List(1,2,3,4,5) 
res24: scala.collection.mutable.Set[Int] = Set(5, 3, 1, 4, 2)

// 要素5を存在チェックします
scala> synchroSet(5)                                                            
res25: Boolean = true

// 要素10を存在チェックします...が、ないです
scala> synchroSet(10)                                                           
res26: Boolean = false

// 要素10を追加します
scala> synchroSet + 10                                                          
res27: scala.collection.mutable.Set[Int] = Set(5, 10, 3, 1, 4, 2)
// 要素10の存在を確認しました
scala> synchroSet(10) 
res28: Boolean = true

同期コレクションを使う場合は並行処理コレクションのjava.util.concurrentやScalaアクターを伴なう非同期コレクションを使った方が良い場合もあるみたいです。アクターについては30章で詳しくやるみたいですね

おまけー

HashMapへのSynchronizedMapトレイトのミックスインが初期構成時にマップ要素を
取らない（空マップしか生成しない）のがちょっと気持ち悪かったので若干改造してみましたよ。とりあえず動いたけどScala的に正しいかどうかは…微妙です(´・ω・｀)

import scala.collection.mutable.{Map, SynchronizedMap, HashMap}
object MapMaker {
  // パラメータを取るように設定します 
  def makeMap(m:(String, String)*): Map[String, String] = {
    // トレイとミックスイン済みの空HashMapを生成します
    val hm = new HashMap[String, String] with SynchronizedMap[String, String] {
      override def default(key:String) = "何を知りたいの？"
    }
    // 空のハッシュマップに要素を追加します
    hm ++ m.toList
  }
}

////実行してみますよ
// 初期状態でMap生成です
scala> val mm = MapMaker.makeMap("Hello"->"World", "Hi"->"Bye")
mm: scala.collection.mutable.Map[String,String] = Map(Hi -> Bye, Hello -> World)

// 要素にアクセスしてみますよ
scala> mm("Hi")                                                
res45: String = Bye

// 要素を追加してみまった
scala> mm += ("Good" -> "Morning")                             
// 追加されております
scala> mm                                                      
res47: scala.collection.mutable.Map[String,String] = Map(Good -> Morning, Hi -> Bye, Hello -> World)

可変長パラメータとか忘れてて少し悩んでしまいました(´・ω・｀)復習大事ね

いじょー

集合とマップについてざらットやりましたよー、次回はミュータブルとイミュータブルについてどう使い分けるべき？って話をやりますねー