Scala: могу ли я полагаться на порядок элементов в наборе?

Это был довольно неожиданный сюрприз:

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)

Пример сам по себе предлагает "нет" ответ на мой вопрос. Тогда как насчет 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)

Этот, похоже, работает, но я должен полагаться на это поведение? Какая другая структура данных подходит для неизменной коллекции уникальных предметов, где первоначальный порядок должен быть сохранен?

Кстати, я знаю о методе distict в List. Проблема в том, что я хочу обеспечить уникальность элементов (при сохранении порядка) на уровне интерфейса, поэтому использование distinct испортит мой опрятный дизайн.

ИЗМЕНИТЬ

ListSet тоже не очень надежный:

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

EDIT2

В моем поиске идеального дизайна я пробовал это:

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

Что на самом деле работает:

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)

Однако проблема заключается в том, что я не хочу выставлять MyList вне библиотеки. Есть ли способ иметь неявное преобразование при переопределении? Например:

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

Я хотел бы сделать это следующим образом:

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

Ответы

Ответ 1

Я считаю, что вы никогда не должны полагаться на порядок в наборе. Без языка.

Кроме того, посмотрите этот вопрос, в котором подробно говорится об этом.

Ответ 2

Это зависит от используемого вами набора. Если вы не знаете, какая у вас реализация Set, то ответ просто, вы не можете быть уверены. На практике я обычно сталкиваюсь со следующими тремя случаями:

  • Мне нужны элементы в наборе, который нужно заказать. Для этого я использую классы, смешивающиеся в признаке SortedSet, который, когда вы используете только стандартный Scala API, всегда равен TreeSet. Он гарантирует, что элементы упорядочены по методу compareTo (см. Ordered trat). Вы получаете (очень) небольшое ограничение производительности для сортировки, так как время выполнения вставки /retrievals теперь логарифмическое, а не (почти) постоянное, как с HashSet (при условии хорошей хэш-функции).

  • Вам нужно сохранить порядок, в который вставлены элементы. Затем вы используете LinkedHashSet. Практически так же быстро, как и обычный HashSet, требуется дополнительное пространство для хранения дополнительных ссылок между элементами.

  • Вам не нужен порядок в наборе. Таким образом, вы используете HashSet. (Это значение используется при использовании метода Set.apply, как в первом примере)

Все это относится и к Java, у Java есть TreeSet, LinkedHashSet и HashSet и соответствующие интерфейсы SortedSet, Comparable и plain Set.

Ответ 3

ListSet всегда будет возвращать элементы в обратном порядке вставки, поскольку он поддерживается List, а оптимальный способ добавления элементов в List заключается в их добавлении.

Неизбежные структуры данных проблематичны, если вы хотите сначала сначала, так и в очередь (очередь). Вы можете получить O(logn) или амортизировать O(1). Учитывая очевидную необходимость в создании набора, а затем выпустить из него итератор (т.е. Вы сначала поместите все элементы, затем вы удалите все элементы), я не вижу способа амортизировать его.

Вы можете полагаться, что ListSet всегда будет возвращать элементы в последнем, первом порядке (стек). Если этого достаточно, то идите на него.