Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

comment on

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

Hi again,

I tried caching using an array and File::Map. All run using one core and are reasonably fast. The main goal here are attempts made at reducing memory consumption.

Update 1: Added PDL example.
Update 2: Improved performance.
Update 3: Added scalar example.

use strict; use warnings; use feature 'say'; use File::Map qw/map_anonymous unmap/; use PDL; # based on the caching demonstration by iM71 # https://stackoverflow.com/a/55361008 # https://stackoverflow.com/questions/38114205/c-collatz-conjecture-op +timization sub collatz_longest_pdl { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp, $n2 ); my $cache = zeros( short(), $size + 1 ); for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + at( $cache, $n ); set( $cache, $current, $tmp ); $length = $tmp, $number = $current if $tmp > $length; } return ( $number, $length ); } sub collatz_longest_array { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp ); my @cache; for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + ( $cache[ $n ] // 0 ); $cache[ $current ] = $tmp; $length = $tmp, $number = $current if $tmp > $length; } return ( $number, $length ); } sub collatz_longest_filemap { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp ); map_anonymous my $cache, $size * 2 + 2, 'shared'; # fill cache with zero's substr($cache, 0, $size * 2 + 2, pack('s', 0) x ( $size + 1 )); for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + unpack('s', substr($cache, $n * 2, 2)); substr($cache, $current * 2, 2, pack('s', $tmp)); $length = $tmp, $number = $current if $tmp > $length; } unmap $cache; return ( $number, $length ); } sub collatz_longest_scalar { my ( $size ) = @_; my ( $length, $number ) = ( 0, 0 ); my ( $n, $steps, $tmp ); # fill cache with zero's my $cache = pack('s', 0) x ( $size + 1 ); for my $current ( 2 .. $size ) { $n = $current, $steps = 0; # count using the T(x) notation $n % 2 ? ( $steps += 2, $n = (3 * $n + 1) >> 1 ) : ( $steps += 1, $n = $n >> 1 ) while $n != 1 && $n >= $current; $tmp = $steps + unpack('s', substr($cache, $n * 2, 2)); substr($cache, $current * 2, 2, pack('s', $tmp)); $length = $tmp, $number = $current if $tmp > $length; } return ( $number, $length ); } #*collatz = \&collatz_longest_pdl; # choose collatz here #*collatz = \&collatz_longest_array; #*collatz = \&collatz_longest_filemap; *collatz = \&collatz_longest_scalar; my ( $number, $length ) = collatz( shift || '1e7' ); say "Longest Collatz (index and value)"; say "$number $length";

Output

1e7 : 8400511 685 1 core collatz_longest 1m16.034s MCE Perl code collatz_longest_pdl 0m13.691s Consumes 39 MiB collatz_longest_filemap 0m06.615s Consumes 59 MiB collatz_longest_scalar 0m06.148s Consumes 39 MiB collatz_longest_array 0m04.986s Consumes 330 MiB collatz_longest_c1 0m01.868s Inline C code collatz_longest_c2 0m00.778s Inline C code

I've been wanting to try File::Map and pleasantly surprised.

Regards, Mario


In reply to Re: Longest Collatz using MCE::Flow, Inline::C, and GCC compiler intrinsics (Caching) by marioroy
in thread Longest Collatz using MCE::Flow, Inline::C, and GCC compiler intrinsics by marioroy

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



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

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

    How do I use this? | Other CB clients
    Other Users?
    Others chanting in the Monastery: (7)
    As of 2020-10-23 22:18 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      My favourite web site is:












      Results (241 votes). Check out past polls.

      Notices?