APM: Sparse arrays -- performance analysis

Brian Michalk michalk at awpi.com
Thu Jul 10 11:53:01 CDT 2003


I ran a single trace through the filtering algorithm.
Old method: 24 seconds
New method: 30 seconds  This uses a hash, but I have to sort the keys.

I'll try out the idea of using another array to hold the indices.


The old method of trying a datum, then counting the percent above the datum:
    121       my %beenhere;
    122       while (($pcnt_above > ($contact_area+.005)) ||
    123            ($pcnt_above < ($contact_area-.005))
    124           ) {
    125         $numloops++;
    126         $total_above = 0;
    127
    128         foreach (@stack) {if (($_-$avg) > $offset )
{$total_above++;}}
    129         $pcnt_above = $total_above / $win;
    130
    131         if ($pcnt_above >= $contact_area ) { $offset++;}
    132         if ($pcnt_above <  $contact_area ) { $offset--;}
    133         if (defined $beenhere{$offset}) {
    134             $pcnt_above = $contact_area;
    135         }
    136         $beenhere{$offset} = 1;
    137       }

The new method using a hash to represent a histogram:

    126       my $bincount=0;
    127       foreach $index (sort {$b <=> $a} keys %hist) {
    128         $bincount += $hist{$index};
    129         $offset = $index;
    130         last if (($bincount/$win)>$contact_area);
    131       }




More information about the Austin mailing list