스칼라의 HashSet은 자바의 HashSet보다 빠른 것으로 알려져 있다.
그 이유는 HashSet의 구현이 해시 트라이(Hash trie)로 구현되어 있다.
참고로 해시 트라이는 스칼라 공식 문서에서 간단히 소개하고 있다.
Their representation is similar to vectors in that they are also trees where every node has 32 elements or 32 subtrees. But the selection of these keys is now done based on hash code. For instance, to find a given key in a map, one first takes the hash code of the key. Then, the lowest 5 bits of the hash code are used to select the first subtree, followed by the next 5 bits and so on. The selection stops once all elements stored in a node have hash codes that differ from each other in the bits that are selected up to this level.
또한, 해시 트라이는 속도를 빠르게 개선하는 분할상환 상수 시간( amortized constant time)인데,
원래 Hash가 검색은 빠르지만, 추가/삭제가 나쁜 구조인데, 스칼라는 이를 개선했다.
http://docs.scala-lang.org/overviews/collections/performance-characteristics.html
| lookup | add | remove | min | |
|---|---|---|---|---|
| immutable | ||||
HashSet/HashMap | eC | eC | eC | L |
| aC | The operation takes amortized constant time. Some invocations of the operation might take longer, but if many operations are performed on average only constant time per operation is taken. |
여기 나오는 분할상환 시간 분석에 대해서는 아래 위키를 참조하거나 인터넷을 참조한다.
분할상환 시간 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이다.
https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0%EC%83%81%ED%99%98%EB%B6%84%EC%84%9D
또한 아래 자료에도 분할상환 시간에 대한 시간에 대해서 설명되어 있다.
http://scabl.blogspot.kr/2014/10/what-heck-is-amortized-constant-time.html
'scala' 카테고리의 다른 글
| [scala] groupBy / mapValues 예제 (0) | 2016.10.11 |
|---|---|
| [scala] retry (0) | 2016.10.06 |
| 스칼라의 대수적 자료형(Algebraic Data Types, ADT), exhaustivity-checking (0) | 2016.10.04 |
| [scala] 이름에 의한 호출 매개변수 (by-name parameter) (0) | 2016.09.29 |
| [scala] filter, exists 성능 주의 (0) | 2016.09.29 |
