Algorithm-Networksort
view release on metacpan or search on metacpan
lib/Algorithm/Networksort.pm view on Meta::CPAN
=item 'batcher'
Use Batcher's Merge Exchange algorithm. Merge Exchange is a real sort, in
that in its usual form (for example, as described in Knuth) it can handle
a variety of inputs. But while sorting it always generates an identical set of
comparison pairs per array size, which lends itself to sorting networks.
=item 'bitonic'
Use Batcher's bitonic algorithm. A bitonic sequence is a sequence that
monotonically increases and then monotonically decreases. The bitonic sort
algorithm works by recursively splitting sequences into bitonic sequences
using so-called "half-cleaners". These bitonic sequences are then merged
into a fully sorted sequence. Bitonic sort is a very efficient sort and
is especially suited for implementations that can exploit network
parallelism.
=item 'oddevenmerge'
Use Batcher's Odd-Even Merge algorithm. This sort works in a similar way
to a regular merge sort, except that in the merge phase the sorted halves
are merged by comparing even elements separately from odd elements. This
algorithm creates very efficient networks in both comparators and stages.
=item 'bubble'
Use a naive bubble-sort/insertion-sort algorithm. Since this algorithm
produces more comparison pairs than the other algorithms, it is only
useful for illustrative purposes.
=item 'oddeventrans'
Use a naive odd-even transposition sort. This is a primitive sort closely
related to bubble sort except that it is more parallel. Because other
algorithms are more efficient, this sort is included for illustrative
purposes.
=item 'balanced'
This network is described in the 1983 paper "The Balanced Sorting Network"
by M. Dowd, Y. Perl, M Saks, and L. Rudolph. It is not a particularly
efficient sort but it has some interesting properties due to the fact
that it is constructed as a series of successive identical sub-blocks,
somewhat like with 'oddeventrans'.
=item 'none'
Do not generate a set of comparators. Instead, take the set from an
outside source, using the C<comparators> option.
#
# 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
=cut
sub BUILD
{
my $self = shift;
my $alg = $self->algorithm();
my $inputs = $self->inputs();
my @network;
my @grouped;
#
# Catch errors
#
croak "Input size must be 2 or greater" if ($inputs < 2);
#
# Providing our own-grown network?
#
if ($alg eq 'none')
{
croak "No comparators provided" unless ($self->has_comparators);
$self->length(scalar @{ $self->comparators });
#
# Algorithm::Networksort::Best will set these, so
# only go through with this if this is a user-provided
# sequence of comparators.
#
unless ($self->has_network and $self->depth > 0)
{
@grouped = $self->group();
$self->network($self->comparators);
$self->depth(scalar @grouped);
$self->network([map { @$_ } @grouped]);
$self->title("Unknown $inputs-Inputs Comparator Set") unless ($self->has_title());
}
$self->nwid("nonalgorithmic-" . sprintf("%02d", $inputs)) unless ($self->has_nwid());
return $self;
}
croak "Unknown algorithm '$alg'" unless (exists $algname{$alg});
$self->nwid($alg . sprintf("%02d", $inputs));
@network = bosenelson($inputs) if ($alg eq 'bosenelson');
@network = hibbard($inputs) if ($alg eq 'hibbard');
@network = batcher($inputs) if ($alg eq 'batcher');
@network = bitonic($inputs) if ($alg eq 'bitonic');
@network = bubble($inputs) if ($alg eq 'bubble');
@network = oddeventransposition($inputs) if ($alg eq 'oddeventrans');
@network = balanced($inputs) if ($alg eq 'balanced');
@network = oddevenmerge($inputs) if ($alg eq 'oddevenmerge');
$self->title($algname{$alg} . " for N = " . $inputs) unless ($self->has_title);
$self->length(scalar @network);
$self->comparators(\@network); # The 'raw' list of comparators.
#
# Re-order the comparator list using the parallel grouping for
# the graphs. The resulting parallelism means less stalling
# when used in a pipeline.
#
@grouped = $self->group();
#
###### @grouped
#
$self->depth(scalar @grouped);
$self->network([map { @$_ } @grouped]);
return $self;
}
=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.
=cut
sub algorithm_name
{
my $self = shift;
my $algthm = $_[0] // $self->algorithm();
return $algname{$algthm} if (defined $algthm);
return "";
}
#
# @network = hibbard($inputs);
#
# Return a list of two-element lists that comprise the comparators of a
# sorting network.
#
# Translated from the ALGOL listed in T. N. Hibbard's article, A Simple
# Sorting Algorithm, Journal of the ACM 10:142-50, 1963.
#
# The ALGOL code was overly dependent on gotos. This has been changed.
#
sub hibbard
{
my $inputs = shift;
my @comparators;
my($bit, $xbit, $ybit);
#
# $t = ceiling(log2($inputs - 1)); but we'll
# find it using the length of the bitstring.
#
my $t = length sprintf("%b", $inputs - 1);
my $lastbit = 1 << $t;
#
# $x and $y are the comparator endpoints.
# We begin with values of zero and one.
#
my($x, $y) = (0, 1);
while (1 == 1)
{
#
# Save the comparator pair, and calculate the next
# comparator pair.
#
### hibbard() top of loop:
##### @comparators
lib/Algorithm/Networksort.pm view on Meta::CPAN
$string .= qq( $clrset{compend}\n) .
qq( newpath 2 copy moveto $c_radius 0 360 arc fill\n) .
qq( $clrset{compbegin}\n) .
qq( newpath 2 copy moveto $c_radius 0 360 arc fill\n);
}
}
$string .= qq(} bind def\n\n);
#
# Save the current graphics state, then change the drawing
# coordinates (from (0,0) = lower left to (0,0) = upper left),
# and the color if we're drawing in a single color.
#
$string .= qq(gsave\n0 $ybound translate\n1 -1 scale\n);
$string .= qq($clrset{foreground}\n) if ($monotone);
if (defined $clrset{background})
{
$string .= qq(\ngsave $clrset{background}\n);
$string .= qq(0 0 moveto 0 $ybound lineto $xbound $ybound lineto $xbound 0 lineto closepath);
$string .= qq(\nfill grestore\n);
}
#
# Draw the input lines.
#
$string .= qq(\n%\n% Draw the input lines.\n%\n$grset{inputline} setlinewidth\n) .
qq(0 1 ) . ($inputs-1) . qq( {draw-inputline} for\n);
#
# Draw our comparators.
# Each member of a group of comparators is drawn in the same column.
#
$string .= qq(\n%\n% Draw the comparator lines.\n%\n$grset{compline} setlinewidth\n);
my $hidx = 0;
for my $group (@node_stack)
{
for my $comparator (@$group)
{
$string .= sprintf("%d %d %d draw-comparatorline\n", $hidx, @$comparator);
}
$hidx++;
}
$string .= qq(showpage\ngrestore\n% End of the EPS graph.\n);
return $string;
}
=head3 graph_svg()
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">
<title>9-input Network by Robert W. Floyd</title>
<defs>
<g id="I_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="18" y1="0" x2="260" y2="0" />
<circle style="fill:#000; stroke:#000" cx="18" cy="0" r="2" /> <circle style="fill:#000; stroke:#000" cx="260" cy="0" r="2" />
</g>
<g id="C1_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="14" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="14" r="2" />
</g>
<g id="C3_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="42" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="42" r="2" />
</g>
<g id="C2_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="28" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="28" r="2" />
</g>
<g id="C4_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="56" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="56" r="2" />
</g>
</defs>
<g id="floyd09_454d">
<use xlink:href="#I_454d" y="21" /> <use xlink:href="#I_454d" y="35" />
<use xlink:href="#I_454d" y="49" /> <use xlink:href="#I_454d" y="63" />
<use xlink:href="#I_454d" y="77" /> <use xlink:href="#I_454d" y="91" />
<use xlink:href="#I_454d" y="105" /> <use xlink:href="#I_454d" y="119" />
<use xlink:href="#I_454d" y="133" />
<use xlink:href="#C1_454d" x="27" y="21" /> <use xlink:href="#C1_454d" x="27" y="63" />
<use xlink:href="#C1_454d" x="27" y="105" /> <use xlink:href="#C1_454d" x="41" y="35" />
<use xlink:href="#C1_454d" x="41" y="77" /> <use xlink:href="#C1_454d" x="41" y="119" />
<use xlink:href="#C1_454d" x="55" y="21" /> <use xlink:href="#C1_454d" x="55" y="63" />
<use xlink:href="#C1_454d" x="55" y="105" /> <use xlink:href="#C3_454d" x="69" y="21" />
<use xlink:href="#C3_454d" x="83" y="63" /> <use xlink:href="#C3_454d" x="97" y="21" />
<use xlink:href="#C3_454d" x="111" y="35" /> <use xlink:href="#C3_454d" x="125" y="77" />
<use xlink:href="#C3_454d" x="139" y="35" /> <use xlink:href="#C3_454d" x="153" y="49" />
<use xlink:href="#C3_454d" x="167" y="91" /> <use xlink:href="#C3_454d" x="181" y="49" />
<use xlink:href="#C2_454d" x="195" y="35" /> <use xlink:href="#C2_454d" x="195" y="91" />
<use xlink:href="#C4_454d" x="209" y="49" /> <use xlink:href="#C2_454d" x="223" y="77" />
<use xlink:href="#C2_454d" x="237" y="49" /> <use xlink:href="#C1_454d" x="237" y="91" />
<use xlink:href="#C1_454d" x="251" y="49" />
</g>
</svg>
=end html
( run in 0.715 second using v1.01-cache-2.11-cpan-524268b4103 )