0

There are two approaches for list concatenation in scala: ::: and ++. For instance, there are 3 lists - x, y, z. I heard that x ::: y ::: z is faster than x ++ y ++ z, because ::: is right associative. x ::: y ::: z is parsed as x ::: (y ::: z). My questions are next:

  1. Is the term above true?
  2. What is the time complexity both of ::: and ++.
Yuval Itzchakov
  • 146,575
  • 32
  • 257
  • 321
pacman
  • 797
  • 10
  • 28

1 Answers1

1

Is term above true

No, both take O(n) time to concat the lists. ::: is right associative, it will it'll concat y and z first, and then x (x ::: (y ::: z)), where ++ will concat x and y first, and then z ((x ++ y) ++ z).

What is the time complexity both of ::: and ++.

O(n). Specifically, ++ on List[A] is optimized to use ::: internally if we're concatenating two lists:

override def ++[B >: A, That](that: GenTraversableOnce[B])
                             (implicit bf: CanBuildFrom[List[A], B, That]): That =
  if (bf eq List.ReusableCBF) (this ::: that.seq.toList).asInstanceOf[That]
  else super.++(that)
Yuval Itzchakov
  • 146,575
  • 32
  • 257
  • 321
  • thx for the answer, please explain me why `:::` is faster than `++` – pacman Jan 02 '17 at 18:29
  • @pacman It is not. As I've said, `++` on `List[A]` will internally call `:::`. Both take O(n) time – Yuval Itzchakov Jan 02 '17 at 18:29
  • in this article i read that `:::` is faster than `++` https://stackoverflow.com/questions/6559996/scala-list-concatenation-vs – pacman Jan 02 '17 at 18:30
  • did you got what i meant? – pacman Jan 02 '17 at 18:34
  • @pacman I'm not sure why the OP wrote that. The implementation detail is that `++` is optimized to use `:::` anyway, so you shouldn't notice any performance differences here. I'll try to interpet what he meant in that answer. – Yuval Itzchakov Jan 02 '17 at 18:35
  • ok, why list concatenations takes O(n) instead O(1), we can append each element of prefix with O(1) and it still O(1) – pacman Jan 02 '17 at 18:37
  • @pacman *we can append each element of prefix with O(1) and it still O(1)* Can you elaborate on what that means? I didn't understand that statement. – Yuval Itzchakov Jan 02 '17 at 18:45
  • I get why it takes `O(n)`. Do you think that `:::` is faster than `++` because `:::` won't iterate through x - first prefix? – pacman Jan 02 '17 at 18:54
  • @pacman Why would it not iterate `x`? How would it combine it's elements with those of `y ::: z`? We get `z.:::(y).:::(x)`, so we only iterate `y` and `x`. Same way around for `++`, we have `x.++(y).++(z)`, so we iterate `y` and `z`. – Yuval Itzchakov Jan 02 '17 at 18:56
  • i think, that both of them will take `O(n)` where n = x + y + z. Do you agree with me? – pacman Jan 02 '17 at 18:58
  • Well there is a point about `(x ::: (y ::: z))` vs `((x ::: y) ::: z)` I think. The first one would need |y| + |x| prepends while the second would need |x| + |x| + |y| prepends because it would have to traverse elements from x twice. – Łukasz Jan 02 '17 at 19:48
  • @Łukasz Wouldn't the first one be |y| + |y| + |z|? We're first prepending `y` to `z`, and then the concatenation of them to `x`, as in the second be |x| + |x| + |y|? – Yuval Itzchakov Jan 02 '17 at 19:54
  • As far as I understand to prepend x to y (x ::: y) I need to traverse x in reverse order and prepending each element to y. So in the first case I need to traverse whole y and then to the resulting list prepend whole x. In the second case I first traverse x to prepend it to y and then I need to traverse whole combined x and y to prepend it to z. I might be wrong but this is how I understand it. – Łukasz Jan 02 '17 at 19:58
  • @Łukasz It doesn't reverse the list. It uses a `ListBuffer` internally, which for each insertion switches the order of tail with the current appended element, and then prepends the entire list in O(1). – Yuval Itzchakov Jan 02 '17 at 20:07
  • It was just a concept what would be needed if we were immutable. Anyway to arepend a list we need a copy of it and then change the pointer in last element to head of the other list, right? Hence for copying we have O(n) and my calculations from the first comment are fine. Or am I wrong? – Łukasz Jan 03 '17 at 06:38
  • @ Łukasz I suppose that @ Yuval Itzchakov is right, it looks logically `(x ::: (y ::: z))` need traverse only y and z, in the second case - x and y. `:::` is a same as an invocation of next flow: `List(1, 2) ::: List(3, 4) = List(3, 4).:::(List(1, 2)) = List(1, 2, 3, 4)`, here we need go through only a first `List`, we don't need to iterate `List(3,4)` –  Jan 05 '17 at 23:10