search

elm-community / list-extra

Convenience functions for working with List.
http://package.elm-lang.org/packages/elm-community/list-extra/latest
MIT License
135 stars 58 forks source link

isPermutationOf performance increase #155

Closed Chadtech closed 2 years ago

Chadtech commented 2 years ago

We just merged in some big performance gains for isPermutationOf from @lue-bird , and since then @jfmengels gave some tips on how to further increase the performance. Namely: (0) dont curry arguments, (1) define all helper functions at the top level, and (2) Re-arrange case and if statements so that the most common cases are branched to earlier.

I followed his advice and I saw performance gains between 270% and 340% depending on the inputs

Chadtech commented 2 years ago

Pinging @gampleman @Janiczek too, just in case you are interested as well.

gampleman commented 2 years ago

LGTM.

Also I wonder if a note about the complexity of the algorithm isn't in order? By my squint, this is still quadratic, right? I think having a little warning about things that can grow their runtime steeply may well be in order.