Proposal: Make size (from 'unordered-containers') run in constant time

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Proposal: Make size (from 'unordered-containers') run in constant time

Alexandre Rodrigues

Greetings;

 

This email's purpose is to request comments from this mailing list regarding a PR to ‘unordered-containers’ (here: https://github.com/tibbe/unordered-containers/pull/170).

 

This PR modifies the existing code so that ‘size’ can calculate the size of a ‘Hash{Map, Set}’ in constant time instead of linear, which is its current performance.

 

To avoid making this message too large, the benchmarking results are not included here, but you may find them in the PR’s discussion. In short, a penalty of about 10% to functions in the library may be expected, and both ‘filterWithKey’ and ‘fromListWith’ are much slower, which is an issue I’d like to solve.

 

If this PR is mediocre, if you have any suggestions to make it better, or any other comment, please reply to this email.

 

I'd like to thank David Feuer and Niklas Hambüchen for the many improvements suggested to this PR, and Johan Tibell for writing an excellent library.


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries