24장 the scala collections api - codeport/scala GitHub Wiki

  • 스칼라 2.8의 새로운 컬렉션 프레임웍크
    • 사용하기 쉽다.
    • 간단하다
    • 안전하다.
    • 빠르다
    • 유니버셜하다: 컬렉션들은 같은 오퍼레이션을 제공한다.

24.1 Mutable and immutable collections

스칼라의 컬랙션은 크게 mutable 컬렉션과 immutable 컬랙션을 나뉜다.

24.2 Collections consistency

  • Traversable
    • Iterable
      • Seq
        • IndexedSeq
          • Vector
          • ResizableArray
          • GenericArray
        • LinearSeq
          • MutableList
          • List
          • Stream
        • Buffer
          • ListBuffer
          • ArrayBuffer
      • Set
        • SortedSet
          • TreeSet
        • HashSet (mutable)
        • LinkedHashSet
        • HashSet (immutable)
        • BitSet
        • EmptySet, Set1, Set2, Set3, Set4
      • Map
        • SortedMap
          • TreeMap
        • HashMap (mutable)
        • LinkedHashMap (mutable)
        • HashMap (immutable)
        • EmptyMap, Map1, Map2, Map3, Map4

24.3 Trait Traversable

  • Traversable 트레이트는 컬렉션계층의 최상위에 있다.

  • Traversable 트레이트는 foreach대한 추상 오퍼레이션 가지고 있다.

      def foreach[U](f: Elem => U)

  • Traversable 트레이트는 여러가지 메서드를 가지고 있다.

    • 추가: ++ - 두 traversable을 합치거나 이터페이터의 모든 엘리먼트를 추가한다
    • Map: map, flatMap, collect- 컬렉션 엘리먼트에 함수를 적용한 새로운 컬랙션을 만든다.
      • map과 collect 비교:
scala> List(1, "2", 3).collect{ case x:Int=> x*2 }
res28: List[Int] = List(2, 6)

scala> List(1, "2", 3).filter(_.isInstanceOf[Int]).asInstanceOf[List[Int]].map(_*2)
res27: List[Int] = List(2, 6)
  • --
    • 변환: toIndexedSeq, toIterable, toStream, toArray, toList, toSeq, toSet, toMap - Traversable 컬렉션을 지정한 컬렉션으로 변환한다.
    • 복사: copyToBuffer, copyToArray
    • 크기: isEmpty, nonEmpty, size, hasDefiniteSize.
      • hasDefiniteSize:
scala> List().hasDefiniteSize
res3: Boolean = true

scala> Stream.from(0).hasDefiniteSize
res5: Boolean = false
  • --
    • 엘리먼트 획득: head, last, headOption, lastOption, find
    • 하위컬렉션 획득: takeWhile, tail, init, slice, take, drop, filter, dropWhile, filterNot, withFilter
    • 세분화: splitAt, span, partition, groupBy
    • 엘리먼트 테스트: exists, forall, count
    • 폴드: foldLeft, foldRight, /:, :\, reduceLeft, reduceRight
    • 구체적인 폴드: sum, product, min, max
    • 문자열: mkString, addString, stringPrefix
    • 뷰: view 메서드의 두 가지 오버로드, view는 lazy 평가하는 컬렉션

24.4 Trait Iterable

  • Iterable 트레이트에 정의된 모든 메서드는 추상메서드 iterator에 대한 것이다.

  • Traversable 트레이트의 foreach 메서드는 Iterable의 iterator로 구현되었다.

  • grouped :

       val vs = List(1, 2, 3, 4, 5)
   val git = vs grouped 3
   git.next() // List(1,2,3)
   git.next() // List(4,5)

  • sliding :

       val vs = List(1,2,3,4,5)
   val sit = vs sliding 3
   sit.next() //List(1,2,3)
   sit.next() //List(2,3,4)

  • 왜 Traversable와 Iterable이 둘다 있는가?

    • 때로는 Traversable가 iterator구현보다 foreach구현을 제공하기가 더 쉽고 효율적이다.

  • Seq, Set, Map 모두 PartialFunction의 apply와 isDefinedAt을 구현한다.

24.5 The sequence traits Seq, IndexedSeq, and LinearSeq

  • IndexedSeq: indexed access시 효율적임

    • subclasses(immutable): Range, Vector[A], 등등..

  • LinearSeq: linear access시 효율적임.

    • subclasses(immutable): List[A], Queue[A], Stack[A], Stream[A]

  • Vector는 indexed, linear access 모두 contant time 안에 결과를 구할 수 있음. 애매할 때는 Vector가 킹왕짱!

  • 인덱싱과 길이: apply, isDefinedAt, length, indices, lengthCompare

  • 인덱스 검색: indexOf, lastIndexOf, indexOfSlice, lastIndexOfSlice, indexWhere, lastIndexWhere, segmentLength, prefixLength

    • segmentLength:
// 인덱스 1부터 2보다 큰 값의 길이 == 0
// (시작 인덱스가 predicate에 만족못하면 0임)
// 인덱스 2부터 List(3, 4, 5)가 2보다 크지만
// 인덱스 1에 있는 2는 2보다 크지 못하기 때문에 0임
scala> List(1, 2, 3, 4, 5).segmentLength( _ > 2, 1)
res39: Int = 0

// 인덱스 1부터 1보다 큰 값의 길이 == 4
// List(2, 3, 4, 5)가 1보다 큼.
scala> List(1, 2, 3, 4, 5).segmentLength( _ > 1, 1)
res40: Int = 4
  • --
    • prefixLength:
def prefixLength(p: A => Boolean): Int = segmentLength(p, 0)
  • 추가: +:, :+, padTo
  • 갱신: updated, patch 
scala> val list = List(1, 2, 3, 4)
list: List[Int] = List(1, 2, 3, 4)

scala> list.patch(2, Seq(5), 1) // replaces one element of the initial sequence
res0: List[Int] = List(1, 2, 5, 4)

scala> list.patch(2, Seq(5), 2) // replaces two elements of the initial sequence
res1: List[Int] = List(1, 2, 5)

scala> list.patch(2, Seq(5), 0) // adds a new element
res2: List[Int] = List(1, 2, 5, 3, 4)
  • 정렬: sorted, sortWith, sortBy
  • 반전: reverse, reverseIterator, reverseMap
  • 비교: startsWith, endsWith, contains, corresponds, containsSlice
    • corresponds:
scala> List(1, 2, 3).corresponds(List(4, 5, 6, 7)){ (a, b) => println(s"$a, $b"); true}
1, 4
2, 5
3, 6
res58: Boolean = false

scala> List(1, 2, 3).corresponds(List(4, 5, 6, 7)){ (a, b) => println(s"$a, $b"); false}
1, 4
res60: Boolean = false
  • 멀티셋: intersect, diff, union, distinct
  • buffers는 mutable sequences의 하위카테고리이다. buffers는 존재하는 엘리먼트의 갱신과 엘리턴트 추가/삭제 를 지원한다.
    • ListBuffer과 ArrayBuffer가 있다.

Buffer

Buffer는 mutable Seq의 중요한 카테고리이고 ListBuffer, ArrayBuffer가 대표적인 구현이다. Mutable Collection에 필요한 메소드들이 구현돼 있지만 생략...

24.6 Sets

  • Set은 중복요소가 없는 Iterables이다.
  • 테스트: contains, apply, subsetOf
  • 추가: +, ++
  • 제거: -, --
  • Set : intersect, union, diff, &, |, &~
  • SortedSet어떤 순서로 엘리먼트를 추가하던지 정렬된 순서로 탐색한다.
  • SortedSet의 기본 구현체는 TreeSet이다: SortedSet(3, 2, 1) == TreeSet(1, 2, 3)
  • TreeSet은 red-black tree로 구현해서 balanced다.
  • BitSet은 Long 배열에 압축해 저장한다. BitSet의 크기는 엘리먼트 중 가장 큰 수에 달려있다("If N is that largest integer, then the size of the set is N/64 Long words, or N/8 bytes, plus a small number of extra bytes for status information")

24.7 Maps

  • Map은 키, 밸류 쌍으로 이루어진 Iterables이다.
  • 검색: apply, get, getOrElse, contains, isDefinedAt
  • 추가/갱신: +, ++, updated
  • 삭제: -, --
  • 하위컬렉션 생성자: keys, keySet, keysIterator, values, iterator, values
  • 변환: filterKeys, mapValues
  • getOrElseUpdate는 캐시처럼 동작하는 맵에 접근하는데 유용하다.

24.8 Synchronized sets and maps

  • 쓰레드세이프한 맵이 필요하면 SynchronizedMap트래이트를 맵에 믹스인할 수 있다.
  • 존재 하지 않는 키를 조회하면 NoSuchElementException이 발생한다.
    • default 메서드를 오버라이드하면 존재하지 않는 키를 조회할 때의 동작을 바꿀 수 있다.

24.9 Concrete immutable collection classes

  • Lists는 유한한 immutable 시퀀스다. 첫 요소와 나머리 리스트에 대한 상수시간 접근을 제공하고 cons로 리스트앞에 엘리먼트를 상수타임으로 추가할 수 있다.
  • Streams는 리스트와 비슷하지만 lazy하게 계산한다. 리스트의 ::와 비슷하게 스트림에서는 #::를 사용할 수 있다.
  • 리스트는 head를 처리할 때 아주 효율적이지만 다른 부분에는 시간이 많이 걸린다. Vectors는 2.8에서 추가된 컬렉션으로 어떤 요소에도 효율적인 접근을 제공한다. Vectors는 immutable이다.
  • LIFO 시퀀스가 필요하면 Stack를 사용해라. List를 Stack으로(head, tail로) 사용할 수 있기 때문에 scala에서는 Stack을 잘 사용하지 않는다.
  • FIFO에는 Queue를 사용해라
  • Range는 동일한 간격으로 떨어진 integer의 정렬된 시퀀스이다.
  • Hash tries는 immutable set과 map을 효율적으로 구현하는 표준적인 방법이다. Vector가 구현된 방식도 비슷하다. 32개 엘리먼트를 가진 Tree 구조이고 액세스할 때 Hash를 사용한다.
  • Red-black tree는 하나는 "Red"로 표시되고 다른 것들은 "black"로 표시되는 balanced binary tree의 형식이다(TreeSet, TreeMap).
  • Immutable BitSet은 작은 정수들를 64bit Long 배열에 효율적으로 저장한다. 작은 정수만 다룬다면 컴팩트하고 성능도 빠르다.
  • list map은 키/밸류 쌍의 링크드 리스트로 된 맵이다.

24.10 Concrete mutable collection classes

  • ArrayBuffer는 array과 size를 가지고 있다. 대부분의 동작은 array의 속도와 같다.
  • ListBuffer는 내부적으로 배열대신 링크드리스트를 사용한다는 점을 제외하면 array buffer와 같다.
  • StringBuilder는 문자열을 만드는데 유용하다.
  • LinkedList는 다음 포인터로 연결되 노드로 이루어진 시퀀스이다. 대부분의 언어에서 비어있는 링크드리스트는 null이지만 Scala에서는 시퀀스 오퍼레이션을 사용하기 위해 null이 아니다.
  • DoubleLinkedList는 LinkedList와 비슷하고 이전 노드를 가르키는 prev라는 필드가 있어서 remove가 매우 빠르다.
  • MutableList는 LinkedList에 끝에 있는(Terminal) Empty Node를 참조하는 포인터가 추가돼 있다. 그래서 append가 빠르다. 현재 mutable.LinearSeq의 표준 구현체다.
  • Queue의 mutable 버전이다. immutable과 비슷하지만 enqueue대신 +=, ++=를 사용한다
  • ArraySeq는 내부에 Array[AnyRef]로 요소를 저장하는 고정된 사이즈의 시퀀스다
  • mutable버전의 Stack
  • ArrayStack는 Mutable Stack보다 약간 빠르다. 내부 배열의 크기는 자동으로 조절된다.
  • Hash Table은 배열에 요소를 저장하고 각 요소의 저장 위치는 hash code로 결정한다. Scala의 mutable hash map과 set이 hash table로 구현됐다. 이터레이션은 특정순서로 일어난다는 보장이 없고 순서를 보장하려면 linked hash map이나 set을 사용해야 한다.
  • WeakHashMap은 해시맵의 특수한 종류로 키를 참조하는 것이 더이상 없으면 gc()때 map에서 삭제된다. Java, Weak References and WeakHashMap 참고
  • concurrent map은 여러 쓰레드에서 동시에 접근할 수 있다.
  • mutable bit set은 immutable버전과 같지만 수정할 수 있다.

24.11 Arrays

  • 스칼라의 배열은 Java의 배열과 1대1 대응된다.

  • 스칼라 배열을 자바보다 더 많은 것을 제공한다.

    • 제너릭을 지원한다.
    • 스칼리 시퀀스화 호환성이 있다.
    • 시퀀스의 모든 오퍼레이선을 지원한다.

  • 자바 배열의 타입컨버전에서 ArrayOps가 WrappedArray 컨버전보다 우선순위가 높다.

    • 스칼라 배열은 의미적으로 Seq라고 생각할 수 있지만 Java와 1대1로 대응해야 하므로 Seq는 아니다. ArrayOps은 Seq-Like 연산을 돕는 거고 WrappedArray는 진짜 Seq로 변환하는데 사용하는 것 같음.(by pismute) String도 마찬가지.

  • 제너릭 지원에서 type erase로 인한 오류를 막기 위해서 scala.reflect.ClassManifest타임의 class manifest를 줄 수 있다.

      def deenElems[T](xs: Vector[T])(implicit m: ClassManifest[T]): Array[T] = ...

  • context bound를 사용해서 더 간단히 쓸 수 있다.

      def evenElems[T: ClassManifest](xs: Vector[T]): Array[T] = ...

24.12 Strings

  • 스트링도 모든 시퀀스 오퍼레이션을 지원한다. Array처럼 StringOps가 WrappedString보다 우선순위가 높고 Seq인 WrappedString있다.

24.13 Performance characteristics

  • 각 컬렉션은 다른 성능 특징이 있다.

24.14 Equality

  • 같은 엘리먼트를 가지고 있고 카테고리(Seq, Set, Map)가 같으면 True다(Seq는 순서도 중요):
scala> List(1, 2, 3) == Vector(1, 2, 3)
res0: Boolean = true

scala> List(1, 2, 3) == Vector(3, 2, 1)
res1: Boolean = false

scala> HashSet(1, 2) == TreeSet(2, 1)
res2: Boolean = true
  • 같은 엘리먼트를 가지고 있지만 카테고리(Seq, Set, Map)가 다르면 False다:
scala> List(1, 2, 3) == Set(1, 2, 3)
res4: Boolean = false

24.15 Views

  • map, filter, ++는 transformers라고 부른다.
  • 트랜스포머는 strict와 non-strict(lazy)로 구현된다.
  • strict 트랜스포머 생성자는 모든 요소의 새로운 컬렉셩을 생성한다.
  • non-strict 트랜스포머틑 결과 컬렉션의 프록시만 생성하고 요청될때 요소를 생성한다.
  • view는 기반 클래스의 모든 트랜스포머를 lazy하게 구현한 특수한 종류의 컬렉션이다.
  • xs.view는 xs와 같은 컬렉션이지만 lazy하게 트랜스포머를 lazy하게 구현한다. 다시 strict한 컬렉션을 얻으려면 force메서드를 사용한다.
scala> List(1, 2, 3).filter{ (x)=> println("1st"); true }.map{ (x)=> println("2nd"); x}
1st
1st
1st
2nd
2nd
2nd
res7: List[Int] = List(1, 2, 3)

scala> List(1, 2, 3).view.filter{ (x)=> println("1st"); true }.map{ (x)=> println("2nd"); x}
res11: scala.collection.SeqView[Int,Seq[_]] = SeqViewFM(...)

scala> List(1, 2, 3).view.filter{ (x)=> println("1st"); true }.map{ (x)=> println("2nd"); x}.force
1st
2nd
1st
2nd
1st
2nd
res10: Seq[Int] = List(1, 2, 3)

24.16 Iterators

  • iterator는 컬렉션이 아니라 컬렉션의 요소에 접근하는 방법이다.
  • 두가지 기본동작 next와 hasNext가 있다.
  • BufferedIterator은 head 메서드를 제공하는 Iterator의 하위트레이트이다. head를 통해서 next()하기 전에 미리 엘리먼트에 접근할 수 있다.
  • 모든 이터레이터에서 buffered 메서드로 buffered iterator로 변환할 수 있다.

24.17 Creating collections from scratch

  • 모든 컬렉션은 컬렉션 이름뒤에 괄호안에 요소를 넣어서 생성할 수 있다.

24.18 Conversions between Java and Scala collections

  • JavaConversions 객체로 주요 컬렉션을 implicit conversion을 지원한다.
import collection.JavaConversions._

24.19 Migrating from Scala 2.7

  • scalac에 -deprecation, -Xmigration 플래그를 주면 마이그레이션 경고를 볼 수 있다.