Почему изменяемые и неизменяемые ListMaps имеют разные порядки в Scala? - PullRequest
Новая
       13

Почему изменяемые и неизменяемые ListMaps имеют разные порядки в Scala?

9 голосов
/ 24 сентября 2011

Почему неизменяемая версия ListMap хранится в порядке возрастания, а изменяемая версия - в порядке убывания?

Вот тест, который вы можете использовать, если у вас есть scalatest-1.6.1.jar и junit-4.9.jar 

  @Test def StackoverflowQuestion()
  {
    val map = Map("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18)
    val sortedIMMUTABLEMap = collection.immutable.ListMap[String, Int](map.toList.sortBy[Int](_._2): _*)
    println("head : " + sortedIMMUTABLEMap.head._2)
    println("last : " + sortedIMMUTABLEMap.last._2)
    sortedIMMUTABLEMap.foreach(X => println(X))
    assert(sortedIMMUTABLEMap.head._2 < sortedIMMUTABLEMap.last._2)

    val sortedMUTABLEMap = collection.mutable.ListMap[String, Int](map.toList.sortBy[Int](_._2): _*)
    println("head : " + sortedMUTABLEMap.head._2)
    println("last : " + sortedMUTABLEMap.last._2)
    sortedMUTABLEMap.foreach(X => println(X))
    assert(sortedMUTABLEMap.head._2 > sortedMUTABLEMap.last._2)
  }

Вот результат теста PASSING: 

head : 2
last : 18
(C,2)
(A,5)
(D,9)
(B,12)
(E,18)
head : 18
last : 2
(E,18)
(B,12)
(D,9)
(A,5)
(C,2)

Ответы [ 3 ]

12 голосов
/ 24 сентября 2011

Симптомы могут быть упрощены до: 

scala> collection.mutable.ListMap(1 -> "one", 2 -> "two").foreach(println)
(2,two)
(1,one)

scala> collection.immutable.ListMap(1 -> "one", 2 -> "two").foreach(println)
(1,one)
(2,two)

"Сортировка" в вашем коде не является ядром проблемы, ваш вызов ListMap использует вызов ListMap.apply от собеседникаобъект, который создает карту списка, поддерживаемую изменяемым или неизменным списком.Правило заключается в том, что порядок вставки будет сохранен.

Разница, по-видимому, заключается в том, что изменяемый список поддерживается списком неизменяемого , и вставка происходит спереди.Вот почему при итерации вы получаете поведение LIFO.Я все еще смотрю на неизменный, но держу пари, что вставки эффективно сзади.Edit, я передумал: insert, вероятно, впереди, но, похоже, метод immutable.ListMap.iterator решает обратить результат с toList.reverseIterator на возвращенном итераторе.Я думаю, что стоит внести это в список рассылки.

Может ли документация быть лучше?Конечно.Есть ли боль?Не совсем, я не позволю этому случиться.Если документация неполная, целесообразно проверить поведение или посмотреть на источник, прежде чем выбирать структуру, а не другую.

На самом деле, может возникнуть боль, если команда Scala решит изменить поведение на более позднем этапе.время и чувство, что они могут, потому что поведение эффективно недокументировано, и нет никакого контракта.

Чтобы рассмотреть ваш вариант использования, описанный в комментарии, скажем, вы собрали счетчик частоты строк на карте (изменяемой или неизменной): 

val map = Map("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18, "B" -> 5)

Поскольку вы тольконужно отсортировать один раз в конце, вы можете преобразовать кортежи с карты в seq и затем отсортировать: 

map.toSeq.sortBy(_._2)
// Seq[(java.lang.String, Int)] = ArrayBuffer((C,2), (A,5), (B,5), (D,9), (E,18))
4 голосов
/ 24 сентября 2011

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

Программирование в Scala объясняет, что ListMap может быть полезен, если более ранние элементы более доступны, но это в противному него мало преимуществ перед картой.

1 голос
/ 21 мая 2015

Не создавайте никаких ожиданий в отношении заказа, он не объявлен и будет варьироваться в зависимости от версии Scala.

Например: 

import scala.collection.mutable.{ListMap => MutableListMap}

MutableListMap("A" -> 5, "B" -> 12, "C" -> 2, "D" -> 9, "E" -> 18).foreach(println)

на 2.9.1 дает: (Е, 18) (Д, 9) (С, 2) (В, 12) (А, 5)

но на 2.11.6 выдает: (Е, 18) (С, 2) (А, 5) (В, 12) (Д, 9)

...