view release on metacpan or  search on metacpan

lib/Array/Shuffle.pm  view on Meta::CPAN

use warnings;

require XSLoader;
XSLoader::load('Array::Shuffle', $VERSION);

require Exporter;
our @ISA = qw(Exporter);
our @EXPORT_OK = qw(shuffle_array shuffle_huge_array);

1;
__END__

=head1 NAME

Array::Shuffle - fast shuffling of arrays in-place

=head1 SYNOPSIS

  use Array::Shuffle qw(shuffle_array);
  shuffle_array(@a);

=head1 DESCRIPTION

This module provide some functions for shuffling arrays in-place
efficiently.

=head2 API

=over 4

=item shuffle_array @a

Shuffles the given array in-place using the Fisher-Yates algorithm that
is O(N).

This function is an order of magnitude faster than the shuffle
function from L<List::Util>.

Note: that was true a long, long, long time ago. If you are worried
about performance, you should check it for yourself.

In most cases you should probably use L<List::Utils/shuffle> instead
of this obscure module!

=item shuffle_huge_array @a

Shuffles the given array in-place using an algorithm that is O(NlogN)
but more cache friendly than Fisher-Yates. In some extreme cases, when
shuffling huge arrays that do not find in the available RAM it may
perform better.

You would like to do some benchmarking to find out which one is better
suited for your particular case.

=back

=head1 SEE ALSO

L<List::Util>.

The following thread on PerlMonks for a discussion on the topic:
L<http://perlmonks.org/?node_id=953607>.

=head1 COPYRIGHT AND LICENSE

Copyright (C) 2012, 2021 by Salvador FandiE<ntilde>o (sfandino@yahoo.com)

This library is free software; you can redistribute it and/or modify
it under the same terms as Perl itself, either Perl version 5.14.2 or,
at your option, any later version of Perl 5 you may have available.

=head1 BENCHMARKS

Included in this package you can find the script samples/benchmark.pl
that compares the performance of the following shuffle algorithms and
implementations:

=over 4

=item pp

uses a Fisher Yates shuffle implemented in pure perl

=item ls

uses the C<shuffle> function from L<List::Util>

=item sa

uses the C<shuffle_array> method from this module

=item sha

uses the C<shuffle_huge_array> method from this module

=back

What follows is the output of this script running on an i386 virtual
machine with 64MB of RAM and several GB of swap running Ubuntu.

Note that the algorithms are selectively switched down when they
become too slow and in the C<sa> case, when it starts using swap
memory as at this point it just becomes unbearably slow.

  Generating array with 100 elements...
    PID TTY      STAT   TIME  MAJFL   TRS   DRS   RSS %MEM COMMAND
   2551 pts/0    S+     0:00     21  1416  5843  3076  5.6 benchmark.pl
        Rate    pp    lu   sha    sa
  pp   354/s    --  -77%  -94%  -94%
  lu  1534/s  333%    --  -73%  -73%
  sha 5697/s 1509%  271%    --   -0%
  sa  5697/s 1509%  271%    0%    --
  Generating array with 158 elements...
    PID TTY      STAT   TIME  MAJFL   TRS   DRS   RSS %MEM COMMAND
   2551 pts/0    S+     0:57     21  1416  5843  3212  5.8 benchmark.pl
        Rate    pp    lu   sha    sa
  pp   188/s    --  -83%  -95%  -95%
  lu  1109/s  489%    --  -69%  -72%
  sha 3618/s 1821%  226%    --  -10%
  sa  4003/s 2025%  261%   11%    --
  Generating array with 251 elements...