Re: [FWP] Factorial Elegance

[abigail@foad.org]

On Fri, Sep 15, 2000 at 11:21:11AM -0500, Tim Ayers wrote:
> 
> D'accord. I used the following.
> 
>   #!/usr/bin/perl -w
>   
>   use strict;
>   use Benchmark;
>   
>   use Tie::Math qw(f X);
>   my %factorial = ();
>   tie %factorial, 'Tie::Math', sub { f(X) = X * f(X-1) },
>                                sub { f(0) = 0;  f(1) = 1; };
>   sub schwern {
>     my $x = shift;
>     return $factorial{$x};
>   }
>   
>   sub klement {
>     return eval join '*', 1 .. shift;
>   }
>   
>   my @cache = (1);
>   sub tayers {
>     my $x = shift;
>     @cache = (1);
>     return undef if $x < 0;
>     unless (defined $cache[$x]) {
>       my $p = $cache[$#cache];
>       $cache[$_] = $p *= $_ for ($#cache+1..$x);
>     }
>     return $cache[$x];
>   }
>   
>   timethese(7000,
>    {schwern => '%factorial=();schwern(170);',
>     klement => 'klement(170);',
>     tayers  => '@cache=(1);tayers(170);'
>    });
> 
> I'm probably misunderstanding the TIE-mechanism. Thanks for the help and 

No, you are misunderstanding the way Benchmark works. Since you are  
giving Benchmark a string, the string is evalled. It's evalled in a 
different scope, so, you cannot access the my()ed %factorial; nor the  
my()ed @cache.  But, since sub tayers() resets the cache anyway, the
tayers clause works on a cleared caches, but the schwern one *doesn't*.
Since tayers() resets the cache each time, there isn't much point of
using one, hence the sub abigail() as well, which is the straight forward
approach.

But *don't* make %factorial a package variable and do '%::factorial = ()'.
It'll quickly consume all your memory, and with silly OSses like mine
(Linux) that makes your computer get usuable for a while, till the OS
starts to randomly shoot processes. You need to initialize the cache
to the appropriate values. Furthermore, it's wise to run 'schwern' with
warnings off.

Here's the modified benchmark:

    #!/opt/perl/bin/perl -w

    use strict;
    use Benchmark;

    use Tie::Math qw(f X);
    use vars qw /%factorial/;
    tie %factorial, 'Tie::Math', sub { f(X) = X * f(X-1) },
                                 sub { f(0) = 0;  f(1) = 1; };
    sub schwern {
      local $^W;
      my $x = shift;
      return $factorial{$x};
    }

    sub klement {
      return eval join '*', 1 .. shift;
    }

    my @cache = (1);
    sub tayers {
      my $x = shift;
      @cache = (1);
      return undef if $x < 0;
      unless (defined $cache[$x]) {
        my $p = $cache[$#cache];
        $cache[$_] = $p *= $_ for ($#cache+1..$x);
      }
      return $cache[$x];
    }

    sub abigail {
        my ($r  => $x) = (1, shift);
        do {$r *=  $x} while $x -- > 2;
        $r;
    }


    timethese(-5, 
     {
      schwern => '%::factorial = (0, 1, 1, 1); schwern(170);',
      klement => 'klement(170);',
      tayers  => 'tayers(170);',
      abigail => 'abigail(170);'
     });

    __END__
    Benchmark: running abigail, klement, schwern, tayers, each for at least
    5 CPU seconds...
       abigail:  6 wallclock secs ( 5.31 usr +  0.00 sys =  5.31 CPU)
              @ 2894.54/s (n=15370)
       klement:  6 wallclock secs ( 5.35 usr +  0.00 sys =  5.35 CPU)
              @  182.43/s (n=976)
       schwern:  6 wallclock secs ( 5.06 usr +  0.00 sys =  5.06 CPU)
              @   16.40/s (n=83)
        tayers:  6 wallclock secs ( 5.27 usr +  0.00 sys =  5.27 CPU)
              @ 1513.28/s (n=7975)


As you can see, the 'schwern' solution is way slower than anything else.


Abigail

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe