Scala: Kann ich mich auf die Reihenfolge der Elemente in einer Menge verlassen?

Question

Das war eine ziemlich unerfreuliche Überraschung:

scala> Set(1, 2, 3, 4, 5)       
res18: scala.collection.immutable.Set[Int] = Set(4, 5, 1, 2, 3)
scala> Set(1, 2, 3, 4, 5).toList
res25: List[Int] = List(5, 1, 2, 3, 4)

Das Beispiel an sich legt ein "Nein" als Antwort auf meine Frage nahe. Was ist dann mit ListSet ?

scala> import scala.collection.immutable.ListSet
scala> ListSet(1, 2, 3, 4, 5)
res21: scala.collection.immutable.ListSet[Int] = Set(1, 2, 3, 4, 5)

Diese scheint zu funktionieren, aber sollte ich mich auf dieses Verhalten verlassen? Welche andere Datenstruktur ist für eine unveränderliche Sammlung eindeutiger Elemente geeignet, bei der die ursprüngliche Reihenfolge beibehalten werden muss?

Übrigens, ich weiß Bescheid über distict Methode in List . Das Problem ist, dass ich die Eindeutigkeit der Elemente (unter Beibehaltung der Reihenfolge) auf Schnittstellenebene erzwingen möchte, also mit distinct würde mein ordentliches Design durcheinander bringen

EDIT

ListSet scheint auch nicht sehr zuverlässig zu sein:

scala> ListSet(1, 2, 3, 4, 5).toList
res28: List[Int] = List(5, 4, 3, 2, 1)

EDIT2

Auf der Suche nach einem perfekten Design habe ich dies ausprobiert:

scala> class MyList[A](list: List[A]) { val values = list.distinct }
scala> implicit def toMyList[A](l: List[A]) = new MyList(l)
scala> implicit def fromMyList[A](l: MyList[A]) = l.values     

Das funktioniert tatsächlich:

scala> val l1: MyList[Int] = List(1, 2, 3)
scala> l1.values
res0: List[Int] = List(1, 2, 3)

scala> val l2: List[Int] = new MyList(List(1, 2, 3))
l2: List[Int] = List(1, 2, 3)

Das Problem ist jedoch, dass ich nicht die ganze Welt vor den Kopf stoßen möchte. MyList außerhalb der Bibliothek. Gibt es eine Möglichkeit, die implizite Konvertierung beim Überschreiben zu haben? Zum Beispiel:

trait T { def l: MyList[_] }
object O extends T { val l: MyList[_] = List(1, 2, 3) }
scala> O.l mkString(" ")  // Let's test the implicit conversion
res7: String = 1 2 3      

Ich würde es gerne so machen:

object O extends T { val l = List(1, 2, 3) }  // Doesn't work

Answer 1

Das hängt von dem von Ihnen verwendeten Set ab. Wenn Sie nicht wissen, welche Set-Implementierung Sie haben, dann lautet die Antwort einfach: Nein, Sie können nicht sicher sein. In der Praxis treffe ich gewöhnlich auf die folgenden drei Fälle:

1. Ich brauche die Artikel des Sets zum Bestellen. Hierfür verwende ich Klassen, die in der SortedSet Eigenschaft, die bei ausschließlicher Verwendung der Scala-Standard-API immer eine TreeSet . Sie garantiert, dass die Elemente entsprechend ihrer Position geordnet sind compareTo Methode (siehe die Ordered trat). Sie erhalten eine (sehr) kleine Leistungseinbuße für die Sortierung, da die Laufzeit von Einfügungen/Abrufen nun logarithmisch ist, nicht (fast) konstant wie bei der HashSet (eine gute Hash-Funktion vorausgesetzt).

2. Die Reihenfolge, in der die Elemente eingefügt werden, muss beibehalten werden. Dann verwenden Sie die LinkedHashSet . Praktisch so schnell wie der normale HashSet benötigt ein wenig mehr Speicherplatz für die zusätzlichen Verbindungen zwischen den Elementen.

3. Sie kümmern sich nicht um die Ordnung in der Menge. Sie verwenden also eine HashSet . (Das ist die Standardeinstellung, wenn Sie die Set.apply Methode wie in Ihrem ersten Beispiel)

All dies gilt auch für Java, Java hat eine TreeSet , LinkedHashSet y HashSet und die entsprechenden Schnittstellen SortedSet , Comparable und einfach Set .

Answer 2

Ich bin der Meinung, dass man sich nie auf die Reihenfolge in einem Set verlassen sollte. In keiner Sprache.

Abgesehen davon, werfen Sie einen Blick auf diese Frage in dem diese Frage ausführlich behandelt wird.

Answer 3

ListSet gibt immer Elemente in der umgekehrten Reihenfolge der Einfügung zurück, da sie durch eine List und die optimale Art und Weise des Hinzufügens von Elementen zu einer List indem sie vorangestellt werden.

Unveränderliche Datenstrukturen sind problematisch, wenn Sie eine Warteschlange (first in, first out) wünschen. Sie können O(logn) oder abgeschrieben O(1) . In Anbetracht der offensichtlichen Notwendigkeit, die Menge zu erstellen und dann einen Iterator daraus zu erzeugen (d.h. zuerst werden alle Elemente hinzugefügt, dann werden alle Elemente entfernt), sehe ich keine Möglichkeit, dies zu amortisieren.

Sie kann darauf vertrauen, dass ein ListSet gibt die Elemente immer in der Reihenfolge "letzter Eingang, erster Ausgang" zurück (ein Stapel). Wenn das ausreicht, dann nur zu.