How to sort an Iterable without creating intermediate Seq?

Question

I have a Map of String -> Foo and I want to get a sorted collection of Foos by Foo.priority:

fooMap.collect { case (k, f) if k.startWith("F") => f }.toSeq.sortBy(_.priority)

How can I avoid the intermediate toSeq? Can I create a new collection and insert by the ordering? Maybe something like:

fooMap.collect { case (k, f) if k.startWith("F") => f }.to[Seq](orderedCanBuildFrom) //does not work

Can you explain why you want to do this? What is the problem with converting to a suitable collection type before sorting? — Tim
– Tim, Commented Sep 4, 2019 at 15:36
@Tim Performance concerns. We have a very large collection to sort, and very tight memory allocation and latency requirement. — SwiftMango
– SwiftMango, Commented Sep 4, 2019 at 15:38
@texasbruce Can it take any value or only the limited set (like [1,2,3..100])? Maybe you should go for counting sort? — Krzysztof Atłasik
– Krzysztof Atłasik, Commented Sep 4, 2019 at 16:26

Tim · Accepted Answer · 2019-09-04 15:50:14Z

4

You can't sort an Iterable directly, and the insertion sort that you describe is going to be very slow for large collections.

The best option is probably to convert to Array and use the scala.util.sorting package which provides in-place sorting of Arrays.

answered Sep 4, 2019 at 15:50

Tim

27.6k2 gold badges18 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Volty De Qua · Accepted Answer · 2019-09-04 17:20:12Z

2

Since you say you are tight on memory and latency, try this

fooMap.view.filter(_._1.startsWith("F")).map(_._2).toSeq.sortBy(_.priority)

Otherwise consider buying more memory and/or speed :).

answered Sep 4, 2019 at 17:20

Volty De Qua

2981 silver badge7 bronze badges

Comments

SwiftMango · Accepted Answer · 2019-09-04 18:20:26Z

1

For Scala 2.12 and below, I use a custom CanBuildFrom to allow map/collect to transform into a different collection type. scala.collection.breakOut does this automatically:

import scala.collection.breakOut

fooMap.collect[Foo, Seq[Foo]]  { 
  case (k, f) if k.startWith("F") => f
}(breakOut).sortBy(_.priority)

For Scala 2.13 and above, since CanBuildFrom and breakOut is no longer available and Views are more reliable, I would use a view as stated in @volty-de-qua 's answer, since only from 2.13 that collection.Views have been vastly simplified and should now work reliably.

edited Sep 4, 2019 at 18:20

answered Sep 4, 2019 at 18:06

SwiftMango

15.4k14 gold badges79 silver badges140 bronze badges

Collectives™ on Stack Overflow

How to sort an Iterable without creating intermediate Seq?

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related