best results from the CPAN

best

Algorithm-Networksort

view release on metacpan or search on metacpan

lib/Algorithm/Networksort/Best.pm view on Meta::CPAN

=pod

=encoding UTF-8

=head1 NAME

Algorithm::Networksort::Best - Optimized Sorting Networks.

=cut

package Algorithm::Networksort::Best;

use 5.010001;

use Algorithm::Networksort;
use Carp;
use Exporter;
use vars qw(@ISA %EXPORT_TAGS @EXPORT_OK);
use strict;
use warnings;

@ISA = qw(Exporter);

%EXPORT_TAGS = (
	'all' => [ qw(
		nwsrt_best
		nw_best_names
		nw_best_title
	) ],
);

@EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } );

our $VERSION = '2.02';

#
# The hashes represent each network, with a short, hopefully descriptive, key.
#
my %nw_best_by_name = (
	floyd09 => {
		inputs => 9,
		depth => 9,
		title => '9-input Network by Robert W. Floyd',
		comparators =>
		[[0,1], [3,4], [6,7], [1,2], [4,5], [7,8], [0,1], [3,4],
		[6,7], [0,3], [3,6], [0,3], [1,4], [4,7], [1,4], [2,5],
		[5,8], [2,5], [1,3], [5,7], [2,6], [4,6], [2,4], [2,3],
		[5,6]]},
	senso09 => {
		inputs => 9,
		depth => 8,
		title => '9-Input Network via SENSO by V. K. Valsalam and R. Miikkulainen',
		comparators =>
		[[2,6], [0,5], [1,4], [7,8], [0,7], [1,2], [3,5], [4,6],
		[5,8], [1,3], [6,8], [0,1], [4,5], [2,7], [3,7], [3,4],
		[5,6], [1,2], [1,3], [6,7], [4,5], [2,4], [5,6], [2,3],
		[4,5]]},
	waksman10 => {
		inputs => 10,
		depth => 9,
		title => '10-Input Network by A. Waksman',
		comparators =>
		[[4,9], [3,8], [2,7], [1,6], [0,5], [1,4], [6,9], [0,3],
		[5,8], [0,2], [3,6], [7,9], [0,1], [2,4], [5,7], [8,9],
		[1,2], [4,6], [7,8], [3,5], [2,5], [6,8], [1,3], [4,7],
		[2,3], [6,7], [3,4], [5,6], [4,5]]},
	senso10 => {
		inputs => 10,
		depth => 8,
		title => '10-Input Network via SENSO by V. K. Valsalam and R. Miikkulainen',
		comparators =>
		[[1,4], [7,8], [2,3], [5,6], [0,9], [2,5], [0,7], [8,9],
		[3,6], [4,9], [0,1], [0,2], [6,9], [3,5], [4,7], [1,8],
		[3,4], [5,8], [6,7], [1,2], [7,8], [1,3], [2,5], [4,6],
		[2,3], [6,7], [4,5], [3,4], [5,6]]},
	shapirogreen11 => {
		inputs => 11,
		depth => 9,
		title => '11-Input by G. Shapiro and M. W. Green',
		comparators =>
		[[0,1], [2,3], [4,5], [6,7], [8,9], [1,3], [5,7], [0,2],
		[4,6], [8,10], [1,2], [5,6], [9,10], [1,5], [6,10], [5,9],
		[2,6], [1,5], [6,10], [0,4], [3,7], [4,8], [0,4], [1,4],
		[7,10], [3,8], [2,3], [8,9], [2,4], [7,9], [3,5], [6,8],
		[3,4], [5,6], [7,8]]},
	senso11 => {
		inputs => 11,
		depth => 10,
		title => '11-Input Network via SENSO by V. K. Valsalam and R. Miikkulainen',
		comparators =>
		[[0,9], [2,8], [3,7], [4,6], [1,5], [1,3], [2,4], [6,10],
		[7,8], [5,9], [0,6], [1,2], [8,10], [9,10], [0,1], [5,7],
		[3,4], [6,8], [2,6], [1,5], [7,8], [4,9], [2,3], [8,9],
		[1,2], [4,6], [3,5], [6,7], [7,8], [2,3], [4,6], [5,6],
		[3,4], [6,7], [4,5]]},
	shapirogreen12 => {
		inputs => 12,
		depth => 9,
		title => '12-Input by G. Shapiro and M. W. Green',

lib/Algorithm/Networksort/Best.pm view on Meta::CPAN

		[16, 17], [18, 19], [20, 21], [1, 3], [5, 7], [9, 11], [0, 2], [4, 6],
		[8, 10], [13, 15], [17, 19], [12, 14], [16, 18], [20, 22], [1, 2], [5, 6],
		[9, 10], [13, 14], [17, 18], [21, 22], [1, 5], [6, 10], [13, 17], [18, 22],
		[5, 9], [2, 6], [17, 21], [14, 18], [1, 5], [6, 10], [0, 4], [7, 11],
		[13, 17], [18, 22], [12, 16], [3, 7], [4, 8], [15, 19], [16, 20], [0, 4],
		[7, 11], [12, 16], [1, 4], [7, 10], [3, 8], [13, 16], [19, 22], [15, 20],
		[2, 3], [8, 9], [14, 15], [20, 21], [2, 4], [7, 9], [3, 5], [6, 8],
		[14, 16], [19, 21], [15, 17], [18, 20], [3, 4], [5, 6], [7, 8], [15, 16],
		[17, 18], [19, 20], [0, 12], [1, 13], [2, 14], [3, 15], [4, 16], [5, 17],
		[6, 18], [7, 19], [8, 20], [9, 21], [10, 22], [2, 12], [3, 13], [10, 20],
		[11, 21], [4, 12], [5, 13], [6, 14], [7, 15], [8, 16], [9, 17], [10, 18],
		[11, 19], [8, 12], [9, 13], [10, 14], [11, 15], [6, 8], [10, 12], [14, 16],
		[7, 9], [11, 13], [15, 17], [1, 2], [3, 4], [5, 6], [7, 8], [9, 10],
		[11, 12], [13, 14], [15, 16], [17, 18], [19, 20], [21, 22]]},
	senso23 => {
		inputs => 23,
		depth => 22,
		title => '23-Input Network via SENSO by V. K. Valsalam and R. Miikkulainen',
		comparators =>
		[[1,20], [2,21], [5,13], [9,17], [0,7], [15,22], [4,11], [6,12],
		[10,16], [8,18], [14,19], [3,8], [4,14], [11,18], [2,6], [16,20],
		[0,9], [13,22], [5,15], [7,17], [1,10], [12,21], [8,19], [17,22],
		[0,5], [20,21], [1,2], [18,19], [3,4], [21,22], [0,1], [19,22],
		[0,3], [12,13], [9,10], [6,15], [7,16], [8,11], [11,14], [4,11],
		[6,8], [14,16], [17,20], [2,5], [9,12], [10,13], [15,18], [10,11],
		[4,7], [20,21], [1,2], [7,15], [3,9], [13,19], [16,18], [8,14],
		[4,6], [18,21], [1,4], [19,21], [1,3], [9,10], [11,13], [2,6],
		[16,20], [4,9], [13,18], [19,20], [2,3], [18,20], [2,4], [5,17],
		[12,14], [8,12], [5,7], [15,17], [5,8], [14,17], [3,5], [17,19],
		[3,4], [18,19], [6,10], [11,16], [13,16], [6,9], [16,17], [5,6],
		[4,5], [7,9], [17,18], [12,15], [14,15], [8,12], [7,8], [13,15],
		[15,17], [5,7], [9,10], [10,14], [6,11], [14,16], [15,16], [6,7],
		[10,11], [9,12], [11,13], [13,14], [8,9], [7,8], [14,15], [9,10],
		[8,9], [12,14], [11,12], [12,13], [10,11], [11,12]]},
	morwenn24 => {
		inputs => 24,
		depth => 18,
		title => '24-Input Network by Morwenn',
		comparators =>
		[[0,1], [2,3], [4,5], [6,7], [8,9], [10,11], [12,13], [14,15],
		[16,17], [18,19], [20,21], [22,23], [1,3], [5,7], [9,11], [0,2],
		[4,6], [8,10], [13,15], [17,19], [21,23], [12,14], [16,18], [20,22],
		[1,2], [5,6], [9,10], [13,14], [17,18], [21,22], [1,5], [6,10],
		[13,17], [18,22], [5,9], [2,6], [17,21], [14,18], [1,5], [6,10],
		[0,4], [7,11], [13,17], [18,22], [12,16], [19,23], [3,7], [4,8],
		[15,19], [16,20], [0,4], [7,11], [12,16], [19,23], [1,4], [7,10],
		[3,8], [13,16], [19,22], [15,20], [2,3], [8,9], [14,15], [20,21],
		[2,4], [7,9], [3,5], [6,8], [14,16], [19,21], [15,17], [18,20],
		[3,4], [5,6], [7,8], [15,16], [17,18], [19,20], [0,12], [1,13],
		[2,14], [3,15], [4,16], [5,17], [6,18], [7,19], [8,20], [9,21],
		[10,22], [11,23], [2,12], [3,13], [10,20], [11,21], [4,12], [5,13],
		[6,14], [7,15], [8,16], [9,17], [10,18], [11,19], [8,12], [9,13],
		[10,14], [11,15], [6,8], [10,12], [14,16], [7,9], [11,13], [15,17],
		[1,2], [3,4], [5,6], [7,8], [9,10], [11,12], [13,14], [15,16],
		[17,18], [19,20], [21,22]]},
);

#
# The hash that will return the keys by input number.
#
my %nw_best_by_input;

#
# Set up %nw_best_by_input.
#
INIT
{
	for my $k (keys %nw_best_by_name)
	{
		my $inputs = ${$nw_best_by_name{$k}}{inputs};

		if (exists $nw_best_by_input{$inputs})
		{
			push @{$nw_best_by_input{$inputs}}, $k;
		}
		else
		{
			$nw_best_by_input{$inputs} = [$k];
		}
		#print STDERR "$inputs: " . join(", ", @{$nw_best_by_input{$inputs}}) . "\n";
	}
}

=head1 SYNOPSIS

    use Algorithm::Networksort;
    use Algorithm::Networksort::Best qw(:all);

    my $inputs = 9;

    #
    # First find if any networks exist for the input size.
    #
    my @nwkeys = nw_best_names($inputs);

    #
    # For each sorting network, show the comparators.
    #
    for my $name (@nwkeys)
    {
        my $nw = nwsrt_best(name => $name);

        #
        # Print the list, and print the graph of the list.
        #
        print $nw->title(), "\n", $nw->formatted(), "\n\n";
        print $nw->graph_text(), "\n\n";
    }

=head1 DESCRIPTION

For some inputs, sorting networks have been discovered that are more efficient
than those generated by rote algorithms. The "Best" module allows you to use
those networks instead.

There is no guarantee that it will return the best network for
all cases. Usually "best" means that the module will return a lower number of
comparators for the number of inputs than the algorithms in Algorithm::Networksort
will return. Some will simply have a lower number of comparators, others may have
a smaller depth but an equal or greater number of comparators.

The current networks are:

=head2 9-Input Networks

=over 4

=item 'floyd09'

A 9-input network of depth 9 discovered by R. W. Floyd. Of interest also
because it is using what are essentially three-way comparators split into
three sets of two-way comparators.

=item 'senso09'

A 9-input network of depth 8 found using the SENSO program by
V. K. Valsalam and R. Miikkulaainen.

=back

=head2 10-Input Networks

=over 4

=item 'waksman10'

A 10-input network of depth 9 found by A. Waksman.

=item 'senso10'

A 10-input network of depth 8 found using the SENSO program by
V. K. Valsalam and R. Miikkulaainen.

=back

=head2 11-Input Networks

=over 4

=item 'shapirogreen11'

An 11-input network of depth 9 found by G. Shapiro and M. W. Green.

=item 'senso11'

A 11-input network of depth 10 found using the SENSO program by
V. K. Valsalam and R. Miikkulaainen.

=back

=head2 12-Input Networks

=over 4

=item 'shapirogreen12'

A 12-input network of depth 9 found by G. Shapiro and M. W. Green.

lib/Algorithm/Networksort/Best.pm view on Meta::CPAN


=back

=head2 21-Input Networks

=over 4

=item 'senso21'

A 21-input network of depth 20 found using the SENSO program by
V. K. Valsalam and R. Miikkulaainen.

=back

=head2 22-Input Networks

=over 4

=item 'alhajbaddar22'

22-input network of depth 12 found by Sherenaz Waleed Al-Haj Baddar.

=item 'senso22'

A 22-input network of depth 15 found using the SENSO program by
V. K. Valsalam and R. Miikkulaainen.

=back

=head2 23-Input Networks

=over 4

=item 'morwenn23'

A 23-input network of depth 18 found by Morwenn, by taking the 24-input
network and removing the final input.

=item 'senso23'

A 23-input network of depth 22 found using the SENSO program by
V. K. Valsalam and R. Miikkulaainen.

=back

=head2 24-Input Networks

=over 4

=item 'morwenn24'

A 24-input network of depth 18 found by Morwenn
L<https://github.com/Morwenn/cpp-sort/wiki/Original-research#sorting-networks-23-and-24>.

=back

=head2 Export

None by default. There is only one available export tag, ':all', which
exports the functions to create and use sorting networks. The functions are
nwsrt_best(), nw_best_names(), and nw_best_title().

=head2 Functions

=head3 nwsrt_best

Return the Algorithm::Networksort object, given a key name. Also takes
an optional title to override the default.

    $nw = nwsrt_best(name => 'floyd09', title => "Compare depth to Bose-Nelson");

=cut

sub nwsrt_best
{
	my(%opts) = @_;

	croak "No network chosen" unless (exists $opts{name});
	my $name = $opts{name};

	croak "Unknown network name '$name'" unless (exists $nw_best_by_name{$name});
	my %nw_struct = %{ $nw_best_by_name{$name} };
	my $title = $opts{title} // $nw_struct{title};

	return Algorithm::Networksort->new(
		algorithm => 'none',
		inputs => $nw_struct{inputs},
		comparators => $nw_struct{comparators},
		depth => $nw_struct{depth},
		title => $title,
		nwid => $name,
	);
}

=head3 nw_best_names

Return the list of keys for sorting networks of a giving input size.

    @names = nw_best_names(13);

Each name key is a valid option for the name argument of nwsrt_best().

An unlikely example:

    my $inputs = 12;

    for my $name (nwsrt_best_names($inputs))
    {
    	my $nw = nwsrt_best(name => $name);
    	print $nw->title(), "\n", $nw, "\n";
    }

To get the list of all available names (regardless of input size), simply
call the function with no argument:

    my @names = nwsrt_best_names();

=cut

sub nw_best_names
{
	my($inputs) = @_;

	return keys %nw_best_by_name unless (defined $inputs);

	unless (exists $nw_best_by_input{$inputs})
	{
		carp "No 'best' sorting networks exist for size $inputs";
		return ();
	}

	return @{$nw_best_by_input{$inputs}};
}

=head3 nw_best_title

Return a descriptive title for the network, given a name key.

    $title = nw_best_title($key);

These are the titles for the available networks. By themselves, they provide
a readable list of choices for an interactive program. They are not to be
confused with a sorting network's title, which may be set by the programmer.

=cut

sub nw_best_title
{
	my $key = shift;
	
	unless (exists $nw_best_by_name{$key})
	{
		carp "Unknown 'best' name '$key'.";
		return "";
	}

	return $nw_best_by_name{$key}{title};
}

1;
__END__

=head1 ACKNOWLEDGMENTS

L<Doug Hoyte|https://github.com/hoytech> pointed out Sherenaz Waleed
Al-Haj Baddar's paper.

L<Morwenn|https://github.com/Morwenn> found for me the SAT and SENSO
papers, contributed 23-input and 24-input sorting networks, and caught
documentation errors.

=head1 SEE ALSO

=head2 Non-algorithmic discoveries

=over 3

=item

The networks by Floyd, Green, Shapiro, and Waksman are in
Donald E. Knuth's B<The Art of Computer Programming, Vol. 3:
Sorting and Searching> (2nd ed.), Addison Wesley Longman Publishing Co., Inc.,
Redwood City, CA, 1998.

=item

The Evolving Non-Determinism (END) algorithm by Hugues Juillé has found
more efficient sorting networks:
L<http://www.cs.brandeis.edu/~hugues/sorting_networks.html>.

=item

The 18 and 22 input networks found by Sherenaz Waleed Al-Haj Baddar
are described in her dissertation "Finding Better Sorting Networks" at
L<http://etd.ohiolink.edu/view.cgi?acc_num=kent1239814529>.

=item

The 16 input network found by David C. Van Voorhis is described in chapter
5 of B<Designing Sorting Networks>, by Sherenaz W. Al-Haj Baddar and Kenneth E.
Batcher.

=item

The Symmetry and Evolution based Network Sort Optimization (SENSO) found more
networks for inputs of 9 through 23.

=item

Morwenn's 23 and 24-input networks are described at
L<https://github.com/Morwenn/cpp-sort/wiki/Original-research#sorting-networks-23-and-24>.

=item

Ian Parberry, "A computer assisted optimal depth lower bound for sorting
networks with nine inputs", L<http://www.eng.unt.edu/ian/pubs/snverify.pdf>.

( run in 0.502 second using v1.01-cache-2.11-cpan-524268b4103 )