Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

I think most (though not all), of your gain is through avoiding the overhead of calling subroutines in loops. Inlining is the last step when trying squeeze out the very last drop of performance. That relates back to my opinion on Perl 5's greatest limitation is...?.

tmoertel's haskell implementation amazes me on the precision!

The precision comes from using Haskell's infinite precision Integer data type (analogous to Math::BigInt) for the product and division calculations, once the cancelling has been carried out.

The performance of that precision comes from the compiled implementation and a highly optimising compiler. The only reason the Perl code manages to beat the compiled Haskell is because it uses the much lower precision, FPU native double representation.

You might find the following code interesting, it's a brute force conversion of Tom's Haskell code staying as close to the original as I could achieve. It works okay for the small dataset, but highlights two major differences between Perl and Haskell.

The highly recusive nature of the algorithm exacerbates the cost of Perl's subcalls and lack of tail recursion.

And if you try to use it on the larger datasets, you'll see that the Perl implementation consumes vast amounts of memory (eventually segfaulting on my machine when it runs out of swap space). Most of the damage is done in building and rebuilding zillions of lists whilst keeping copies of earlier versions on the stack in the merge & cancel functions. It's this type of recursive, divide & copy, list processing that Haskell's ubiquitous lazy operations really excel at.

Not particularly useful given it limitations, but an interesting exercise none the less.

#! perl -slw use strict; $| = 1; package FET; our @EXPORT = 'pCutoff'; use List::Util qw[ sum reduce ]; sub toRatio; sub rpCutoff; sub rdivide; sub fac; sub rtimes; sub cance +l; sub merge; sub pCutoff; sub pCutoff{ toRatio rpCutoff @_ } sub rpCutoff { my @rs = map{ sum @$_ } @_; my @cs = map{ sum @$_ } [ $_[0][0], $_[1][0] ], [ $_[0][1], $_[1][ +1] ]; my $n = sum @rs; my @xs = map{ @$_ } @_; rdivide facproduct( @rs, @cs ), facproduct( $n, @xs ); } sub rproduct{ reduce{ rtimes $a, $b } [[],[]], @_ } sub facproduct{ rproduct map{ fac $_ } @_ } sub fac{ $_[0] < 2 ? [[],[]] : [[ 2 .. $_[0] ], []]; } sub toRatio{ [ bigProduct( $_[0][0] ), bigProduct( $_[0][1] ) ] } sub bigProduct{ reduce{ $a * $b } map{ @$_ } @_ } sub rdivide{ rtimes $_[0], [ $_[1][1], $_[1][0] ] } sub rtimes{ [ cancel merge($_[0][0], $_[1][0]), merge($_[0][1], $_[1][ +1] )] } sub merge; sub merge{ return $_[1] unless defined $_[0] and @{ $_[0] }; return $_[0] unless defined $_[1] and @{ $_[1] }; my( $x, @xs ) = @{ $_[0] }; my( $y, @ys ) = @{ $_[1] }; $x < $y ? [ $x, @{ merge( \@xs, [ $y, @ys ] ) } ] : [ $y, @{ merge( [ $x, @xs ], \@ys ) } ] } sub cancel; sub cancel{ return @_ unless @{ $_[0] } and @{ $_[1] }; my( $x, @xs ) = @{ $_[0] }; my( $y, @ys ) = @{ $_[1] }; return cancel \@xs, \@ys if $x == $y; return do{ my( $xs_, $ys_ ) = cancel \@xs, $_[1]; [$x, @{$xs_}], $ys_ }if $x < $y; return do{ my( $xs_,$ys_ ) = cancel $_[0], \@ys; $xs_, [$y, @{$ys_}] }; } package main; sub Scientific{ sprintf '%.17f', $_[0][0] / $_[0][1] } print Scientific FET::pCutoff [ 5, 0], [1, 4]; #print Scientific FET::pCutoff [ 989, 9400 ], [ 43300, 2400];

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.

In reply to Re^8: Algorithm for cancelling common factors between two lists of multiplicands (192.5 ms) by BrowserUk
in thread Algorithm for cancelling common factors between two lists of multiplicands by BrowserUk

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?

What's my password?
Create A New User
Domain Nodelet?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (5)
As of 2023-09-30 12:30 GMT
Find Nodes?
    Voting Booth?

    No recent polls found