¿Cuál es una forma eficiente de concatenar listas?

Question

Cuando tenemos dos listas a y b, ¿cómo se pueden concatenar esas dos (orden no es relevante) a una nueva lista de una manera eficiente?

No pude entenderlo desde la API de Scala, si a ::: b y a ++ b son eficientes. Tal vez me perdí algo.

Answer 1

En Scala 2.9, el código para ::: (prepend a la lista) es como sigue:

def :::[B >: A](prefix: List[B]): List[B] = 
    if (isEmpty) prefix 
    else (new ListBuffer[B] ++= prefix).prependToList(this) 

mientras que ++ es más genérico, ya que toma un parámetro CanBuildFrom, es decir, se puede devolver un tipo de colección diferente de List:

override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[List[A], B, That]): That = { 
    val b = bf(this) 
    if (b.isInstanceOf[ListBuffer[_]]) (this ::: that.seq.toList).asInstanceOf[That] 
    else super.++(that) 
} 

Así que si su tipo de retorno es List, los dos realizan idénticas.

El ListBuffer es un mecanismo ingenioso en el sentido de que se puede usar como un generador de mutaciones, pero eventualmente "consumido" por el método toList. Entonces, ¿qué (new ListBuffer[B] ++= prefix).prependToList(this) hace, primero se agrega secuencialmente todos los elementos en prefix (en el ejemplo a), teniendo O (| a |) vez. Luego llama al prependToList, que es una operación de a tiempo constante (no es necesario separar el receptor o b). Por lo tanto, el tiempo total es O (| a |).

En el otherhand, como PST señaló, tenemos reverse_::::

def reverse_:::[B >: A](prefix: List[B]): List[B] = { 
    var these: List[B] = this 
    var pres = prefix 
    while (!pres.isEmpty) { 
    these = pres.head :: these 
    pres = pres.tail 
    } 
    these 
} 

Así que con a reverse_::: b, esta vez toma O (| a |), por lo tanto, no es más o menos eficiente que los otros dos métodos (aunque para tamaños de lista pequeños, se ahorra la sobrecarga de tener una creación intermedia de ListBuffer).

---

En otras palabras, si usted tiene conocimiento acerca de los tamaños relativos de a y b, usted debe asegurarse de que el prefijo es el más pequeño de las dos listas. Si usted no tiene ese conocimiento, no hay nada que puede hacer, ya que la operación size en un List toma O (N) :)

---

Por otro lado, en una versión futura de Scala puede ver una mejoró el algoritmo de concatenación Vector, como se demuestra en this ScalaDays talk. Promete resolver la tarea en el tiempo O (log N).