Scala: puis-je compter sur l'ordre des éléments dans un Ensemble?

C'était un unplesant surprise:

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)

L'exemple en lui-même suggérer un "non" en réponse à ma question. Alors que penser de 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)

Celui-ci semble fonctionner, mais dois-je compter sur ce comportement?
Quelles sont les autres données de la structure est adaptée pour une immuable collection de pièces uniques, où l'ordre d'origine doit être conservé?

En passant, je ne sais à propos de distict méthode dans List. Le problème est, je veux renforcer l'unicité des éléments (tout en préservant l'ordre) au niveau de l'interface, afin de l'utiliser distinct serait gâcher ma conception soignée..

MODIFIER

ListSet ne semblent pas très fiables:

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

EDIT2

Dans ma recherche d'un design parfait, j'ai essayé ceci:

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

Qui fonctionne réellement:

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)

Le problème, cependant, est que je ne veux pas exposer MyList en dehors de la bibliothèque. Est-il possible d'avoir la conversion implicite lors de la substitution? Par exemple:

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

Je voudrais faire comme ceci:

object O extends T { val l = List(1, 2, 3) }  //Doesn't work
  • Où pourrais-je lire sur la scala de collections plus en profondeur que "Programming in Scala" et Scaladocs?
  • C'est un bon endroit pour commencer à apprendre à propos de la Scala collections: scala-lang.org/docu/files/collections-api/collections.html
  • Les jeux ont par (mathématiques), pas de définition de l'ordre et de la plupart des langues s'en tenir à cette convention. Curieux, pourquoi voudriez-vous attendre à avoir? L'ordre est la seule différence notable entre Seq et Set en plus d'originalité!
  • Dans ce cas, je ne suis pas trop préoccupé par les propriétés mathématiques de ma structure de données. J'ai juste besoin d'une immuable collection d'articles distincts avec leur ordre d'origine conservés. Appelez cela une liste, ensemble, vecteur, une table ou un "camion" 🙂
InformationsquelleAutor Vilius Normantas | 2011-03-09
  1. 13

    Il est ma conviction que vous ne devez jamais compter sur l'ordre dans un ensemble. Dans aucune langue.

    En dehors de cela, jetez un oeil à cette question qui parle de cela en profondeur.

    • Merci, je n'ai pas trouvé l'autre question.. Mon mauvais
    • En C++, std::set est garanti d'être commandés. -1.
    • un exemple? un exemple que ne pas fournir la commande de l'OP veut (c'est à dire, l'ordre d'insertion)? vraiment?
    • D'accord avec @larsmans. En C++, std::set est ordonnée alors que std::unordered_set n'est pas commandé
    • Christoph Henkelmann réponse est la bonne réponse. L'unicité et sortedness sont orthogonaux propriétés et il est totalement légitime de vouloir à la fois dans une classe de collection (dans toutes les langues).
    • Bien que je upvoted Christoph réponse depuis longtemps, c'est vraiment pas correct que la mienne, mais plutôt de mieux dans le sens que c'est plus élaborée. La question, après tout, était “puis-je compter sur le bon de commande dans un Set”, et non “puis-je compter sur le bon de commande dans un SortedSet”.

    InformationsquelleAutor Michael Piefel
  2. 47

    Qui dépend du Jeu que vous utilisez. Si vous ne connaissez pas le Jeu de la mise en œuvre que vous avez, alors la réponse est simple, non, vous ne peut pas être sûr. Dans la pratique, j'ai l'habitude de rencontrer les trois cas suivants:

    1. J'ai besoin d'éléments dans l'Ensemble est commandé. Pour cela, j'utilise des classes de mélange dans le SortedSet trait qui lorsque vous utilisez uniquement la Norme API Scala est toujours un TreeSet. Il garantit les éléments sont classés en fonction de leur compareTo méthode (voir la Ordered trat). Vous obtenez une (très) petite perte de performance pour le tri sélectif et l'exécution des insertions/récupérations est maintenant logarithmique, à ne (presque) constante comme avec la HashSet (en supposant une bonne fonction de hachage).

    2. Vous avez besoin de préserver l'ordre dans lequel les éléments sont insérés. Ensuite, vous utilisez la LinkedHashSet. Pratiquement aussi rapide que la normale HashSet, a besoin d'un peu plus d'espace de stockage pour les liens supplémentaires entre les éléments.

    3. Vous ne vous souciez pas de l'ordre dans l'Ensemble. Si vous utilisez un HashSet. (C'est la valeur par défaut lors de l'utilisation de la Set.apply méthode comme dans votre premier exemple)

    Tout cela s'applique à Java et, Java a un TreeSet, LinkedHashSet et HashSet et les interfaces correspondantes SortedSet, Comparable et la plaine Set.

    • Si vous regardez la source pour LinkedHashSet vous voyez que tout cela n'est mixin l'Ensemble de base de traits et d'ajouter un membre de la liste qui stocke l'ordre des éléments. Ainsi, en suivant ce modèle, il vous suffit d'écrire votre propre Immuable LinkedHashSet à l'aide de la fonction de base de classes et les traits de l'immuable paquet.
    • Ordre d'Insertion n'est pas a priori bien définis: Qu'advient-il si le même élément est ajouté deux fois, c'est à dire, l'unique représentant de mettre?
    • Aussi, en s'appuyant sur la mise en œuvre d'un type donné n'est pas une bonne idée. Vous avez besoin de quelque chose qui assure pour maintenir l'ordre, de par sa définition de l'interface (contrat). Je ne peux pas penser à une banale enveloppe existante immuable collections qui le fait. Vous pouvez utiliser TreeMap[(Int,T)] (suivi de la commande d'insertion dans le premier volet), mais cela implique de déléguer toutes les méthodes définies explicitement.
    • La Scala doc API n'est (malheureusement) pas le mentionner, mais selon le code du travail, l'insertion d'un élément nouveau ne pas changer de position (qui est la Java LinkedHashMap se comporte en tant que bien): if (addEntry(elem)) { ordered += elem; true } else false. L'API Java est plus précis: “Notez que la commande d'insertion n'est pas affectée si une clé est à nouveau inséré dans la carte”
    • Parfois, il est essentiel de s'appuyer sur la mise en œuvre d'un type donné. Quand j'ai besoin d'une liste avec la constante de temps ajoutant, j'ai besoin d'utiliser une liste chaînée, pas un tableau soutenu la liste. C'est pourquoi, dans de tels cas, j'ai choisi d'utiliser le type de l'implémentation d'une interface ou d'un trait. Aurais-je permettre à, disons, un Tableau soutenu la liste pour être remis à mon code, je peux obtenir quadratique runtimes. Donc, mon code s'appuie sur la mise en œuvre de la liste. Si je veux faire comprendre que la commande d'insertion a un effet sur le comportement de mon code, j'utilise LinkedHashSet que le type. Si je n'aime pas, je utiliser.
    • Mais encore, vous code par rapport à la spécification resp assuré propriétés de LinkedList, pas contre le code, non?
    • Vous avez raison, bien sûr, je ne le ferais pas. LinkedList , par définition, possède certaines propriétés que je peux compter sur. En utilisant explicitement LinkedList, je précise que je compte sur ceux des propriétés Spécifiques. À mon humble avis, pour la présente discussion, il est OK de s'appuyer sur les propriétés spécifiques de la LinkedHashSet aussi longtemps que je utiliser explicitement un LinkedHashSet, pas un Set. Le fait que le ScalaDoc ne fait pas mention de l'insertion de l'ordre est conservé est juste parce que la doc est encore rares dans de nombreux endroits.

    InformationsquelleAutor Christoph Henkelmann
  3. 13

    ListSet retournera toujours les éléments dans l'ordre inverse de l'insertion, car il est soutenu par une List, et la meilleure façon d'ajouter des éléments à un List est grâce à eux.

    Immuable structures de données sont des problèmes si vous voulez premier entré, premier sorti (une file d'attente). Vous pouvez obtenir O(logn) ou amortis O(1). Au vu de l'apparente nécessité de construire le jeu, puis de produire un itérateur de lui (c'est à dire, vous devez d'abord mettre tous les éléments, alors vous devez supprimer tous les éléments), je ne vois pas de toute façon à amortir elle.

    Vous peut fier qu'un ListSet retournera toujours des éléments en dernier entré, premier sorti ordre (pile). Si cela suffit, puis aller pour it.

    • J'ai considéré ListSet pendant un certain temps, mais il y avait un problème - j'ai eu à inverser la liste quelque part pour restaurer l'ordre original. Malheureusement, vous ne pouvez pas le faire à l'intérieur immuable trait. Et si je convertir mon trait à une classe (que j'ai eu à faire à la fin), je peux aussi le faire facilement list = providedList.distinct ou simplement jeter une exception sur les doublons...
    InformationsquelleAutor Daniel C. Sobral