Scala CH25. 스칼라 컬렉션의 아키텍처

아래의 글은 마틴 오더스키,렉스 스푼,빌 베너스 공저 / 오현석,이동욱,반영록 공역, 『Programming in Scala 3/e』,에이콘출판사(2017), CH01의 내용을 기반으로 작성하였습니다.

 

새 컬렉션 프레임워크으 주 설계 목표는 모든 연산을 가능한 한 적은 위치에 정의해서 중복을 피하는 것

설계시 택한 접근 방법은 대부분의 컬렉션 연산을 컬렉션 템플릿에 정의해서 개별 기반 클래스나 구현을 필요에 따라 유연하게 상속할 수 있게 제공하는 것

 

1. 빌더

대부분의 연산이 빌더와 순회 (build, traversal)을 가지고 구현됨.

package scala.collection.generic     class Builder[-Elem, +To] {     def +=(elem: Elem): this.type     def result(): To     def clear()     def mapResult[NewTo] (f: To => NewTo): Builder[Elem, NewTo] = ... }

2. 공통 연산 한데 묶기

자연스러운 타입을 만들면서 동시에 구현 코드는 최대한 공유

스칼라 컬렉션은 동일 결과 타입 원칙, 예를 들어 filter 연산은 모든 컬렉션 타입에 대해 같은 컬렉션 타입을 반환

구현 트레이트 (implementation trait) 라 불리는 제네릭 빌더와 순회를 사용해 코드 중복을 줄이고, 동일 결과 타입을 달성

트레이트에는 Like라는 접미사가 붙는다. Traversable의 구현 트레이트는 TraverableLike

일반 컬렉션에는 하나의 타입 파라미터가 있는 반면, 구현 트레이트에는 2개가 있음.

trait TraversableLike[+Elem, +Repr] { ... } Elem은 순회 트레이트 원소 타입이며, Repr은 순회 타입 자체

package scala.collection     trait TraversableLike[+Elem, +Repr] {     def newBuilder: Builder[Elem, Repr]     def foreach[U[(f: Elem => U)         ...     def filter(p: Elem => Boolean) : Repr = {         val b = newBuilder         foreach { elem => if (p(elem)) b += elem }         b.result         }       // TraversableLike의 map 구현 def map[B, That] (f:Elem => B)     (implicit bf: CanBuildForm[Repr, That, This]): That = {     val b = bf(this)     for (x <- this) b += f(x)     b.result }     // CanBuildForm 트레이트 package scala.collection.generic     trait CanBuildForm(-From, -Elem, +To] {     def apply(from: From): Builder[Elem, To] ]     CanBuildForm[Set[_], A, Set[A]] // 와일드카드 타입 Set[_] : 타입에 관계없니 Set을 만들 수 있다.

 

3. 새 컬렉션 통합

 

시퀀스 통합

abstract class Base case object A extends Base case object T extends Base case object G extends Base case object U extends Base     object base {     val fromInt: Int => Base = Array(A, T, G, U)     val toInt: Base => Int = Map(A -> 0, T -> 1, G -> 2, U -> 3) }     import collection.IndexedSeqLike import collection.mutable.{Builder, ArrayBuffer} import collection.generic.CanBuildFrom     final class RNA1 private (val groups: Array[Int], val length: Int) extends IndexedSeq[Base] {     import RNA1.*         def apply(idx: Int): Base = {         if (idx <0 || length <= idx)             throw new IndexOutOfBoundsException         Base.fromInt(groups(idx / N) >> (idx % N * ) & M)     }     }     object RNA1 {     private val S = 2     private val N = 32 / S     private val M = (1 << S) - 1         def fromSeq(buf: Seq[Base]) : RNA1 = {         val groups = new Array[Int]((buf.length + N - 1) / N)         for (i <- 0 until buf.length)             groups(i / N) != buf.toInt(buf(i)) << (i % N * S)         new RNA1(groups, buf.length)     }         def apply(bases: Base*) = fromSeq(base) }     // RNA1 생성자 private : 직접 생성할 수 없음. // RNA1 시퀀스를 압축한 배열로 표현한다는 것을 감춤 // 인터페이스와 구현을 분리할 수 있음.         val xs = List(A, G, T, A) RNA1.fromSeq(xs)     val rna1 = RNA1(A, U, G, G, T)     rna1.length rna1.last rna1.take(3) IndexSeq[Base] = Vector(A, U, G)     정적 타입 결과는 IndexSeq[Base]이고 동적타입 결과는 Vector 이를 변경할려면 override def take(count:Int) : RNA1 = RNA1.fromSeq(super.take(count)) 이렇게 하면 take를 대신할 수 있음. 하지만 drop, filter, init은? 일관성을 위해서 seq를 반환하는 메소드 50개가 있는데 전부 변경해야함....     final class RNA2 private ( val groups: Array[Int], val length: Int) extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA2] {     import RNA2._     override def newBuilder: Builder[Base, RNA2] = new ArrayBuffer[Base] mapResult fromSeq         def apply(idx: Int): Base = ... // 예전과 동일... }     val rna2 = RNA2(A, U, G, G, T)     rna2 take 3 RNA2 = RNA2(A, U, G)     rna2 filter (U !=) RNA2 = RNA2(A, G, G, T)   val rna = RNA(A, U, G, G, T)     ran map { case A => T case b => b] RNA = RNA(T, U, G, G, T)     rna ++ rna     RNA(A, U, G, G, T, A, U, G, G, T)         rna map Base.toInt     IndexedSeq[Int] = Vector(0, 3, 2, 2, 1)     rna ++ List("missing, "data)     Vector(A, U, G, G, T, missing data)       def map[B, That](f: Elem => b) (implicit cbf: CanBuildFrom[Repr, B, That]): That     Elem은 컬렉션의 원소 타입이며, Repr은 컬렉션 자체의 타입, TraversableLike나 IndexedSeqLike 같은 구현 클래스의 두 번째 타입 인자로 들어가야하는 타입 B는 매핑 함수의 결과 타입인 동시에 결과 컬렉션의 원소 타입이다.         final class RNA private (val groups: Array[Int], val length: Int) extends IndexedSeq[Base] with IndexedSeqLike[Base, RNA] {     import RNA._         // 'IndexedSeq' 에 있는 'newBuilder'를 재구현하는 것은 필수다     override protected[this] def newBuilder: Builder[Base, RNA] = RNA.newBuilder         // 'indexSeq'의 apply를 재구현하는 것은 필수다     def apply(idx: Int): Base = {         throw new IndexOutOfBoundsException     Base.fromInt(group(idx / N) >> (idx % N * S) & M)     }         override def foreach[U](f: Base => U) : Unit = {         var i = 0         var b = 0         while (i < length) {             b = if (i % N == 0) groups(i / N) else b >>> S             f(Base.fromInt(b & ))             i += 1         }     } }     object RNA {     private val S = 2     private val M = (1 << S) - 1     private val N = 32 / S           def fromSeq(buf: Seq[Base]: RNA = {         val groups = new Array[Int]((buf.length + N + 1) / N)         for (i < 0 until buf.length)             groups(i / N) |= Base.toInt(buf(i) << (i % N * S)         new RNA(groups, buf.length)     }         def apply(bases: Base*) = fromSeq(bases)         def newBuilder: Builder[Base, RNA] = new ArrayBuffer mapResult fromSeq         implicit def canBuildFrom: CanBuildFrom[RNA, Base, RNA] =         new CanBuildFrom[RNA, Base, RNA] {             def apply(): Builder[Base, RNA] = new Builder             def apply(from: RNA): Builder[Base, RNA] = newBuilder         } }     foreach는 다른 곳에서도 많이 사용하기 때문에 최적화 구현을 필요로 한다.

 

새로운 집합과 맵의 통합

문자열이 키인 패트리샤 트라이 patricia trie 영숫자 부화화 정보를 가져오는 실욕적인 알고리즘 practical algorithm to retrieve information coded in alphanumeric 집합이나 맵을 트리로 구성하되, 검색 키의 각 문자가 유일한 자식 트리를 구성하게 만드는 것     아주 효율적인 검색과 변경을 제공함. 어떤 접두사를 포함하는 하위 컬렉션을 쉽게 선택할 수 있다는 특성이 있음.

 

val m = PrefixMap("abc" -> 0, "abd" -> 1, "al" -> 2, "all" -> 3, "xy" -> 4) PrefixMap[Int] = Map((abc, 0), (abd, 1), (al, 2), (all, 3), (xy, 4))     m withPrefix "a" Map((bc, 0), (bd, 1), (l, 2), (ll, 3))     import collection._     class PrefixMap[T] extends mutable.Map[String, T] with mutable.MapLike[String, T, PrefixMap[T]] {     var suffixes: immutable.Map[Char, PrefixMap[T]] = Map.empty     var value : Option[T] = None         def get(s: String): Option[T] =         if (s.isEmpty) value         else suffixes get (s(0)) flatMap (_.get(s substring 1))         def withPrefix(s: String): PrefixMap[T] =         if (s.isEmpty) this         else {             val leading = s(0)             suffixes get leading match {                 case None =>                     suffixes = suffixes + (leading -> empty)                 case _ =>             }             suffixes(leading) withPrefix (s substring 1)         }         override def update(s: String, elem: T) =         withPrefix(s).value = Some(elem)     override def remove(s: String): Optio[T] =         if (s.isEmpty) { val prev = value; value = None; prev }         else suffixes get (s(0) flapMap (_.remove(s substring 1)))         def iterator: Iterator[(String, T)] =         (for (v <- value.iterator) yield ("", v) ++             (for ((chr, m) <- suffixes.iterator;                 (s, v) <- m.iterator) yield (chr +: s, v))     def += (kv: (String, T)): this.type = (update(kv._1, kv._2); this }     def -= (s: String): this.thype = { remove(s); this }     override def empty = new PrefixMap[T] }     // 5개 이하이면 변경 불가능한 map : suffixes // newBuilder가 없다. 이유는 맵이나 집합에는 MapBuilder 클래스의 인스턴스인 디폴트 빌더가 따라오기 때문     import scala.collection.mutable.{Builder, MapBuilder} import scala.collection.generic.CanBuildFrom     object PrefixMap {     def empty[T] = new PrefixMap[T]         def apply[T](kvs: (String, T)*): PrefixMap[T] = {         val m: PrefixMap[T] = empty         for (kv <- kvs) m += kv         m     }           def newBuilder[T]: Builder[(String, T), PrefixMap[T]] =         new MapBuilder[String, T, PrefixMap[T]](empty)         implicit def canBuildForm[T]         : CanBuildFrom[Prefix[_], (String, T), PrefixMap[T]] =             new CanBuildFrom[PrefixMap[_], (String, T), PrefixMap[T]] {             def apply(from: PrefixMap[_]) = newBuilder[T]             def apply() = newBuilder[T]         } }

 

정리

1. 컬렉션을 변경 가능학 할지 여부를 결정해야 한다.
2. 기반 트레이트를 제대로 선택해야 한다
3. 대부분의 컬렉션 연산을 구현하기 위해 구현 트레이트를 제대로 선택해야 한다
4. map이나 그와 비슷한 연산을 사용해 컬렉션 타입의 인스턴스를 반환해야 한다면, 암시적인 CanBuildForm을 동반 객체에 제공해야 한다.