| Subject: | shuffle() and pick() extremely slow. |
List::Gen->pick came up on StackOverflow. See
http://stackoverflow.com/a/8963302/14660
I noticed its pick(P) algorithm shuffles the whole array and takes the
first P elements. This is O(NlogN) for speed (the cost of sorting) and
O(N) for memory where N is the size of the array.
A more efficient algorithm is to iterate through the array once, picking
each element with a probability of $picks_left / $elements_left. It
only goes through the array once and only stores the picked elements
making it O(N) for speed and O(P) for memory. It should work out faster
on large arrays. You can see this in perl5i's pick() method.
https://github.com/schwern/perl5i/blob/master/lib/perl5i/2/ARRAY.pm
perl5i's pick is two orders of magnitude faster than List::Gen's even
with very small arrays... which means there's something very wrong with
List::Gen. It pokes along at a few thousand a second on my top of the
line laptop.
List::Gen's shuffle algorithm is very slow. It would be better served
simply using List::Util's shuffle (three orders of magnitude faster) and
making a separate lazy_shuffle method. List::Gen::pick() does not need
a lazy shuffle and would be better served either using List::Util's
shuffle or using the algorithm from perl5i.
| Subject: | shuffle |
Message body not shown because it is not plain text.
| Subject: | pick |
Message body not shown because it is not plain text.