RE: [FWP] Finding the length of the longest string

[Larry Rosler <lr@hpl.hp.com>]

> From: Andy Jacobs [mailto:andyj@microsoft.com]
> Sent: Wednesday, June 23, 1999 19:00
> To: 'Larry Rosler'; 'fwp@technofile.org'
> Subject: RE: [FWP] Finding the length of the longest string
> 
> This would probably be MUCH slower... but it's kind of 
> compact and fun.
> 
> (sort map {length} @data)[-1];

It would be more fun if it sorted the lengths by their values instead of
lexicographically.  Here's an unusual (but faster!) way of doing that:

  $len = unpack 'n' =>
     (sort map pack('n' => length) => @data)[-1];

I think those fancy commas are so expressive!


#!/usr/local/bin/perl -w
use strict;
use Benchmark;

my @data = map 'x' x $_ => 1 .. 100;

timethese(1 << (shift || 0), {
  Length => \&Length,
  Sort0  => \&Sort0 ,
  Sort1  => \&Sort1 ,
  Xor    => \&Xor   ,
});

sub Length {
    my $len = 0;
    $len < length and $len = length
      for @data;
    $len
}

sub Sort0 {
  (sort { $a <=> $b } map { length } @data)[-1];
}

sub Sort1 {
  unpack 'n' => (sort map pack('n' => length) => @data)[-1];
}

sub Xor {
    my $x = "";
    $x ^= $_ for @data;
    length $x
}
__END__

Benchmark: timing 16384 iterations of Length, Sort0, Sort1, Xor...
    Length: 10 wallclock secs ( 9.34 usr +  0.00 sys =  9.34 CPU)
     Sort0: 27 wallclock secs (27.29 usr +  0.00 sys = 27.29 CPU)
     Sort1: 21 wallclock secs (20.88 usr +  0.00 sys = 20.88 CPU)
       Xor:  8 wallclock secs ( 7.92 usr +  0.00 sys =  7.92 CPU)

Question:  Why is the complicated Sort1 faster than the simple Sort0?

For the definitive answer, see the paper that Uri Gellman and I are
giving at te Perl Conference.
<URL:http://www.hpl.hp.com/personal/Larry_Rosler/sorting.html>

-- 
Larry Rosler
Hewlett-Packard Laboratories
http://www.hpl.hp.com/personal/Larry_Rosler/
lr@hpl.hp.com 

==== Want to unsubscribe from Fun With Perl?
==== Well, if you insist... Send mail with body "unsubscribe" to
==== fwp-request@technofile.org