Long ago we made all maps and sets “linked” because it was really confusing in many practical applications. If you want a hashset for performance/memory reasons (you measured, right?) you can use

toCollection(HashSet())

no, i haven't measured, but I try to watch out for death-by-a-thousand-cuts type situations. of course, java is riddled with these already. but lots of tiny operations that are only 20% more expensive, but which are scattered all over the codebase, can add up and then be hard to detect or fix.

that said, i agree using a LinkedHashSet is less confusing

other issue here is that

distinct()

should use

toCollection(HashSet())

itself not to depend on

toMutableSet()

implementation

you mean

toCollection(LinkedHashSet())

yep

Not really a sound comparison, but this same issue was measured for JavaScript, as it turned out the overhead of a linked implementation was actually not that much.

I've just implemented the Knuth-Morris-Pratt String Matching algorithm in Kotlin, which can be used to find the occurrences of a pattern in a long text in linear time. Would you like to see a PR for it? Not sure if there's interest in it, but I figured I'd just ask simple smile I've seen someone looking for a method like this a few weeks ago in this Slack. This is what it looks like: https://gist.github.com/cbruegg/dada72b6c39e906d093b

@cbruegg: isn't something like that in the jdk standard library already? if not, why not submit it?

@mikehearn As far as I know, there's only indexOf, which returns only one index. It also does naive string matching (at least in OpenJDK 8). I'm currently preparing the pull request, just need to write some tests first.

ok. it seems more useful for it to be submitted to OpenJDK on the core-libs-dev list, than to kotlin specifically

I mean, useful long term

obviously in the short term it's more convenient to have it in a library

@mikehearn: shouldn't it return a lazy sequence as well?

perhaps it also should consume

CharSequence

rather than

String

or even

Reader

@mikehearn Not a bad idea either, I'll consider it. @cy I'll change it to return to a sequence and accept a CharSequence or Reader.

why is

pi

not an

IntArray

?

and I think using local functions will hurt performance

(0..length - 1).forEach

could also be replaced by a simple for loop for better performance

It is an IntArray in a revised version, it's just that the snippet hasn't updated from the Gist changes. Thanks for the feedback!

computePrefixFunction

could also be an extension function

I've tried making it a local inline function, but it looks like the compiler doesn't support that yet. I'm thinking of making it a private inline function, as it's really only useful within the

occurencesOf

method. I could also manually inline it in

occurencesOf

, but that looks a little bloaty to me.

I'd go for private inline

or just private

Just private sounds reasonable.

Here's a revised version, using IntArray, non-local

computePrefixFunction

, regular

for

-loops and it now returns a lazy `Sequence<Int>`: https://gist.github.com/cbruegg/dada72b6c39e906d093b

Oh, and it now accepts

CharSequence

.

you don't need an initializer for

val resultTable = IntArray(pattern.length)

the array will be filled with 0s by default

where is

sequence

defined?