[tpm] OID sorting

[Fulko Hew]

Thanks all for your ideas.

I've coalesced the various suggestions (excluding Uri's comments so far)
and present for your amusement, the following results based on my
'real-world' dataset of 24,528 OID strings.

                      s/iter
abram_whilecmp          7.30       --
indy_slow_sort          7.11       3%
indy_fast_sort          6.53      12%
henrys_sort             5.06      44%
fulko_sort_optimized    1.77     314%
fulko_sort_orig         1.72     323%
abram_swartzpacksort    1.60     357%
abram_packsort          1.48     392%
abram_nounpacksort      0.96     660%


Note: I had to alter Indy's 'slow' compare because %3d is not large
enough for real data.  The numbers can range from 0 to 4 Gig.
This also means that Indy's fast compare won't work either.

As it turns out, my original code doesn't appear to be all that
bad after all.  But as I went through and thought I was optimizing
it with maps and stuff, it actually gets worse.

Both my original code, and my optimized version is provided below for
peer review.  In the mean time, I may just investigate the 'nounpacksort'
version.

sub fulko_sort_orig {
    my @oids = @_;

    my ($i, @r1, $temp);
    my $len = scalar(@oids);
    for ($i = 0; $i < $len; $i++) {
        $temp = '';
        @r1 = split(/\./, $oids[$i]);
        foreach (@r1) { $temp .= sprintf ("%8d.", $_); }
        chop($temp);
        $oids[$i] = $temp;
    }
    @oids = sort @oids;
    for ($i = 0; $i < $len; $i++) {
        $oids[$i] =~ s/ //g;
    }
    @oids;
}

sub fulko_sort_optimized {
    my @oids = sort
                map { join ".",
                    map { sprintf ("%8d", $_); } split /\./;
                } @_;

    for (my $i = 0; $i < scalar(@oids); $i++) {
        $oids[$i] =~ s/ //g;
    }
    @oids;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/toronto-pm/attachments/20090502/a3f23cb5/attachment.html>