Scala Standard Set Implementierung

Question

Ich kann sehen, dass von Scala Dokumentation scala.collection.immutable.Set ist nur ein Merkmal. Welche der Set-Implementierungen wird standardmäßig verwendet? HashSet oder TreeSet (oder etwas anderes)?

Ich möchte die Laufzeit bestimmter Funktionen wissen/planen.

Beispiel:

scala> val s = Set(1,3,6,2,7,1) 
res0: scala.collection.immutable.Set[Int] = Set(1, 6, 2, 7, 3) 

• Was würde die Laufzeit des s.find (5), O (1) oder O (log (n))?

• Da dasselbe gilt für Karte, was ist der beste Weg, um dies herauszufinden?

Answer 1

Durch den Quellcode suchen, können Sie die Sets bis zu vier Elemente haben eine optimierte Implementierung von EmptySet, Set1, Set2, Set3 und Set4, die einfach halten die einzelnen Werte vorgesehen finden.

Zum Beispiel ist hier Set2 Erklärung (Stand scala 2.11.4):

class Set2[A] private[collection] (elem1: A, elem2: A) extends AbstractSet[A] with Set[A] with Serializable 

Und hier ist die contains Umsetzung:

def contains(elem: A): Boolean = 
    elem == elem1 || elem == elem2 

oder die find Implementierung

override def find(f: A => Boolean): Option[A] = { 
    if (f(elem1)) Some(elem1) 
    else if (f(elem2)) Some(elem2) 
    else None 
} 

Sehr einfach.

Für Sets mit mehr als 4 Elementen ist die zugrunde liegende Implementierung ein HashSet. Wir können dies leicht überprüfen, in der REPL:

scala> Set(1, 2, 3, 4).getClass 
res1: Class[_ <: scala.collection.immutable.Set[Int]] = class scala.collection.immutable.Set$Set4 

scala> Set(1, 2, 3, 4, 5, 6).getClass 
res0: Class[_ <: scala.collection.immutable.Set[Int]] = class scala.collection.immutable.HashSet$HashTrieSet 

aber sagen, dass find muss immer durchlaufen die ganze HashSet, da sie unsortiert ist, so wird es O(n) sein. Umgekehrt wird eine Nachschlageoperation wie contains stattdessen O(1) sein.

Here's a more in-depth reference über die Leistung von Scala-Sammlungen im Allgemeinen.

Apropos Map, so ziemlich die gleichen Konzepte gelten. Es gibt optimierte Map Implementierungen von bis zu 4 Elementen, und dann ist es ein HashMap.