¿Por qué los ListMaps mutables e inmutables tienen diferentes pedidos en Scala?

Question

¿Por qué la versión inmutable de ListMap se almacena en orden ascendente, mientras que la versión mutable se almacena en orden descendente?

Aquí es una prueba de que se puede utilizar si tienes scalatest-1.6.1.jar y 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) 
    } 

Aquí está la salida de la prueba de adelantamiento:

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) 

Answer 1

los síntomas pueden simplificarse a:

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) 

la "clasificación" en el código no es el centro de la cuestión, su llamada a ListMap está utilizando la llamada ListMap.apply del objeto complementario que construye un mapa de lista respaldado por una lista mutable o inmutable. La regla es que se preservará el orden de inserción.

La diferencia parece ser que la lista mutable está respaldada por una lista inmutable y la inserción se realiza en la parte frontal. Entonces, es por eso que al iterar obtienes el comportamiento de LIFO. Todavía estoy mirando el inmutable, pero apuesto a que los insertos están efectivamente en la parte posterior. Editar, voy a cambiar de idea: insert están probablemente en la parte frontal, pero parece que el método immutable.ListMap.iterator decide invertir el resultado con un toList.reverseIterator en el iterador devuelto. Creo que vale la pena incluirlo en la lista de correo.

¿Podría la documentación ser mejor? Ciertamente. Hay dolor? No realmente, no dejo que suceda. Si la documentación está incompleta, es conveniente probar el comportamiento o buscar en la fuente antes de elegir una estructura en lugar de otra.

En realidad, puede haber dolor si el equipo de Scala decide cambiar el comportamiento en un momento posterior y sienten que pueden porque el comportamiento es efectivamente indocumentado y no hay contrato.

---

Para hacer frente a su caso de uso se explica en el comentario, decir que usted ha recogido el cálculo de la frecuencia de cadena en un mapa (mutable o inmutable):

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

ya que sólo necesita para ordenar una vez al final, puede convertir las tuplas del mapa a un seq y luego ordenar:

map.toSeq.sortBy(_._2) 
// Seq[(java.lang.String, Int)] = ArrayBuffer((C,2), (A,5), (B,5), (D,9), (E,18)) 

Answer 2

Tal como lo veo ni ListMap dice ser un mapa ordenada, sólo un mapa implementado con una lista. De hecho, no veo nada en su contrato que diga nada sobre la preservación del orden de inserción.

La programación en Scala explica que ListMap puede ser útil si es más probable que se acceda a los primeros elementos, pero que de otro modo tiene poca ventaja sobre Map.

Answer 3

No genere ninguna expectativa sobre pedido, no está declarado y variará según las versiones de Scala.

Por ejemplo:

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

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

En 2.9.1 da: (E, 18) (D, 9) (C, 2) (B, 12) (A, 5)

pero en 2.11.6 da: (E, 18) (C, 2) (a, 5) (B, 12) (D, 9)