#!/bin/bash

# Compare the performance of perl arrays vs. hash tables
# for inserting and removing a small number of references.
# The order of removal is randomized.
#
# Plotted with gnuplot:
# set title "Per-element time inserting and then removing N elements in Perl"
# set xlabel "N (Number of elements)"
# set ylabel "Clock cycles"
# set terminal png size 800,600
# set output "perlbencharrayvshash.png"
# # 166700 is my processor speed divided by the iteration count below
# plot [] [0:] "array-time" using 1:(166700*($3-$2)/$1) with lines lw 2 title "Array", \
#              "hash-time"  using 1:(166700*($3-$2)/$1) with lines lw 2 title "Hash table"

for n in $( seq 0 30 );do
  overhead=$(
    for trial in {1..3};do
      { time perl -we '
          sub fisher_yates {
           my $i = @_;
           while( $i-- ) {
            my $j = int rand( 1 + $i );
            @_[$i,$j] = @_[$j, $i];
           }
           @_;
          }
          my @things;
          push @things, {} foreach (1..'"$n"');
          foreach(1..10000) {
            @things = fisher_yates @things;
          }'
      } 2>&1 |
        sed -n 's/real[[:space:]]*0m\([0-9.]*\)s/\1/p'
    done | sort -n | head -n1
  )

  {
    echo -n "$n $overhead "
    for trial in {1..5};do
      { time perl -we '
          sub fisher_yates {
           my $i = @_;
           while( $i-- ) {
            my $j = int rand( 1 + $i );
            @_[$i,$j] = @_[$j, $i];
           }
           @_;
          }
          my @things;
          push @things, {} foreach (1..'"$n"');
          my %store;
          foreach(1..10000) {
            foreach my $thing (@things) { $store{$thing} = $thing; }
            @things = fisher_yates @things;
            foreach my $thing (@things) { delete $store{$thing}; }
          }'
      } 2>&1 |
        sed -n 's/real[[:space:]]*0m\([0-9.]*\)s/\1/p'
    done | sort -n | head -n1
  } | tee -a hash-time | tr \\n \\t
    
  {
    echo -n "$n $overhead "
    for trial in {1..5};do
      { time perl -we '
          sub fisher_yates {
           my $i = @_;
           while( $i-- ) {
            my $j = int rand( 1 + $i );
            @_[$i,$j] = @_[$j, $i];
           }
           @_;
          }
          my @things;
          push @things, {} foreach (1..'"$n"');
          my @store;
          foreach(1..10000) {
            foreach my $thing (@things) { push @store, $thing; }
            @things = fisher_yates @things;
            foreach my $thing (@things) {
              foreach $i (0..(scalar(@store)-1)) {
                if ( $store[$i] == $thing ) {
                  splice @store, $i, 1;
                  last;
                }
              }
            }
          }'
      } 2>&1 |
        sed -n 's/real[[:space:]]*0m\([0-9.]*\)s/\1/p'
    done | sort -n | head -n1
  } | tee -a array-time
done