Algorithm-Networksort
view release on metacpan or search on metacpan
with function textsettings(), as making graphsettings()
handle it all was ridiculous, not to mention the key
collisions with the changes above.
- Check for "monotone" diagrams. If all the colors are
the same, just set the color once in the SVG or
EPS output instead of setting the color for each part
of the diagram, resulting in a smaller file.
- Update the t/ and eg/ files to use the above changes.
Sun Jan 14 2018
- Test file best.t only skips networks of input size > 16
instead of all skipping all networks if AUTHOR_TESTING
isn't set.
Fri Jan 12 2018
- Added Designing Sorting Networks to the book list.
- Added David C. Van Voorhis's 16-input network (found in
Designing Sorting Networks) to Best.pm.
2.01
Wed Apr 20 2016
- Add nwsrt_title() to the list of default exported functions
in Networksort.pm for consistency with ::Best.pm and for the
- Grey background in SVG at begining lightened up.
2.00
Tue Apr 12 2016
- The module now returns the sorting network as an object.
This is obviously a major change; please see the documentation
for reassuring examples. The OO basis is Moose, plus
Moose::Exporter for a couple of convenience functions. The
function-heavy Version 1.30 will remain on CPAN for at
least another year in the mean time.
- The collection of 'best' networks has been greatly added to,
thanks to the efforts of Morwenn. These networks now reside
in their own child module, Algorithm::Networksort::Best.
It could be argued that the module should be named
Algorithm::Networksort::Optimal, but 'optimal' has seven
letters and 'best' has four, so 'best' wins.
- Doug Hoyte provided code for an astonishing three more
algorithms: odd-even merge, odd-even transposition, and balanced.
- The example scripts in eg/ have been updated and in some
cases improved.
- Found untested cases (formats in particular) and added them
to the tests.
- SVG output is massively improved. The graphing example is now
HTML5 instead of XML, beginning circles now cover their line
instead of vice versa, background color is now supported, and
the ids of graph elements now have a random component in them
- Update documentation to make sure 'bitonic' is mentioned.
- Got svg.t to work correctly in systems that don't have
Test::XML::Easy installed.
- Heavily update README to cover testing, and Doug Hoyte's
contributions.
Sun Nov 18 2012
- Consolidated the "algorithm" test files into one file,
abecedarian.t. Now that we're using $ENV{AUTHOR_TESTING},
we can consolidate test files without worrying about
tests timing out on CPAN testers' machines.
- Simplified code in the "best" test files.
Sat Nov 17 2012
- Upgrage tests to use the is() function from Test::More.
Fri Nov 16 2012
- Fixed the code in Build.PL that would set $ENV{AUTHOR_TESTING}.
All tests, even the lengthy ones, are now run when using
"Build test --Testlong".
Tue Nov 13 2012
- Long-running tests now check for $ENV{AUTHOR_TESTING} = 1,
and skip if it doesn't.
Tue Nov 6 2012
- Worked on bitonic() code. Use existing pack/unpack code to
determine power-of-two value, this replaces the
greater_power_of_2_less_than() function.
- Made loop a little more perlish by using the '..' operator.
- Added 'bitonic' to the keyword list.
- Added a get_options parameter in Build.PL. Looking towards
an option to automatically skip long-running tests in
non-development situations.
Tue Oct 30 2012
- Fall-back algorithm for 'best' option is now Batcher's Merge
Exchange algorithm instead of Bose-Nelson.
- Checks for $inputs < 2 in the algorithm functions are pointless
since the calling, exported function already checks for it.
- "use integer" means that int($n/2) may be written more simply
as $n/2.
Sat Oct 27 2012
- Added two new 'best' networks for input sizes 18 and 22,
discovered by Sherenaz Waleed Al-Haj Baddar and submited
by Doug Hoyte.
- Added the bitonic() code and test file as provided by Doug Hoyte.
Thu Oct 25 2012
- New function nw_sort_stats() to return information about
sorting network exchange counts (based on Doug Hoyte's
idea) and other future ideas.
1.24
Sun Oct 14 2012
- Emergency change to svg.t -- I'm doing something wrong in
that now. Dr. Batcher's web site at Kent State has changed slightly,
making a change in the links necessary.
1.09 Sat May 22 2010
- Error in POD snuck in. While I was fixing this, added some more
documentation on group options.
- Added another choice for "grouping" in nw_comparators().
1.08 Mon May 17 2010
- Added an option to nw_comparators() as a result of a communication by
Daniel Stutzbach. Up until now, nw_comparators simply returned the
comparator in the order that the algorithms created them. Daniel
Stutzbach pointed out that these were often not in the best order and
would cause a super-scalar pipeline to stall. He also pointed out that
just reading the list of comparators grouped for graphing removes that
problem (the function that arranges them for graphing, nw_group(), does
in fact "parallelize" the comparators so that they'll look nice on the
graph). So there's now an option to re-group the list. It's not the
default because the default behavior has been there since the beginning
of the module.
See the documentation for nw_comparator() for more information.
- Undid use of mark attributes for SVG graphing. Too many inconsistencies
between different SVG viewers for me to be sure that I'm doing the right
Tue May 23 2006
- Changed arrangement of files to default layout by Module::Build.
- Added the Meta.yml and Build.PL files.
- Changed test files to use Test::Simple.
Fri Jun 2 2006
- Added pod.t.
- Typo fix in pod (itme instead of item). Fixed stale links.
- It looks like the Forbes D. Lewis article, "Sorting Networks"
has vanished altogether. Removed it from the See Also section.
Wed Jul 26 2006
- Split the batcher.t, best.t, bn.t, and hibbard.t files into
two. I'm trying to cut down the time-to-finish length, which
some test environments don't handle well ("Is this test done
yet? I'm bored.")
Wed Sep 13 2006
- Added color components, although no actual colors are set yet
except for 'foreground'.
- Changed the text graph option names 'fromcomp' and 'tocomp'
to 'compbegin' and 'compend' to make them consistant with the
input line names 'inputbegin' and 'inputend'. These names
get adopted by the color option hash.
TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY
YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER
PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE
POSSIBILITY OF SUCH DAMAGES.
END OF TERMS AND CONDITIONS
Appendix: How to Apply These Terms to Your New Programs
If you develop a new program, and you want it to be of the greatest
possible use to humanity, the best way to achieve this is to make it
free software which everyone can redistribute and change under these
terms.
To do so, attach the following notices to the program. It is safest to
attach them to the start of each source file to most effectively convey
the exclusion of warranty; and each file should have at least the
"copyright" line and a pointer to where the full notice is found.
<one line to give the program's name and a brief idea of what it does.>
Copyright (C) 19yy <name of author>
Makefile.PL
LICENSE
MANIFEST
META.json
META.yml
README
lib/Algorithm/Networksort.pm
lib/Algorithm/Networksort/Best.pm
t/00-load.t
t/abecedarian.t
t/best.t
t/fmt.t
t/pod.t
t/svg.t
t/zero_one.pl
eg/algtest.pl
eg/best.pl
eg/bruteforce.pl
eg/eps.pl
eg/fmt00.pl
eg/fmt01.pl
eg/fmt02.pl
eg/fmt03.pl
eg/fmt04.pl
eg/fmt05.pl
eg/svg.pl
eg/text.pl
Run the tests:
Build test
Install the module:
Build install
MORE ON TESTING
With the addition of 'best' networks for sizes 18 and 22, the testing
time went from 'lengthy' to 'intolerable for unsuspecting CPAN testers'.
Consequently, the sorting tests now have an upper limit of 10 for
normal testing. This size goes up to 17 if the environment variable
AUTHOR_TESTING is set (and the size 12 and up 'best' networks are also
tested).
If you want to have the full testing experience, I've provided a switch
that will automatically do all this for you. Run the tests with
Build test --Testlong
and the full suite will run (and depending on your machine, you may have
time to go out and get lunch). If you want to run only a single test file,
then the Module-Build switch '--test_files' can select that file for you:
Build test --test_files=t/best.t --Testlong
Note that the '--Testlong' switch comes last.
COPYRIGHT AND LICENSE
Copyright (C) 2016 John M. Gamble. All rights reserved. This program is
free software; you can redistribute it and/or modify it under the same
terms as Perl itself.
use Algorithm::Networksort ':all';
use Algorithm::Networksort::Best ':all';
use strict;
use warnings;
my $inputs;
my $name;
if (@ARGV == 0)
{
warn "best.pl <input size>\nbest.pl <key name>\n\nPlease give an input size or a key name.";
exit(0);
}
if ($ARGV[0] =~ /^[0-9]+/)
{
$inputs = $ARGV[0];
my(@names) = nw_best_names($inputs);
if (@names == 0)
{
print "No 'best' networks available for size $inputs.\n";
exit(0);
}
print "Available names for size $inputs: ", join(", ", @names), "\n";
exit(0);
}
$name = $ARGV[0] || die "Please use a keyname or a number.";
my $nw = nwsrt_best(name => $name);
print $nw;
exit(0);
my %colorset = (compbegin => undef,
compend => undef,
compline => undef,
inputbegin => undef,
inputend => undef,
inputline => undef,
foreground => undef,
background => undef,
);
my $alg = 'bosenelson';
my($nw, $best);
GetOptions('co_cb=s' => \$colorset{compbegin},
'co_ce=s' => \$colorset{compend},
'co_cl=s' => \$colorset{compline},
'co_ib=s' => \$colorset{inputbegin},
'co_ie=s' => \$colorset{inputend},
'co_il=s'=> \$colorset{inputline},
'co_fg=s' => \$colorset{foreground},
'co_bg=s' => \$colorset{background},
#
'hz_margin=i' => \$graphset{hz_margin},
'hz_sep=i' => \$graphset{hz_sep},
'indent=i' => \$graphset{indent},
'inputradius=i' => \$graphset{inputradius},
'compradius=i' => \$graphset{compradius},
'inputline=i' => \$graphset{inputline},
'compline=i' => \$graphset{compline},
'vt_margin=i' => \$graphset{vt_margin},
'vt_sep=i' => \$graphset{vt_sep},
'algorithm=s' => \$alg,
'best=s' => \$best,
);
my $inputs = $ARGV[0] || 8;
if (defined $best)
{
$nw = nwsrt_best(name => $best);
}
else
{
$nw = nwsrt(inputs => $inputs, algorithm => $alg);
}
print STDERR $nw->title(), "\n";
$nw->colorsettings(%colorset);
$nw->graphsettings(%graphset);
my %colorset = (compbegin => undef,
compend => undef,
compline => undef,
inputbegin => undef,
inputend => undef,
inputline => undef,
foreground => undef,
background => undef,
);
my $alg = 'bosenelson';
my($nw, $best);
GetOptions('co_cb=s' => \$colorset{compbegin},
'co_ce=s' => \$colorset{compend},
'co_cl=s' => \$colorset{compline},
'co_ib=s' => \$colorset{inputbegin},
'co_ie=s' => \$colorset{inputend},
'co_il=s'=> \$colorset{inputline},
'co_fg=s' => \$colorset{foreground},
'co_bg=s' => \$colorset{background},
#
'hz_margin=i' => \$graphset{hz_margin},
'hz_sep=i' => \$graphset{hz_sep},
'indent=i' => \$graphset{indent},
'inputradius=i' => \$graphset{inputradius},
'compradius=i' => \$graphset{compradius},
'inputline=i' => \$graphset{inputline},
'compline=i' => \$graphset{compline},
'vt_margin=i' => \$graphset{vt_margin},
'vt_sep=i' => \$graphset{vt_sep},
'algorithm=s' => \$alg,
'best=s' => \$best,
);
my $inputs = $ARGV[0] || 8;
if (defined $best)
{
$nw = nwsrt_best(name => $best);
}
else
{
$nw = nwsrt(inputs => $inputs, algorithm => $alg);
}
print STDERR $nw->title(), "\n";
$nw->colorsettings(%colorset);
$nw->graphsettings(%graphset);
use warnings;
my %txtset = (compbegin => undef,
compend => undef,
compline => undef,
inputbegin => undef,
inputend => undef,
inputline => undef,
);
my $alg = 'bosenelson';
my($nw, $best);
GetOptions(
'compbegin=s' => \$txtset{compbegin},
'compend=s' => \$txtset{compend},
'compline=s' => \$txtset{compline},
'inputbegin=s' => \$txtset{inputbegin},
'inputend=s' => \$txtset{inputend},
'inputline=s' => \$txtset{inputline},
'algorithm=s' => \$alg,
'best=s' => \$best,
);
my $inputs = $ARGV[0] || 8;
if (defined $best)
{
$nw = nwsrt_best(name => $best);
}
else
{
$nw = nwsrt(inputs => $inputs, algorithm => $alg);
}
#
# Ensure we're only passing in set parameters. And, if it's defined
# (and because it's a pain to do it on the command line), fix the endline.
#
lib/Algorithm/Networksort.pm view on Meta::CPAN
#
# Test our own 5-input network.
#
@cmptr = ([1,2], [0,2], [0,1], [3,4], [0,3], [1,4], [2,4], [1,3], [2,3]);
$nw = Algorithm::Networksort->new(inputs => 5,
algorithm => 'none',
comparators => [@cmptr]);
Internally, this is what L<nwsrt_best()|Algorithm::Networksort::Best/nwsrt_best()>
of L<Algorithm::Networksort::Best> uses.
=back
=item 'comparators'
The list of comparators provided by the user instead of by an algorithm.
=back
lib/Algorithm/Networksort.pm view on Meta::CPAN
=head3 comparators()
The comparators in their 'raw' form, as generated by its algorithm.
For the comparators re-ordered in such a way as to take advantage
of parallelism, see L<network()>.
=head3 network()
Returns the comparators re-ordered from the 'raw' form, providing a
parallelized version of the comparator list; e.g., the best order possible
to prevent stalling in a CPU's pipeline.
This is the form used when printing the sorting network using L<formats()>.
=cut
=head3 algorithm_name()
Return the full text name of the algorithm, given its key name.
lib/Algorithm/Networksort.pm view on Meta::CPAN
Returns a string that creates a Knuth diagram of a network.
$nw = nwsrt(inputs => 4, algorithm => 'bitonic');
$diagram = $nw->graph_svg(); # Using default attributes.
The string will consist of SVG drawing tags enclosed by E<lt>svgE<gt> and E<lt>/svgE<gt> tags.
The attributes of the diagram can be changed via colorsettings() and graphsettings().
$nw = nwsrt_best(name => 'floyd09'); # See Algorithm::Networksort::Best
$nw->colorsettings(compbegin => '#04c', compend => '#00c');
$diagram = $nw->graph_svg();
=begin html
<p>Embedded in a web page, this will produce</p>
<svg xmlns="http://www.w3.org/2000/svg"
xmlns:xlink="http://www.w3.org/1999/xlink" width="278" height="154" viewbox="0 0 278 154">
lib/Algorithm/Networksort/Best.pm view on Meta::CPAN
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 => {
lib/Algorithm/Networksort/Best.pm view on Meta::CPAN
[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
lib/Algorithm/Networksort/Best.pm view on Meta::CPAN
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.
t/abecedarian.t view on Meta::CPAN
#
# "It can be a primer for teaching reading and spelling and more loosely
# any listing in alphabetical order."
# World Wide Words: Abecedarian
# http://www.worldwidewords.org/weirdwords/ww-abe2.htm
#
# Test file created to check the algorithms together. Since we now have a method
# to limit the size of the test once the package is out of the author's hands,
# it's now easier to combine the various tests into one file.
#
# The tests for the 'best' comparator set have their own files since these
# comparators were created by different individuals using different methods.
# It is more sensible to test them individually.
#
# The file may be run by itself with "Build test --test_files=t/abecedarian.t"
#
our $author_testing = $ENV{AUTHOR_TESTING};
our @input_range = $author_testing? (3..17): (3..10);
our @algorithms = nwsrt_algorithms();
plan tests => (scalar @input_range * scalar @algorithms);
use warnings;
use Test::More;
use Algorithm::Networksort;
use Algorithm::Networksort::Best qw(:all);
require "t/zero_one.pl";
my @names;
our $author_testing = $ENV{AUTHOR_TESTING};
@names= sort sizename_cmp nw_best_names();
#
# Spare the CPAN testers from testing networks greater
# than 15 inputs.
#
unless ($author_testing)
{
@names = grep{/^[a-z]+0[0-9]$|^[a-z]+1[0-5]$/} @names;
}
diag("Networks to test: " . join(", ", @names));
plan tests => 1 + scalar @names;
ok(scalar @names > 0, "@names");
for (@names)
{
my $nw = nwsrt_best(name => $_);
my $status = zero_one($nw);
is($status, "pass", "$_, $status, " . $nw->title());
}
sub sizename_cmp
{
my($aname, $asize, $bname, $bsize) = ($a, 999, $b, 999);
if ($a =~ /^([a-z]+)(\d+)$/)
{
( run in 1.085 second using v1.01-cache-2.11-cpan-4e96b696675 )