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

Make groupsOf and greedyGroupsOf fn families tail-recursive #157

Closed Janiczek closed 2 years ago

Janiczek commented 2 years ago

Closes #75

I've hit this during Advent of Code 😭 😄

Chadtech commented 2 years ago

Thanks for looking into this. Sorry for the delay, but I will check out this PR ASAP (later today or tomorrow).

Chadtech commented 2 years ago

I just benchmarked this here: https://ellie-app.com/gm9X8yfPLXMa1 (with a one small adjustment: I pulled go out into a top level function). There seems to be a performance drop primarily on small lists and small group sizes.

(Ignore the fact that its labelled "isPermutationOf". Thats because I copy and pasted the "isPermutationOf" benchmark to get started). Screen Shot 2022-01-08 at 02 56 25 Screen Shot 2022-01-08 at 02 56 37 Screen Shot 2022-01-08 at 02 56 52

Is it worth it? Probably. But what do you all think?

Janiczek commented 2 years ago

Is it worth it?

I'd consider it worth it, as correctness issues IMHO should have more priority than performance issues

jfmengels commented 2 years ago

I agree with @Janiczek, correctness is more important than performance (at least as a generally available function like this). In a way, it's good that it's slower mostly for the small inputs because performance increases for those don't matter too much in the big picture anyway (I mean, you can still call this function 2 million times per second apparently!).

Chadtech commented 2 years ago

Sounds good to me. Thanks @Janiczek !