CODEWITHSUNDEEP
scalacollections
Kakaji
Kakaji

Reputation: 1491

What is the fastest way to join two iterables (or sequences) in Scala?

Say I want to create an Iterable by joining multiple Iterables. What would be the fastest way to do so?

Documentation for ListBuffer's ++= says that it

Appends all elements produced by a TraversableOnce to this list buffer.

which sounds like it appends the elements one by one and hence should take Ω(size of iterable to append) time. I want something that joins the two Iterables in O(1) time. Does ::: method of List runs in O(1) time? Documentation simply states that it

Adds the elements of a given list in front of this list.

I also checked out performance characteristics of scala collections but it says nothing about joining two collections.

Upvotes: 1

Views: 951

Answers (1)

Oleg Pyzhcov
Oleg Pyzhcov

Reputation: 7353

You can create a Stream:

Stream(a, b, c).flatten

or concatenate iterators (this gives you Stream at runtime anyway)

(a.iterator ++ b.iterator ++ c.iterator).toIterable

(assuming that a, b and c are Iterable[Int])

That will give you something along the lines of O(number of collections to join)

Streams are evaluated on demand, so only little memory allocation will happen for closures until you actually request any elements. Converting to anything else is unavoidably O(n).

Upvotes: 2

Related Questions