The little gems of Scala standard library

If we dig deeper, under the hood of this method we can find the implementation of Knuth–Morris–Pratt algorithm which is a really clever algorithm for substring search.

It has a linear (O(n + m)) complexity even in the worst case (meaning — for any input possible).

If you try to benchmark Java indexOf vs Scala indesOfSlice on random inputs, I’m sure Java indexOf would win.

Simply because it specializes on Strings, while Scala indexOfSlice supports sequences of generic type.

Also, the implementation of the naive search algorithm has less overhead.

However, indexOfSlice has advantage whenever you have to be defensive against inputs that you do not control — for example, when your users can provide you with sufficiently large strings and trigger the search on them.

Also, linear vs quadratic complexity really matters in Competitive Programming.

Part of my current job is introducing new team members to Scala.

One of the things I ask them to do is to go over the documentation of a typical Scala collection class (such as IndexedSeq) a few times, in order to learn about the methods that can be useful in a day to day work, like the ones we have just discussed.

But I hope that even experienced Scala developers have learned something new from this blog post.

Do you think I have missed some useful methods of Scala collections?.Please share your favourite ones in the comments!.

. More details

Leave a Reply