Algorithm-Networksort-Chooser

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

        $ algorithm-networksort-chooser 9  ## find best sorting network for array size 9
        $ algorithm-networksort-chooser 9 --all  ## show all candiate networks
        $ algorithm-networksort-chooser 9 --algorithms=batcher,bitonic  ## only consider batcher and bitonic algos

        $ algorithm-networksort-chooser 9 --opt=comparators  ## optimise for comparators (default)
        $ algorithm-networksort-chooser 9 --opt=stages  ## optimise for stages
        $ algorithm-networksort-chooser 9 --opt=swaps  ## optimise for average swaps

        $ algorithm-networksort-chooser 9 --median  ## best median network
        $ algorithm-networksort-chooser 9 --selection=4  ## also best median network
        $ algorithm-networksort-chooser 9 --selection=0,1,2  ## top-3 elements selection net

        $ algorithm-networksort-chooser 9 --validate  ## run 0-1 validation test
        $ algorithm-networksort-chooser 9 --show  ## show network as ASCII diagram
        $ algorithm-networksort-chooser 9 --raw  ## show network as raw comparators

DESCRIPTION
    This module uses Algorithm::Networksort to experiment with sorting
    networks.

    Introduction To Sorting Networks
    <http://hoytech.github.io/sorting-networks/>

    By default this script examines the output of all implemented algorithms
    and the currently best known special-cases, and chooses the one that
    best meets your specified criteria.

    This module allows you to trim sorting networks into median or selection
    networks.

    You can then choose the optimal net based on comparators (total number
    of operations) or on stages (number of operations considering
    parallelism).

    Normally the output is something like this:

        $ algorithm-networksort-chooser --median 22
        Network size: 22

README  view on Meta::CPAN

           |  |  |        |  |     |  |  |   
        o--v--|--|--^-----v--|--^--v--|--v--o
              |  |  |        |  |     |      
        o-----v--|--|--------v--v-----|-----o
                 |  |                 |      
        o--------v--v-----------------v-----o

    The "--all" switch shows all networks that were considered.

    Sometimes which algorithm or which best special-case network is
    surprising. For instance, selecting the top-3 elements in a size-9 array
    is best done by adapting Hibbard's algorithm, even though there is a
    special best (by comparators) network for size 9:

        $ algorithm-networksort-chooser 9 --selection=0,1,2 --all
        Network size: 9
        Network type: Selection network: 0,1,2

        Optimisation criteria: comparators

        Optimal network:
          Algorithm "hibbard":
            Comparators: 18
            Stages: 7

bin/algorithm-networksort-chooser  view on Meta::CPAN

use Algorithm::Networksort;
use Getopt::Long;

use Algorithm::Networksort::Chooser;


my @opt_spec = (
  'opt=s',
  'median',
  'selection=s',
  'all',
  'validate',
  'show',
  'raw',
  'algorithms=s',
  'swap-mode=s',
  'help|h|?',
);

my $opt = {

bin/algorithm-networksort-chooser  view on Meta::CPAN

    network => \@network,
  };
}




#### Selection network processing

if ($opt->{median}) {
  die "--selection and --median are incompatible" if defined $opt->{selection};

  $opt->{selection} = int($network_size / 2);
}


if (defined $opt->{selection}) {
  my $selection = [ split(',', $opt->{selection}) ];

  foreach my $ind (@$selection) {
    die "badly formed selection index: $ind" unless $ind =~ /^\d+$/;
    die "selection index $ind is too large for the network size" if $ind >= $network_size;
  }

  foreach my $candidate (@candidates) {
    $candidate->{network} = Algorithm::Networksort::Chooser::build_selection_network($candidate->{network}, $selection);
  }
}




#### Score the generated networks

foreach my $candidate (@candidates) {
  my @network = @{ $candidate->{network} };

bin/algorithm-networksort-chooser  view on Meta::CPAN

  print join(',', map { "[$_->[0],$_->[1]]" } @{ $sorted_candidates[0]->{network} });
  print "]\n";
  exit;
}


print "Network size: $network_size\n";

if ($opt->{median}) {
  print "Network type: Median network\n";
} elsif ($opt->{selection}) {
  print "Network type: Selection network: $opt->{selection}\n";
} else {
  print "Network type: Sorting network\n";
}

print "\n";

print "Optimisation criteria: $opt->{opt}\n";

print "\n";

bin/algorithm-networksort-chooser  view on Meta::CPAN

    $ algorithm-networksort-chooser 9  ## find best sorting network for array size 9
    $ algorithm-networksort-chooser 9 --all  ## show all candiate networks
    $ algorithm-networksort-chooser 9 --algorithms=batcher,bitonic  ## only consider batcher and bitonic algos

    $ algorithm-networksort-chooser 9 --opt=comparators  ## optimise for comparators (default)
    $ algorithm-networksort-chooser 9 --opt=stages  ## optimise for stages
    $ algorithm-networksort-chooser 9 --opt=swaps  ## optimise for average swaps

    $ algorithm-networksort-chooser 9 --median  ## best median network
    $ algorithm-networksort-chooser 9 --selection=4  ## also best median network
    $ algorithm-networksort-chooser 9 --selection=0,1,2  ## top-3 elements selection net

    $ algorithm-networksort-chooser 9 --validate  ## run 0-1 validation test
    $ algorithm-networksort-chooser 9 --show  ## show network as ASCII diagram
    $ algorithm-networksort-chooser 9 --raw  ## show network as raw comparators



=head1 DESCRIPTION

This module uses L<Algorithm::Networksort> to experiment with sorting networks.

L<Introduction To Sorting Networks|http://hoytech.github.io/sorting-networks/>

By default this script examines the output of all implemented algorithms and the currently best known special-cases, and chooses the one that best meets your specified criteria.

This module allows you to trim sorting networks into median or selection networks.

You can then choose the optimal net based on comparators (total number of operations) or on stages (number of operations considering parallelism).

Normally the output is something like this:

    $ algorithm-networksort-chooser --median 22
    Network size: 22
    Network type: Median network

    Optimisation criteria: stages

bin/algorithm-networksort-chooser  view on Meta::CPAN

       |  |  |        |  |     |  |  |   
    o--v--|--|--^-----v--|--^--v--|--v--o
          |  |  |        |  |     |      
    o-----v--|--|--------v--v-----|-----o
             |  |                 |      
    o--------v--v-----------------v-----o


The C<--all> switch shows all networks that were considered.

Sometimes which algorithm or which best special-case network is surprising. For instance, selecting the top-3 elements in a size-9 array is best done by adapting Hibbard's algorithm, even though there is a special best (by comparators) network for si...

    $ algorithm-networksort-chooser 9 --selection=0,1,2 --all
    Network size: 9
    Network type: Selection network: 0,1,2

    Optimisation criteria: comparators

    Optimal network:
      Algorithm "hibbard":
        Comparators: 18
        Stages: 7

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

sub silence_carps {
  local *Algorithm::Networksort::carp = sub {};

  shift->();
}


sub build_selection_network {
  my ($network, $selection) = @_;

  my $pinned = {};
  $pinned->{$_} = 1 foreach (@$selection);

  my @reversed_network = reverse @$network;
  my @reversed_output;

  foreach my $comparator (@reversed_network) {
    if ($pinned->{$comparator->[0]} || $pinned->{$comparator->[1]}) {
      $pinned->{$comparator->[0]} = $pinned->{$comparator->[1]} = 1;

      push @reversed_output, $comparator;
    }