[an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive]
 
[an error occurred while processing this directive] [an error occurred while processing this directive]
Skåne Sjælland Linux User Group - http://www.sslug.dk Home   Subscribe   Mail Archive   Forum   Calendar   Search
MhonArc Date: [Date Prev] [Date Index] [Date Next]   Thread: [Date Prev] [Thread Index] [Date Next]   MhonArc
 

dårlig quicksort i perl



En lille morsom perl-oplevelse, som jeg gerne vil dele med jer.


Et firma havde brug for et mindre perl-script til at behandle nogle post-lister og fik et eksternt firma til at løse opgaven for dem. Fint nok.

Nogle år senere stoppede scriptet med at virke, da inputfilen var
vokset til et par
hundred megabytes og jeg fik opgaven med at finde fejlen og få det løst.

Jeg kunne se at programmet brugte et par gigabytes hukommelse indtil
alt swap var opbrugt.
I koden var der en mystisk SortBy funktion, som det tog lidt tid at dekode.
Det var en forklædt quick-sort implementation, der kaldte sig selv
rekursivt uden at
bruge referencer og kopierede data ved hvert kald !

Ufatteligt at man kan lave en rigtig Quicksort i perl uden at kende
sort eller referencer.

Jeg erstattede flg. de to steder hvor SortBy blev kaldt


sub SortBy { my $type=shift; my $key=shift; my $count=shift; my @sslug@sslug;

[...snap...]

       if($lcount>0) { @lower=SortBy($type,$key,$lcount,@lower); }
       if($ucount>0) { @upper=SortBy($type,$key,$ucount,@upper); }

       my $pos=0;
       for($i=0;$i<$lcount;$i++) { $data[$pos++]=$lower[$i]; }
       for($i=0;$i<$mcount;$i++) { $data[$pos++]=$middle[$i]; }
       for($i=0;$i<$ucount;$i++) { $data[$pos++]=$upper[$i]; }
       return @data;
}

Jeg erstattede flg. de to steder hvor SortBy blev kaldt

med

   @rows=sort{$a->{$curkey}<=>$b->{$curkey}} @rows;
   [...]
   @bundle=sort{ $a->{'key'} <=> $b->{'key'} } @bundle;

og problemet var nu løst.

Når jeg nu sidder at læse koden igen, tænker jeg på om det mon er en
merge-sort istedet for.

/Martin

--
"If atheism is a religion, then not collecting stamps is a hobby."
"We are all atheists about most of the gods that humanity
has ever believed in.  Some of us just go one god further."


 
Home   Subscribe   Mail Archive   Index   Calendar   Search

 
 
Questions about the web-pages to <www_admin>. Last modified 2007-08-01, 02:01 CEST [an error occurred while processing this directive]
This page is maintained by [an error occurred while processing this directive]MHonArc [an error occurred while processing this directive] # [an error occurred while processing this directive] *