Łączenie listy Scala, ::: vs ++

362

Czy jest jakaś różnica pomiędzy :::i ++za łączeniem list w Scali?

scala> List(1,2,3) ++ List(4,5)
res0: List[Int] = List(1, 2, 3, 4, 5)

scala> List(1,2,3) ::: List(4,5)
res1: List[Int] = List(1, 2, 3, 4, 5)

scala> res0 == res1
res2: Boolean = true

Z dokumentacji wynika, że ++jest bardziej ogólna, podczas gdy :::jest Listspecyficzna. Czy to drugie jest zapewnione, ponieważ jest używane w innych językach funkcjonalnych?

Luigi Plinge
źródło
4
Również :::jest operatorem prefiks jak wszystkich metod zaczynając:
Ben Jackson
3
Odpowiedzi w zasadzie nakreślają sposób, w jaki Scala ewoluowała wokół list i jednolitości operatora w Scali (lub jej braku). Trochę niefortunne jest to, że coś tak prostego ma tak długi ogon drobiazgów, aby zmylić i zmarnować czas każdego ucznia Scali. Chciałbym, żeby został wyrównany w 2.12.
matanster

Odpowiedzi:

321

Dziedzictwo. Lista została pierwotnie zdefiniowana jako wyglądająca na języki funkcjonalne:

1 :: 2 :: Nil // a list
list1 ::: list2  // concatenation of two lists

list match {
  case head :: tail => "non-empty"
  case Nil          => "empty"
}

Oczywiście Scala ewoluowała inne kolekcje w sposób ad hoc. Kiedy pojawiła się wersja 2.8, kolekcje zostały przeprojektowane w celu maksymalnego ponownego wykorzystania kodu i spójnego interfejsu API, dzięki czemu można używać ++do łączenia dowolnych dwóch kolekcji - a nawet iteratorów. Lista jednak zachowała swoich pierwotnych operatorów, oprócz jednego lub dwóch, które stały się przestarzałe.

Daniel C. Sobral
źródło
19
Więc czy to najlepsza praktyka, której należy unikać :::na korzyść ++teraz? Użyj również +:zamiast ::?
Luigi Plinge
37
::jest przydatny ze względu na dopasowanie wzorca (patrz drugi przykład Daniela). Nie da się tego zrobić z+:
paradygmatycznym
1
@Luigi Jeśli używasz Listzamiast Seq, równie dobrze możesz użyć Listmetod idiomatycznych . Z drugiej strony utrudni to przejście na inny typ, jeśli kiedykolwiek będziesz tego chciał.
Daniel C. Sobral
2
Uważam, że dobrze jest mieć zarówno operacje idiomatyczne List (jak ::i :::), jak i bardziej ogólne operacje wspólne dla innych kolekcji. Nie usunęłbym żadnej operacji z języka.
Giorgio
21
@paradigmatic Scala 2.10 ma :+i wypakowuje +:obiekty.
0__
97

Zawsze używaj :::. Są dwa powody: wydajność i bezpieczeństwo typu.

Wydajność

x ::: y ::: zjest szybszy niż x ++ y ++ z, ponieważ :::ma właściwe skojarzenie. x ::: y ::: zjest analizowany jako x ::: (y ::: z), który jest algorytmicznie szybszy niż (x ::: y) ::: z(ten drugi wymaga O (| x |) więcej kroków).

Wpisz bezpieczeństwo

Z :::możesz połączyć tylko dwa Lists. Dzięki ++niemu możesz dołączyć dowolną kolekcję List, co jest okropne:

scala> List(1, 2, 3) ++ "ab"
res0: List[AnyVal] = List(1, 2, 3, a, b)

++jest również łatwy do zmieszania z +:

scala> List(1, 2, 3) + "ab"
res1: String = List(1, 2, 3)ab
ZhekaKozlov
źródło
9
Podczas łączenia tylko 2 list nie ma różnicy, ale w przypadku 3 lub więcej masz dobrą rację, a ja potwierdziłem to szybkim testem porównawczym. Jeśli jednak martwisz się wydajnością, x ::: y ::: znależy go zastąpić List(x, y, z).flatten. pastebin.com/gkx7Hpad
Luigi Plinge
3
Proszę wyjaśnić, dlaczego konkatenacja lewej asocjacji wymaga więcej kroków O (x). Myślałem, że oba działają dla O (1).
pacman
6
Listy @pacman są pojedynczo połączone, aby dołączyć jedną listę do drugiej, musisz wykonać kopię pierwszej listy, która ma drugą dołączoną na końcu. Łączenie wynosi zatem O (n) w odniesieniu do liczby elementów na pierwszej liście. Długość drugiej listy nie wpływa na środowisko wykonawcze, dlatego lepiej jest dołączyć długą listę do krótszej niż dołączać krótką listę do długiej.
puhlen
1
Listy @pacman Scala są niezmienne . Dlatego nie możemy po prostu zastąpić ostatniego linku podczas konkatenacji. Musimy stworzyć nową listę od podstaw.
ZhekaKozlov
4
@pacman Złożoność jest zawsze liniowa względem długości xi y( znigdy nie jest iterowana, więc nie ma wpływu na czas wykonywania, dlatego lepiej jest dołączyć długą listę do krótszej niż na odwrót), ale asymptotyczna złożoność nie opowiada całej historii. x ::: (y ::: z)iteruje yi dołącza z, a następnie iteruje xi dołącza wynik y ::: z. xi yoba są powtarzane raz. (x ::: y) ::: ziteruje xi dołącza y, a następnie iteruje wynik x ::: yi dołącza z. ywciąż jest powtarzany raz, ale xw tym przypadku jest powtarzany dwukrotnie.
puhlen
84

:::działa tylko z listami, a ++można go używać z każdym przejściem. W obecnej implementacji (2.9.0), ++spada z powrotem na :::jeśli argument jest również List.

paradygmatyczny
źródło
4
Jest więc bardzo łatwy w użyciu zarówno ::: jak i ++ pracujący z listą. To potencjalnie może zepsuć kod / styl.
ses
24

Inną kwestią jest to, że pierwsze zdanie jest analizowane jako:

scala> List(1,2,3).++(List(4,5))
res0: List[Int] = List(1, 2, 3, 4, 5)

Natomiast drugi przykład jest analizowany jako:

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

Więc jeśli używasz makr, powinieneś się zachować ostrożność.

Poza tym, ++dla dwóch list wywołuje się, :::ale z większym obciążeniem, ponieważ prosi o wartość domyślną, aby mieć konstruktora z listy do listy. Ale mikrobenchmarki nie okazały niczego przydatnego w tym sensie, myślę, że kompilator optymalizuje takie wywołania.

Mikro-Benchmarki po rozgrzaniu.

scala>def time(a: => Unit): Long = { val t = System.currentTimeMillis; a; System.currentTimeMillis - t}
scala>def average(a: () => Long) = (for(i<-1 to 100) yield a()).sum/100

scala>average (() => time { (List[Int]() /: (1 to 1000)) { case (l, e) => l ++ List(e) } })
res1: Long = 46
scala>average (() => time { (List[Int]() /: (1 to 1000)) { case (l, e) => l ::: List(e ) } })
res2: Long = 46

Jak powiedział Daniel C. Sobrai, możesz dołączyć zawartość dowolnej kolekcji do listy za pomocą ++, podczas gdy za pomocą :::możesz łączyć tylko listy.

Mikaël Mayer
źródło
20
Proszę zamieścić swoje niezbyt uproszczone mikrobenki, a ja je głosuję.
Mikaël Mayer,