Scala: Liste Performance

Question

Doc dit

Heure: Liste a O (1) et la tête précédez/accès arrière. La plupart des autres opérations sont O (n) sur le nombre d'éléments dans la liste. Ce inclut la recherche indexée des éléments, longueur, append et inverse.

Docs "fièrement" mentionne que la plupart des opérations sont O (n). Même si elle est sauvegardée par une liste chaînée, les opérations de longueur et d'ajout peuvent facilement être faites à temps constant. Aussi pas sûr si je comprends pourquoi ce n'est pas une liste doublement liée, ce qui aurait fait l'opération inverse O (1).

C'est le mumbo jumbo fonctionnel, n'est-ce pas?

[EDIT] Quelle collection peut me donner O (1) pour toutes les opérations mentionnées ci-dessus?

Answer 1

L'immutabilité est la réponse. Ceci est une version simplifiée de la mise en œuvre de la liste

trait List[+A] { 
    def prepend[A1 >: A](a:A1): List[A] 
} 
case class Cons[A](head: A, tail: List[A]) extends List[A] { 
    def prepend[A1 >: A](a:A1): List[A1] = Cons(a, this) 
} 
case object Nil extends List[Nothing] { 
    def prepend[A1 >: A](a:A1): List[A1] = Cons(a, Nil) 
} 

Avec ce ADT vous êtes en mesure de préfixer mais pas créer une double liste liée. Faisons Sé un exemple

val list1 = Cons(1, Cons(2, Nil)) 
val list2 = Cons(0, list1) 
val list3 = Cons(-1, list1) 

Cela ne peut pas être mis en œuvre comme une liste doublylinked sans muter la valeur de list1 lorsque vous créez liste2 et liste3

Answer 2

Pour la plupart des cas, vous devez utiliser un vecteur au lieu d'une liste. Voici une comparaison des performances pour différentes collections Scala:

http://docs.scala-lang.org/overviews/collections/performance-characteristics.html