Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Meditations

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

If you've discovered something amazing about Perl that you just need to share with everyone, this is the right place.

This section is also used for non-question discussions about Perl, and for any discussions that are not specifically programming related. For example, if you want to share or discuss opinions on hacker culture, the job market, or Perl 6 development, this is the place. (Note, however, that discussions about the PerlMonks web site belong in PerlMonks Discussion.)

Meditations is sometimes used as a sounding-board — a place to post initial drafts of perl tutorials, code modules, book reviews, articles, quizzes, etc. — so that the author can benefit from the collective insight of the monks before publishing the finished item to its proper place (be it Tutorials, Cool Uses for Perl, Reviews, or whatever). If you do this, it is generally considered appropriate to prefix your node title with "RFC:" (for "request for comments").

User Meditations
For magnificent glory, a TT Replacement.
6 direct replies — Read more / Contribute
by EvanCarroll
on May 20, 2014 at 14:23
    TT is pretty old and dated, so I've endeavored to implement Jade in Perl. Jade is a modern markup that is quickly becoming somewhat of a standard for Node.js. Here is what Jade looks like, (and all of this currently works in my port).
    doctype html
    html(lang="en")
      head
        title= pageTitle
        script(type='text/javascript').
          if (foo) {
             bar(1 + 5)
          }
      body
        h1 Jade - node template engine
        #container.col
          if youAreUsingJade
            p You are amazing
          else
            p Get on it!
          p.
            Jade is a terse and simple
            templating language with a
            strong focus on performance
            and powerful features.
    
    You can read more about it on jade-lang.com/ There are a lot of key features to it. The big thing is, of course, not having to manage closing tags with whitespace sensitivity. This may be very un-Perlesque. But all good Perl users should join the rest of the rest of world in passionately hating sgml/xml. I've got very few tests on it currently, and most importantly it does not set out to recreate a DOM. It's a basic Jade recursive decent parser that supports interpolated (Blocks) and compiled (includes). The only things not yet implemented are in the POD. I plan on getting to them in the future.


    Evan Carroll
    The most respected person in the whole perl community.
    www.evancarroll.com
The 10**21 Problem (Part 4)
6 direct replies — Read more / Contribute
by eyepopslikeamosquito
on May 19, 2014 at 07:48

    In part three of this seemingly never-ending series on high performance computing we continued what may become the longest whittle in Perl Monks history by further reducing the running time of our magic formula search program, from 728 years down to just 286.

    The latest round of improvements were achieved not by a major breakthrough, rather by applying a succession of micro-optimizations. To achieve the required massive speed boost, it was becoming increasingly clear that we needed to find a new breakthrough idea.

    Constraint Satisfaction Problems

    Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time.

    -- Constraint satisfaction problem (wikipedia)

    So, while the talk of this being a “10**21 problem” is an interesting one, and the latest installment (#3) about whacking the TLB of the processor is even more so, it seems like an incredible amount of work to unleash on a problem that has a trivial algorithmic solution ... This is on the one hand very interesting and computer-sciency, as I have already said, but the choice of example-problem puzzles me.

    -- sundialsvc4

    Roman numerals were the challenge at hand. The method of the example is common to constraint searches beyond the example. Constraint searches exist in drug research and many other fields ... Pick any field which has a large search space for just the right combination of properties in an as yet undiscovered item. Write a program which tries and makes a preliminary fitness determination for each possibility. Have that program spit out a short list of candidates for further investment of testing and development ... In this specific case, the fitness is a maximum length, a handful of inputs, and a handful of outputs that map correctly to those inputs ... The point of an example is that it is a concrete thing that is completed and shown rather than an abstract idea.

    -- mr_mischief beautifully explains the point to sundialsvc4

    mr_mischief was right on the money, sundialsvc4 on the wrong track.

    This was indeed a classic constraint satisfaction problem ... which I felt woefully ill-equipped to solve. Lacking the mathematical ability of an ambrus, the only strategy I could think of was to desperately search for a hack, any hack, that would allow me to abandon a potential solution as early as possible, as soon I was certain it could not be successfully completed.

    In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem, especially with incomplete or imperfect information or limited computation capacity.

    -- Metaheuristic (wikipedia)

    Ahem. Instead of "hack" above, please feel free to substitute "metaheuristic" -- a new word I learnt while researching this series.

    An "early abandonment hack", erm metaheuristic, would clearly be much faster than a brute force complete enumeration of all candidate solutions. How to find such a hack?

    Know Your Data

    To get a feel for what the data in the 4GB lookup tables actually looked like, I wrote some small Perl programs similar to the one below, which displays the data in 128-byte blocks:

    use strict; use warnings; use List::MoreUtils qw(natatime); # See [id://861938] sub chunk_array { my ( $n, @vals ) = @_; my $str; my $iter = natatime( $n, @vals ); while ( my @line = $iter->() ) { $str .= join( " ", @line ) . "\n"; } return $str; } sub dump_blocks { my $file = shift; # bytemap file to read my $nblock = shift; # number of blocks to dump local $/ = \128; # Make <> operator read 128 bytes open( my $fh, '<', $file ) or die "error: open '$file': $!"; binmode($fh); for my $n ( 1 .. $nblock ) { my $block = <$fh>; length($block) == 128 or die "oops"; print "block $n:\n"; print chunk_array( 16, map { sprintf "%3d", ord } split //, $b +lock ); } close($fh); } # A 4GB bytemap consists of four 1GB physical files (suffix: "-0" .. " +-3"). # (See [id://1086481] for a program that generates a bytemap). my $bytemap_root = "lookzpM.byte"; my $fname = $bytemap_root . "-0"; dump_blocks( $fname, 16 );
    which produced:
    block 1: 0 118 0 126 0 126 0 102 0 102 0 94 0 94 0 86 0 86 0 94 0 94 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 75 55 51 55 59 63 35 47 43 39 35 39 27 31 19 15 11 23 19 23 27 31 block 3: 0 111 0 103 0 103 0 127 0 79 0 119 0 119 0 127 0 111 0 103 0 103 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 4: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 114 0 122 0 114 0 106 0 98 0 90 0 66 0 74 0 82 0 90 0 82 44 42 40 34 36 58 56 2 12 0 8 50 52 58 56 50 44 42 40 34 36 block 5: 0 88 0 76 0 72 0 84 0 88 0 108 0 104 0 100 0 120 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 6: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 109 0 97 0 101 0 65 0 77 0 113 0 117 0 113 0 109 0 97 0 101 5 1 1 0 0 17 17 21 21 17 17 45 45 33 33 37 0 65 0 77 0 block 7: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 8: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 68 0 72 0 76 0 88 0 84 0 104 0 108 0 24 26 4 2 8 0 12 0 120 0 116 0 104 0 108 0 120 0 68 0 72 0 76 0 88 0 84 0 block 9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 10: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 83 0 91 0 67 0 75 0 67 63 59 55 51 55 43 47 51 63 59 7 3 7 11 15 3 31 27 23 19 23 0 111 0 95 0 71 0 71 0 79 0 127 0 119 0 119 0 111 0 127 0 block 11: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 12: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 124 0 112 0 116 0 112 0 124 0 64 0 68 0 64 0 92 0 80 0 84 22 16 30 28 30 0 6 4 6 0 62 60 62 48 54 52 54 48 62 60 62 0 70 0 70 0 94 0 94 0 86 0 0 0 0 0 0 0 0 0 0 0 block 13: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 14: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 85 0 89 0 93 0 73 0 69 0 121 0 125 0 105 0 117 0 121 0 125 1 9 5 5 1 25 29 29 17 105 0 85 0 89 0 93 0 73 0 69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 15: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 block 16: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 78 0 70 0 70 0 94 44 46 40 22 20 22 24 30 12 14 8 6 4 6 0 126 0 110 0 118 0 118 0 126 0 78 0 70 0 70 0 94 0 110 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    Hmmm, every one of these blocks looks like it is one of just three distinct types:
    • All zeros
    • All non-zero numbers even
    • All non-zero numbers odd
    Every one of those blocks is one of just three distinct types! Every one of those blocks is one of just three distinct types?!! Whoa. But does that hold true everywhere? To find out, I nervously ran a brute force search over all seven 4GB lookup tables and was elated to learn that this "theorem" does indeed hold true for every single block of every single lookup table!

    Only odd modulos (i.e. 1001, 1003, 1005, ...) can produce a valid solution

    -- ambrus' third theorem

    For modulo 1001, each and every 128-byte block in all seven 4GB lookup tables contains either all zeros, all non-zero numbers even, or all non-zero numbers odd

    -- ambrus' fourth theorem

    Once again I could not restrain myself from adding to our list of the theorems of ambrus. :-) I expect ambrus' third theorem is easy to prove, his fourth much harder.

    Curiously, out of all odd modulos in the range 1001..1221, the fourth theorem of ambrus applies to modulos 1001 and 1221 only. Why only those two? Who decides? Weird. Maybe ambrus can show mathematically why it must be so. I "proved" it only via brute force enumeration of hundreds of 4GB lookup tables.

    For modulo 1003..1219 you would need to find a different heuristic to trim the search space (if one exists). That is the main reason why I used modulo 1001 only.

    As you might have guessed, noticing this oddity in the lookup table data was a key breakthrough. Why?

    • All zero blocks can be skipped immediately. 125 searches eliminated.
    • To get a hit, all blocks must be even or all blocks must be odd (a value from an odd block can never match one from an even block).
    • We can encode each 128 byte block in just two bits: one to indicate zero or non-zero, the other to indicate odd or even. This reduces the lookup table size from 4GB down to just 8MB! This is crucial in reducing CPU cache misses.

    Wait, there's more. Each of MDCLXVI can produce a valid solution only if all their lookup table blocks are of the same (non-zero) type. Assuming an equal number of blocks of each type, that occurs with a probability of (2/3) (first block non-zero) times (1/3)**6 (next six blocks match first non-zero block). After a preliminary check of all seven bitmaps therefore, only one in 1093.5 candidate solutions needs further (more expensive) checking for an exact match -- via a 4GB table lookup plus calculation, as detailed in earlier episodes of this series.

    Bitmaps

    Here is the code (64-bit compile, 32-bit int, 64-bit size_t) to create a 8MB bitmap from a 4GB lookup table:

    #define LAST_CHUNK_IDX_4MB 33554431 #define LAST_CHUNK_IDX_8MB (33554432*2 - 1) #define BIT_MAP_SIZE_BYTES ((LAST_CHUNK_IDX_8MB+1) >> 3) typedef unsigned char bytev_t; void make_bitmapA( const char* bitfname, // in: bit map file name const bytev_t* bytevec, // in: byte vector unsigned char* bitvec // out: bitvec put here (assumed already z +eroed) ) { unsigned int uu; unsigned int uu2; unsigned int byte; unsigned int bit; const size_t* psz; const bytev_t* psy; int j; unsigned int neven; unsigned int nodd; unsigned int totzero = 0; unsigned int toteven = 0; unsigned int totodd = 0; for (uu = 0; uu <= LAST_CHUNK_IDX_4MB; ++uu) { psy = &bytevec[uu << 7]; psz = (size_t*)psy; // This is the zero case. if (psz[0] == 0 && psz[1] == 0 && psz[2] == 0 && psz[3] == 0 && psz[4] == 0 && psz[5] == 0 && psz[6] == 0 && psz[7] == 0 && psz[8] == 0 && psz[9] == 0 && psz[10] == 0 && psz[11] == 0 && psz[12] == 0 && psz[13] == 0 && psz[14] == 0 && psz[15] == 0) { // zero: both bits are zero, nothing to do ++totzero; continue; } // All non-zero elements in block will be all even or all odd! neven = 0; nodd = 0; for (j = 0; j < 128; ++j) { if (psy[j] != 0) { if (psy[j] % 2 == 0) { ++neven; } else { ++nodd; } } } if (neven > 0 && nodd > 0) { fprintf(stderr, "oops 1\n"); exit +(1); } if (neven == 0 && nodd == 0) { fprintf(stderr, "oops 2\n"); exit +(1); } uu2 = uu * 2; // nonzero: set first bit byte = uu2 >> 3; bit = uu2 & 7; bitvec[byte] |= (1 << (bit+1)); if (neven > 0) { // even: second bit is zero, nothing to do ++toteven; continue; } // odd: set second bit ++totodd; bitvec[byte] |= (1 << bit); } printf("zero=%u even=%u odd=%u from %u (%u)\n", totzero, toteven, t +otodd, LAST_CHUNK_IDX_4MB+1, uu); FILE* fh; printf("write %s\n", bitfname); fh = fopen(bitfname, "wb"); if (fh == NULL) { fprintf(stderr, "oops open '%s' failed: errno=%d\n", bitfname, e +rrno); exit(1); } if (fwrite(bitvec, BIT_MAP_SIZE_BYTES, 1, fh) != 1) { fprintf(stderr, "oops write '%s' failed: errno=%d\n", bitfname, +errno); exit(1); } fclose(fh); }

Object Oriented Perl - very basic guide
9 direct replies — Read more / Contribute
by Preceptor
on May 15, 2014 at 10:10

    I've been doing Perl for a while now, and one of the things I've meant to get to grips with, is 'object oriented' Perl. I think I'm getting there now, so I'm writing up what I've got so far in the hopes that it'll be a helpful reference.

    First, the basics - object oriented languages encapsulate code into 'objects'. The object has an internal state, and it's own 'code' for handling that state.

    The reason that's useful, is because if I write a module for you to use - then all you need to know is how to run the internal code, and don't have to worry about what goes on inside.

    That's why it's widely used in modules on CPAN, and chances are pretty good that you've already used it if you've used any CPAN modules.

    The way perl 'does' objects, is that it treats each object as a hash. The 'attributes' or 'internal state' are hash keys.

    As a start point (save as 'MyObject.pm')

    #!/usr/bin/perl use strict; use warnings; package MyObject; sub new { print "method 'new' called with parameters: ", join ("\n", @_ ), "\n +"; my ( $class, @args ) = @_; my $self = {}; $self -> {state} = "newly created"; bless $self, $class; return $self; } sub set_state { my ( $self, $new_state ) = @_; $self -> {state} = $new_state; } sub get_state { my ( $self ) = @_; return $self -> {state}; }

    You can then 'drive' this module with:

    # use_oo.pl #!/usr/bin/perl use strict; use warnings; use MyObject my $object_instance = MyObject -> new(); print "Object is: ", $object_instance,"\n"; $object_instance -> set_state ( "here is a new state" ); print "Object state: ", $object_instance -> get_state(),"\n";

    It's fairly simple, but what it means is that I can 'build in' all sorts of code and state variables into 'MyObject' - for example, validating when you 'set state' to ensure that it's not forcing something odd to happen. But this can happen transparently, and your code snippet doesn't actually need to worry about it.

    What you may not have seen before is the 'bless' keyword - when you create '$self' then you create a hash reference - which you could (and essentially, do) treat it as any other hash reference. What 'bless' does is 'mark' the reference as a specific type of object. So you'll see when you print '$object_instance' that it looks something like:

    MyObject=HASH(x012345)

    That's key, because it lets perl identify where it should look when you use a method - e.g. 'get_state' - it knows to look inside the 'MyObject' module explicitly.

    $object_instance -> set_state ( "here is a new state" );

    is translated by perl (because it knows it's a 'MyObject' because of that 'bless') into:

    MyObject::set_state ( $object_instance, "here is a new state" );

    (Passing $object_instance is necessary, because that has it's own internal state, and we need to know which internal state to modify).

    I wouldn't say it's something I'll always use as a technique, but it's a useful extra tool - if I've got a set of scripts that all do similar and related things, then there may well be value in creating a module for them to all use... and if you do, it's certainly worth considering using an object oriented module instead.

At the risk of saying something stupid-but-obvious about Roman Numerals
4 direct replies — Read more / Contribute
by sundialsvc4
on May 12, 2014 at 08:34

    Like everyone else, I have been reading the “10**21” threads with some academic interest – but also, I confess, some confusion when talk is made of “4 gigabyte lookup-tables.”   If the poor Romans actually had to do that, they’d never have been able to count anything.   An algorithm for converting Roman numerals to decimal is trivially easy:   just reverse the string (say ...) so that you intepret it from right-to-left instead of left-to-right.

    use strict; use warnings; my %letters = ('I' => 1, 'V' => 5, 'X' => 10, 'L' => 50, 'C' => 100, 'D' => 500, 'M' => 1000); my $roman = "MCCMLXXIV"; #1874 my $result = 0; my $high_score = 0; foreach my $letter ( split(//, reverse($roman)) ) { my $score = $letters{$letter}; if ($score >= $high_score) { $result += $score; } else { $result -= $score; } $high_score = $score if $score > $high_score; } print "$result\n";

    When the string is viewed from left-to-right, parsing seems difficult because in a well-formed Roman string like MCCMLXXIV you don’t know what C means until you encounter M.   However, that’s not the way the Romans did it.   They probably also read the string from right-to-left, as was and is the standard for many human languages of the region.   Now, the rule is one that any human could do in his head:   “if the digit is as big or bigger than the biggest one you have seen so-far, reading from right to left, add it to the total; otherwise, subtract.”   They did not use arbitrary combinations of letters, although the algorithm shown above would accept them.   (As an example, I doubt that they actually used IM to represent 999.)   In fact, the rules that they did use make the process similar to “making change” given various denominations of currency, and this can’t be accidental.

    So, while the talk of this being a “10**21 problem” is an interesting one, and the latest installment (#3) about whacking the TLB of the processor is even more so, it seems like an incredible amount of work to unleash on a problem that has a trivial algorithmic solution.   I am certainly not “dissing” that thread for its informative discussion of how to deal with problems that would require massive search, but Roman Numerals does not seem to be a good example to use here, unless I am entirely missing the point.   (Which possibility I do not deny.)   The proper solution for Roman Numerals would be to “find a better algorithm,” then optimize-the-hell out of that algorithm.   I cannot imagine that any solution would be faster, especially when the time required to populate those gigabytes of data is included, but I say this only because a nearly cost-free algorithm to solve this problem readily exists, as just shown.   For problems that lack such alternatives, the issues discussed in that thread are of course hugely relevant, and the solutions, very informative.

    - - - - -

    For the “true die-hard golfers” among us, the same algorithm can be expressed, even without any conditional branches at all other than for the scan-loop, as a finite-state machine (FSM) with twenty-six-element tables containing numbers that are either positive or negative depending on the table.   The machine’s state would, of course, represent the largest digit, if any, yet seen when scanning from right to left.   For instance, in the table for state LARGEST_SEEN_IS_V (i.e. all tables except LARGEST_SEEN_IS_I and INITIAL_STATE), the entry for I would now be (-1).   A “real” Perl implementation would use a C-language subroutine.   If an ERROR_STATE is provided, such an algorithm could also detect and reject “syntax error” inputs (as the algorithm shown above cannot do).   Which is exactly why we build language-parsers and lexical-scanners this way . . .

    - - - - -

    Clearly, the intent of the main thread must be to present efficient solutions to problems that actually do consist of arbitrary-string inputs, for which all possible strings are equally probable, under conditions where arbitrarily-large amounts of physical RAM are presumed to be available.   Problems that, unlike Roman Numerals, do not present a trivial algorithmic solution.   Problems for which an efficient solution in the Perl language (or at least, the Perl environment) is required.

    - - - - -

    (Postscript:   I recently helped with a geocaching-like team building challenge for highly-paid “alpha-male” executives, in which you had to use a GPS to find nearby things in an unfamiliar town and obtain clues.   One of the things we took them to was a statue which had a date written in Roman Numerals.   They just needed to get that date.   No big deal, any third-grader could do that, right?   Uh uh.   I was speechless to watch several(!) of them busily searching-for and downloading a “Roman Numerals app” to let them decipher the clue ... which they had utterly no idea how to do on their own.   They could not read Roman Numerals!   So they sat there, locating and downloading – in a couple of cases, buying – an app for their cell-phones.   “Oy vey!”)

The 10**21 Problem (Part 3)
2 direct replies — Read more / Contribute
by eyepopslikeamosquito
on May 11, 2014 at 09:04

    To recap, in parts one and two we reduced the estimated running time of a magic formula search program from 52,887,477 years down to just 728 years. Though that was gratifying, I really didn't want to wait that long. I was happy to wait a year or two, but no more. So I had to find a way to somehow make the search program run a hundred times faster.

    That's not a minor disadvantage, we're talking about things being 50 to 100 times slower with a linked list. Compactness matters. Vectors are more compact than lists. And predictable usage patterns matter enormously. With a vector, you have to shove a lot of elements over, but caches are really really good at that.

    When you traverse lists you keep doing random access ... so you are actually random accessing your memory and you are maximizing your cache misses, which is exactly the opposite of what you want.

    -- Bjarne Stroustrup: Why you should avoid Linked Lists (3:30-5:00) (from GoingNative 2012 Keynote)

    At the end of Part 2, you may recall that we had become stalled by a nasty "cache miss" performance problem, similar to the one Stroustrup describes above. By following Stroustrup's advice to "stay compact, stay predictable" -- and without changing the essential algorithm -- I was able to eventually achieve the massive speed up required.

    Sometimes you think a code change "should" improve performance yet it does not. Each specific code "performance improvement" therefore has to be benchmarked separately, accepted if it improves performance, backed out if not. Painstaking work. One step at a time ... one insight leads to another ... just like playing code golf. :-)

    Lookup Table vs Calculation

    In Part 1 we noticed, when playing golf, there is often a battle between a lookup table and a magic formula. Curiously, when searching for a code golf magic formula, there is often a similar battle, this time between a lookup table and a calculation: for example, to eliminate the inner loop, ambrus used a calculation; I used a lookup table.

    When searching for our magic formula, lookup table wins for the first Roman Numeral value, it's a tie for the second value, and calculation wins for all subsequent values. Why?

    Well, from Part 2, the code to calculate the first Roman Numeral value (D):

    d8 = (d7 ^ q8) * H_PRIME ^ HASH_LEN; d9 = d8 & ~127; d9 %= 1001; if (d9 < 0) d9 += 1001; if (d9 < 500 - 127) continue; if (d9 > 500 + 127) continue; dist = d9 < 500 ? 500 - d9 : d9 - 500; q9 = (d8 & 127) ^ dist; if (q9 == 0 || q9 == 10 || q9 == 13) continue;
    is significantly more work than the code to calculate the second and subsequent values namely:
    c9 = (c7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; c9 %= 1001; if (c9 < 0) c9 += 1001; if (c9 != 100) continue;
    Apart from being more work, the first value always needs to be calculated, while the second value only need be calculated about 255 times per 1001 (i.e. when d9 above is in the range 373..627). Since the second value matches only once per 1001 (i.e. when c9 above is precisely 100), the third value only need be calculated with a probability of (255/1001) * (1/1001), the fourth value (255/1001) * (1/1001) * (1/1001), ... and so on. Testing showed that hitting the third and subsequent values (i.e. L, X, M) is a sufficiently rare event that, with current commodity hardware, it is not worth cluttering all the memory caches with their 4GB lookup tables.

    Of course, whether lookup table is faster than calculation depends on CPU versus memory speed. And main memory speed can be improved by spending a lot of money. At one stage, I was considering boosting memory performance by buying expensive high speed memory and overclocking my PC.

    By the way, a nice bonus from reducing five 4GB lookup tables down to just one is that the program's total memory requirement is now much lower, allowing us to run it in certain massively parallel environments, such as Xeon Phi for example (which currently has a 6GB limit per core).

    Here is the inner loop code revised to use just one 4GB lookup table:

    #define H_PRIME 1000003 #define HASH_LEN 11 // my_m128_t mimics Intel __m128i type typedef struct my_m128_t my_m128_t; struct my_m128_t { short m128i_i16[8]; }; int inner( const unsigned char* bytevecM, int startval, int endval, int m2, int d2, int c2, int l2, int x2, my_m128_t* ps) { int m3, m4, m5, m6, m7; int d3, d4, d5, d6, d7, d9; int c3, c4, c5, c6, c7, c9; int l3, l4, l5, l6, l7, l9; int x3, x4, x5, x6, x7, x9; int q3, q4, q5, q6, q7, q8, q9; int iret = 0; for (q3 = startval; q3 < endval; ++q3) { if (q3 == 10 || q3 == 13) continue; m3 = (m2 ^ q3) * H_PRIME; d3 = (d2 ^ q3) * H_PRIME; c3 = (c2 ^ q3) * H_PRIME; l3 = (l2 ^ q3) * H_PRIME; x3 = (x2 ^ q3) * H_PRIME; for (q4 = 1; q4 < 128; ++q4) { if (q4 == 10 || q4 == 13) continue; m4 = (m3 ^ q4) * H_PRIME; d4 = (d3 ^ q4) * H_PRIME; c4 = (c3 ^ q4) * H_PRIME; l4 = (l3 ^ q4) * H_PRIME; x4 = (x3 ^ q4) * H_PRIME; for (q5 = 1; q5 < 128; ++q5) { if (q5 == 10 || q5 == 13) continue; m5 = (m4 ^ q5) * H_PRIME; d5 = (d4 ^ q5) * H_PRIME; c5 = (c4 ^ q5) * H_PRIME; l5 = (l4 ^ q5) * H_PRIME; x5 = (x4 ^ q5) * H_PRIME; for (q6 = 1; q6 < 128; ++q6) { if (q6 == 10 || q6 == 13) continue; m6 = (m5 ^ q6) * H_PRIME; d6 = (d5 ^ q6) * H_PRIME; c6 = (c5 ^ q6) * H_PRIME; l6 = (l5 ^ q6) * H_PRIME; x6 = (x5 ^ q6) * H_PRIME; for (q7 = 1; q7 < 128; ++q7) { if (q7 == 10 || q7 == 13) continue; m7 = (m6 ^ q7) * H_PRIME; d7 = (d6 ^ q7) * H_PRIME; c7 = (c6 ^ q7) * H_PRIME; l7 = (l6 ^ q7) * H_PRIME; x7 = (x6 ^ q7) * H_PRIME; for (q8 = 1; q8 < 128; ++q8) { if (q8 == 10 || q8 == 13) continue; q9 = bytevecM[(unsigned int)(m7 ^ q8)]; if (q9 == 0) continue; d9 = (d7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; d9 %= 1001; if (d9 < 0) d9 += 1001; if (d9 != 500) continue; c9 = (c7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; c9 %= 1001; if (c9 < 0) c9 += 1001; if (c9 != 100) continue; l9 = (l7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; l9 %= 1001; if (l9 < 0) l9 += 1001; if (l9 != 50) continue; x9 = (x7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; x9 %= 1001; if (x9 < 0) x9 += 1001; if (x9 != 10) continue; ps[iret].m128i_i16[0] = q3; ps[iret].m128i_i16[1] = q4; ps[iret].m128i_i16[2] = q5; ps[iret].m128i_i16[3] = q6; ps[iret].m128i_i16[4] = q7; ps[iret].m128i_i16[5] = q8; ps[iret].m128i_i16[6] = q9; ++iret; } } } } } } return iret; }
    As you can see, we simply combined the "first theorem of ambrus" code and the "first hack of eyepopslikeamosquito" code from Part 2.

    Doing this reduced the running time from 95 to 74 seconds = 74 * 125**4 / 60 / 60 / 24 / 365 = 572 years.

    Prefetching

    In emerging and future high-end processor systems, tolerating increasing cache miss latency and properly managing memory bandwidth will be critical to achieving high performance. Prefetching, in both hardware and software, is among our most important available techniques for doing so.

    -- When Prefetching Works, When it Doesn't, and Why (pdf)

    What more can be done to speed up our (newly single) 4GB lookup table? Well, before we enter the inner loop, we already know the limited range of values required from the bytevecM lookup table. In fact, just as in ambrus's first theorem, there are only 128 values, and they are all right next to each other in memory. To reduce memory latency, can we somehow tell the computer to start the tortuous load sequence of those 128 bytes from main memory before we enter the inner loop? Yes! The MSVC _mm_prefetch compiler instrinsic, which under the covers generates the x86 SSE SIMD prefetcht0 instruction, does just that. That is, adding the following code immmediately before the q8 loop above:

    _mm_prefetch(&bytevecM[(unsigned int)m7 & 0xffffff80], _MM_HINT_T0); _mm_prefetch(&bytevecM[64+((unsigned int)m7 & 0xffffff80)], _MM_HINT_T +0);
    begins bringing into all CPU caches the two (64-byte) cache lines required by the q8 loop for the bytevecM lookup table before the loop starts. Note that 0xffffff80 above is just ~127 in disguise.

    Adding this prefetch hack reduced the running time by 6 seconds to 68 seconds = 68 * 125**4 / 60 / 60 / 24 / 365 = 526 years. Update: this was later improved from 6 to 17 seconds.

Nothingness - The far end of language development
2 direct replies — Read more / Contribute
by wjw
on May 03, 2014 at 04:56
    After having read an impressive meditation by eyepopslikeamosquito here The 10**21 Problem (Part 2) I went on a bit of a walk-about through CPAN; Not looking for anything in particular, just looking.

    Along the way I ran into a Moose, which was a bit of a surprise. I had heard of this creature in the world of Perl, had seen references to it, read a bit about it. But my understanding was that is was one of those 'Object' creatures which I have, for a long time, 'Object'ed to.

    Not for any good reason I guess. Mostly because God and everyone had been talking about object oriented programming as if the worlds existence prior to its appearance was somehow miraculous. "How did people get anything done?". Being the obstinate type, I plodded along shaking my head and writing my procedural code, getting the job done without accessors, roles, classes, instances, methods or any of the other goofy constructs that generated a whole new way of talking about code. I liked(and still do like) my simple variables, and sub-routines.

    But that illusion is finally to be set aside. My obstinate Luddite attitude, I have to admit finally, is being undermined by my use of all those handy CPAN modules that make it possible for me to talk to databases, coerce odd date representations into something I consider readable, deliver web pages and data for them, etc... .

    Yes, I am finally, after reading perlootut and perlobj, ready to admit that the goddamn OO stuff is useful, and I probably should have been learning it instead of ignoring it.

    All this from a wander through CPAN... And then I find it... The ultimate module! The one which inspires me to realize that I might as well go a head and learn something new after all this time. Someday, I might write a module with this level of elegance...something so fundamental that it leaves observers with nothing but the unanswerable question 'Why?'. It will not generate debate like our current Voting Booth subject. Nor will it genearate heady (worth-while, informative) study like the one previously mentioned that started tonights personal Chautauqua.

    A module which is, and does and contributes like this one. Some day... . Someday, I will achieve M!

    ...the majority is always wrong, and always the last to know about it...
    Insanity: Doing the same thing over and over again and expecting different results...
The 10**21 Problem (Part 2)
2 direct replies — Read more / Contribute
by eyepopslikeamosquito
on May 02, 2014 at 05:11

    There is no point looping over q9. Instead, notice that as q9 takes all possible values from 0..127, m9 will take the values from (m8&~127)..(m8&~127)+127 in a different order. Among those 127 possible values of m9, there can only be one that has the right value modulo 1001. You can compute that value directly, and try the corresponding single value for q9, checking if it lies in the range.

    -- ambrus' first theorem

    Part I of this new series of articles on high performance computing ended with a teaser:

    Can we eliminate the innermost loop somehow?

    Our resident Perl Monks mathematician, ambrus, answered this question with an emphatic yes, with what I cannot restrain myself from dubbing the first theorem of ambrus. Not satisfied with that, he composed a second theorem:

    ...it could use any modulus between 1001 and 9999. To search for the magic formula in that case, first compute t = gcd(m9 - 1000, d9 - 500) (be careful with underflows). Then compute the small prime factors of t, and using this, all divisors of t between 1001 and 9999, and check all those divisors as the modulus against the rest of the numbers. In the rare lucky case that t is 0, you will have to try all moduluses (or all divisors of c9 - 100).

    -- ambrus' second theorem

    Given my maths is weak, I am grateful to ambrus for his mathematical advice and wish him the best in his career as a mathematician, hoping one day he will be remembered with something as famous as ambrus' last theorem. :-)

    The first theorem of ambrus

    Compared to the beautiful flower that is ambrus' first theorem, my implementation of it (inner2.c) looks like an ugly weed:

    #define H_PRIME 1000003 #define HASH_LEN 11 // my_m128_t mimics Intel __m128i type typedef struct my_m128_t my_m128_t; struct my_m128_t { short m128i_i16[8]; }; int inner( int startval, int endval, int m2, int d2, int c2, int l2, int x2, int v2, int i2, my_m128_t* ps) { int m3, m4, m5, m6, m7, m9; int d3, d4, d5, d6, d7, d8, d9; int c3, c4, c5, c6, c7, c9; int l3, l4, l5, l6, l7, l9; int x3, x4, x5, x6, x7, x9; int q3, q4, q5, q6, q7, q8, q9; int dist; int iret = 0; for (q3 = startval; q3 < endval; ++q3) { if (q3 == 10 || q3 == 13) continue; m3 = (m2 ^ q3) * H_PRIME; d3 = (d2 ^ q3) * H_PRIME; c3 = (c2 ^ q3) * H_PRIME; l3 = (l2 ^ q3) * H_PRIME; x3 = (x2 ^ q3) * H_PRIME; for (q4 = 1; q4 < 128; ++q4) { if (q4 == 10 || q4 == 13) continue; m4 = (m3 ^ q4) * H_PRIME; d4 = (d3 ^ q4) * H_PRIME; c4 = (c3 ^ q4) * H_PRIME; l4 = (l3 ^ q4) * H_PRIME; x4 = (x3 ^ q4) * H_PRIME; for (q5 = 1; q5 < 128; ++q5) { if (q5 == 10 || q5 == 13) continue; m5 = (m4 ^ q5) * H_PRIME; d5 = (d4 ^ q5) * H_PRIME; c5 = (c4 ^ q5) * H_PRIME; l5 = (l4 ^ q5) * H_PRIME; x5 = (x4 ^ q5) * H_PRIME; for (q6 = 1; q6 < 128; ++q6) { if (q6 == 10 || q6 == 13) continue; m6 = (m5 ^ q6) * H_PRIME; d6 = (d5 ^ q6) * H_PRIME; c6 = (c5 ^ q6) * H_PRIME; l6 = (l5 ^ q6) * H_PRIME; x6 = (x5 ^ q6) * H_PRIME; for (q7 = 1; q7 < 128; ++q7) { if (q7 == 10 || q7 == 13) continue; m7 = (m6 ^ q7) * H_PRIME; d7 = (d6 ^ q7) * H_PRIME; c7 = (c6 ^ q7) * H_PRIME; l7 = (l6 ^ q7) * H_PRIME; x7 = (x6 ^ q7) * H_PRIME; for (q8 = 1; q8 < 128; ++q8) { if (q8 == 10 || q8 == 13) continue; d8 = (d7 ^ q8) * H_PRIME ^ HASH_LEN; d9 = d8 & ~127; d9 %= 1001; if (d9 < 0) d9 += 1001; if (d9 < 500 - 127) continue; if (d9 > 500 + 127) continue; dist = d9 < 500 ? 500 - d9 : d9 - 500; q9 = (d8 & 127) ^ dist; if (q9 == 0 || q9 == 10 || q9 == 13) continue; c9 = (c7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; c9 %= 1001; if (c9 < 0) c9 += 1001; if (c9 != 100) continue; l9 = (l7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; l9 %= 1001; if (l9 < 0) l9 += 1001; if (l9 != 50) continue; x9 = (x7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; x9 %= 1001; if (x9 < 0) x9 += 1001; if (x9 != 10) continue; m9 = (m7 ^ q8) * H_PRIME ^ HASH_LEN ^ q9; if (m9 == -1) m9 = -2; m9 %= 1001; if (m9 < 0) m9 += 1001; if (m9 != 1000) continue; ps[iret].m128i_i16[0] = q3; ps[iret].m128i_i16[1] = q4; ps[iret].m128i_i16[2] = q5; ps[iret].m128i_i16[3] = q6; ps[iret].m128i_i16[4] = q7; ps[iret].m128i_i16[5] = q8; ps[iret].m128i_i16[6] = q9; ++iret; } } } } } } return iret; }
    Comparing to inner1.c, discussed last time, you will notice the entire innermost q9 loop is now gone! The observant reader will have further noticed that I shortened and inlined the old py_mod function (see this stackoverflow question for more details on calculating modulos that contain negative numbers). Oh, and I also only bothered to calculate the first five Roman numbers (M, D, C, L, X) because hitting these five is rare enough that you can easily check with a separate program whether the last two (V and I) match.

    Since this inner2.c code is just plain ANSI C, you can try it out for yourself by combining with find1.cpp given in episode one. For example, using gcc on Linux:

    gcc -O3 -c inner2.c g++ -o find1 find1.cpp inner2.o
    Or Visual C++ on Windows:
    cl /W3 /MD /O2 find1.cpp inner2.c
    An example run on my (Haswell 4770K-powered) home PC is shown below:
    # find1 9 8 9 60 61 1 2 9: sv1=8 ev1=9 sv2=60 ev2=61 sv3=1 ev3=2: 9 8 60 1 94 6 51 38 78 100 (wall clock time:109 secs, cpu time:108.95 units)
    where 9 is the value of the outermost loop, and [8,9), [60,61), and [1,2) are the semi open ranges to search in the next three outer loops, with all other inner loops searched exhaustively.

    From that short run, we can estimate the total required running time as:

    109 * 125**4 = 26,611,328,125 seconds = 26611328125 / 60 / 60 / 24 / 3 +65 = 844 years
    The 125 in the formula above is used because we search the values 1..9, 11, 12, 14..127, a total of 125 distinct values.

    So, removing the innermost loop, via the first theorem of ambrus, reduced the estimated running time from 62,860 years down to 844 years, a 75-fold improvement! Yay!

Module::Runtime - Invalid version format
1 direct reply — Read more / Contribute
by kcott
on Apr 25, 2014 at 07:33

    A script that I've been running fairly regularly for the last three to four years unexpectedly died (Compilation failed) today. I was unable to find a match for the error via Super Search. I did find information in various other locations so I thought I'd gather them together here to save the next person some effort.

    I've found a (somewhat dodgy) work-around which fixes my immediate problem (described below). So, while I'm not actually asking for a solution, I'd be happy to hear about a better one.

    I'm running Perl v5.18.1 on darwin-thread-multi-2level.

    The error had two formats (from the same line of code). Initially, I got:

    Invalid version format (version required) at .../Module/Runtime.pm lin +e 386.

    After upgrading several modules, I got this:

    Invalid version format (non-numeric data) at .../Module/Runtime.pm lin +e 386.

    I found Ovid had written about this in blogs.perl.org: Moose Dying With "Invalid version format (version required)". There's a fair amount of discussion following Ovid's post.

    A bug report has been raised for this: Bug #92989 for Module-Runtime: bad if statement causes use_module() and use_package_optimistically() to fail

    Here's the Changes file describing the changes in Module::Runtime v0.014 that caused this issue.

    My initial attempts at a solution involved upgrading whatever modules I could find that seemed likely to be involved. One of the issues raised in Ovid's blog and the bug report was the fact that the problematic modules were not reported. I don't have a list of what I ugraded and it was a fairly diverse lot (some examples: MooseX::NonMoose, MooseX::ClassAttribute, Exception::Class::Base, version, et al). At some point, the error message changed from "version required" to "non-numeric data", as stated above, but didn't get me any further.

    I next tried rolling back to Module::Runtime v0.013. However, my version of Moose (2.1205) wanted Module::Runtime v0.014, so I reinstalled that.

    Finally, [after making a copy] I manually edited .../Module/Runtime.pm, changing line 386, in use_package_optimistically(), from:

    $name->VERSION($version) if @_ >= 2;

    to

    $name->VERSION($version) if @_ >= 2 && defined $version;

    My old script was now running again!

    [For anyone else choosing this path, there's a sub use_module($;$) {...} starting on line 346 which may need the same change. I didn't need to change this so, wanting to make the least manual changes, I left it alone.]

    -- Ken

The 10**21 Problem (Part I)
4 direct replies — Read more / Contribute
by eyepopslikeamosquito
on Apr 21, 2014 at 13:01

    When I looked for magic formulae, etc., I would give up after 20 minutes!

    -- Jasper

    Unlike Jasper, I have spent more than 20 minutes searching for magic formulae. Especially ancient Roman ones. I first became aware of them back in 2006 during the Fonality Christmas Golf Challenge where I was astonished by Ton's ingenuity and deviousness in constructing his original HART (Hospelian Arabic to Roman Transform) magic formula.

    Shortly after the Fonality game, codegolf.com hosted an endless competition where you must convert the other way, from Roman to Decimal. By 2009, I had managed to take the lead in all four languages (Perl, Python, Ruby, PHP), as detailed in this series of nodes. And the winning solutions -- in all four languages -- all used (quite different) magic formulae!

    To refresh your memory, the codegolf game rules were essentially:

    Convert a Roman numeral to its integer value. The input numeral, provided on stdin followed by a single newline, is guaranteed to be in the range I to MMMCMXCIX (1 to 3999). For example, given IV on stdin, your program should print 4 to stdout.

    As you might expect, a key component of solutions to this game is mapping individual Roman letters to their decimal equivalents. To help us focus on that, let's define a simpler spec:

    Write a function to convert a single Roman Numeral letter to its decimal equivalent. The function assumes the Roman letter is in $_ and returns its decimal equivalent.

    To clarify, here's a sample (non-golfed) Perl solution:

    sub r { my %h = ( I=>1, V=>5, X=>10, L=>50, C=>100, D=>500, M=>1000 ); return $h{$_}; } print "$_: ", 0+r(), "\n" for (qw(I V X L C D M));
    Running this program produces:
    I: 1 V: 5 X: 10 L: 50 C: 100 D: 500 M: 1000

    Lookup Table vs Magic Formula

    In code golf, there is often a battle between a lookup table and a magic formula. So it proved here. When converting from Roman to Decimal, magic formula trumps lookup table.

    Here are three attempts to solve this problem using a lookup table:

    sub r {%h=(I,1,V,5,X,10,L,50,C,100,D,500,M,1000);$h{$_}} sub r {M1000D500C100L50X10V5I1=~$_;$'} sub r {M999D499C99L49X9V4I=~$_+$'}

    And here are some of my earliest magic formulae from 2007:

    sub r {5**y/VLD//.E.(3*/M/+2*/C|D/+/X|L/)} sub r {1 .E.~-ord()*41%52%5>>y/VLD//} sub r {5**y/VLD//.E.ord()x3%75%50%4} sub r {1 .E.(72^ord)*5/7%5>>y/VLD//} sub r {5**y/VLD//.E.(42^88*ord)%5} sub r {1 .E.(3^77%ord)%7>>y/VLD//}
    Back then, my magic formula searching skills were so poor that I erroneously concluded that the lookup table approach was better. :-)

    Later, when I tackled this problem in Python, I really needed to use each Roman letter once only in the formula, which forced me to explore alternative approaches ... which, in turn, led to still shorter Perl magic formulae, such as:

    sub r {10**(7&69303333/ord)%9995} sub r {10**(7&5045e8/ord)%2857} # needs 64-bit Perl sub r {IXCMVLD=~$_;"1E@-"%9995}
    Back in the good old days, the little search programs that uncovered these solutions took hours to run, not years. :-)

    The long numbers (such as 69303333 above) that began popping up in these formulae were an indication that the ord function didn't scale very well as the required solutions became less probable. Can we find a built-in function better suited to Roman magic formulae? In PHP and Python, yes. In Perl and Ruby, probably not. At least, I don't know of one.

    The PHP built-in md5 function is perfect for Roman magic formulae. Not only does it generate all required digits (0-9), it generates little else (just a-f). Moreover, you can use all 256 characters in a magic formula, compared to just ten (0-9) for ord. To illustrate, in an eight character magic string (for example 69303333), there are just 10**8 combinations available for ord, while there are a mind-boggling 256**8=1.8*10**19 combinations available for md5! This is a huge advantage when searching for highly improbable solutions, as we shall see later.

    The Python hash function is also superior to ord, though not as good as PHP's md5. This is because Python's Unicode and character escaping claptrap limits you to 125 characters (namely ord 1..9,11,12,14..127) that can be used as input to the hash function without special treatment. Still, 125 is a huge improvement over 10! One drawback of hash compared to md5 is that it generates huge numbers, forcing you to waste five strokes with %1001 to trim the generated numbers into the required Roman Numeral range (1-1000).

    In some cases, the Perl crypt built-in could be employed, though it is not well-suited to this specific problem because (unlike md5) it generates many other characters in addition to the desired 0-9.

    To recap, the shortest magic formulae found so far in all four languages (as detailed in this series of nodes) are:

    10**(205558%ord(r)%7)%9995 # Python hash(r+"magicstrng")%1001 # Python (finding magicstrng is the subjec +t of this node!) VLD=~$_*5+IXCM=~$_."E@-" # Perl 10**(7&5045e8/ord)%2857 # Perl (64-bit) IXCMVLD=~$_;"1E@-"%9995 # Perl XCMVLD=~$_;"1E@+"%9995 # Perl (update: Grimy improvement) uppp&md5_hex$_.PQcUv # Perl (needs Digest::MD5 module) 10**(494254%r/9)%4999 # Ruby (no need for explicit ord in this g +ame) md5($r.magicstrng) # PHP (finding magicstrng is an unsolved p +roblem) md5($r.PQcUv)&uppp # PHP wins due to superb mf properties of +md5

    The 10**21 Problem

    There's just no sane regularity in this thing. But in "random" mappings with a very small result set like this, the shortest solution is often to make up some magic formula that has no particular meaning, but just happens to give the wanted result.

    -- Ton Hospel explaining his original decimal-to-roman magic formula

    When Ton Hospel invented magic formulae in golf way back in 2004, he correctly noted that they work best "with a very small result set". Indeed, if there were only five Roman Numeral letters, rather than seven, we would have a straightforward 10**15 problem, rather than a (borderline intractable) 10**21 problem. Why 10**21?

    Suppose you have a magic formula that produces a random number between 1 and 1000. The probability of scoring a (lucky) hit for one numeral is therefore 1 in 1000. Since probabilities multiply, the probability of hitting five out of five numerals is 1 in 10**15, while the chance of hitting all seven Roman Numerals is a daunting 1 in 10**21. Though 1 in 10**21 sounds improbable in the extreme, if you could generate 10**21 combinations, you would not need luck, indeed you would expect to find such an improbable solution. Yet how long would it take to search 10**21 combinations for the elusive (lucky) one?

    Well, if you could perform 10,000 search operations per second, the time required to search 10**21 combinations is a mere 10**21/10000 seconds = 10**17 seconds = 3,170,979,198 years! By the way, this "brute force search infeasibility problem" is why you are asked to create longer and longer passwords, and with a wider range of characters in them, as computer speeds improve. Indeed, Password cracking and magic formula searching are closely related disciplines, the lack of a "codegolf magic formula" wikipedia page notwithstanding. :-)

    To make this theoretical argument more concrete, consider searching for a Roman to Decimal magic formula using the Python built-in hash function. Since this hash function produces very large values, we need to apply %1001 to it so as to produce an essentially random value in the desired 1..1000 range. We might try searching for such a magic formula using a simple Python brute-force search program, such as:

    import time print time.time(), time.clock() for q0 in range(1, 128): for q1 in range(1, 128): for q2 in range(1, 128): for q3 in range(1, 128): for q4 in range(1, 128): for q5 in range(1, 128): for q6 in range(1, 128): for q7 in range(1, 128): for q8 in range(1, 128): for q9 in range(1, 128): magic = chr(q0)+chr(q1)+chr(q2)+chr(q3)+chr(q4)+chr(q5)+chr( +q6)+chr(q7)+chr(q8)+chr(q9) m = hash("M" + magic) % 1001 if m != 1000: continue d = hash("D" + magic) % 1001 if d != 500: continue c = hash("C" + magic) % 1001 if c != 100: continue l = hash("L" + magic) % 1001 if l != 50: continue x = hash("X" + magic) % 1001 if x != 10: continue v = hash("V" + magic) % 1001 if v != 5: continue i = hash("I" + magic) % 1001 if i != 1: continue print "bingo!", q0, q1, q2, q3, q4, q5, q6, q7, q8, q9 print time.time(), time.clock()
    On my machine, this naive brute force search for a ten-character magic string is expected to find a solution in about 52,887,477 years! Note that, with 127 different values for each character in the string, we need a 10-character magic string to give us the required 127**10 = 1.1e21 = 10**21 combinations.

    Rather than give up at this point, I found this "impossible" 50 million year challenge strangely irresistible ... and was eager to learn about any high performance computing techniques required to solve it.

    I get it -- optimization is a fun game ... one can play all day with unrolling loops, peeling away layers of indirection, and so forth to gain cycles, while piddling away time and energy

    -- davido

    Or, as davido puts it, "optimization is a fun game". Well, I enjoy it. So I started by rewriting the above search program in C++, then kept on refining it until I was able to reduce the running time from fifty million years down to only several years and eventually find a solution. This new series of articles describes that endeavour.

    Please note that this series focuses more on High Performance Computing/Supercomputing/Parallel computing in C/C++/Intel assembler than code golf.

PerlBrew (perlbrew list-modules)
No replies — Read more | Post response
by wjw
on Apr 19, 2014 at 12:28
    PerlBrew
    has a bug(85493) noted in version 0.63 which has yet to be addressed. I spent a good 2.5 hours trying to figure out why 'perlbrew list-modules' didn't return anything. Finally found the the problem in the bug list at RT CPAN. The actual cause of the problem was pointed out Here on github.

    In simple terms: the command 'list-modules' will not work if you are use'ing or have switch'ed to an alias.

    You must use the full name of the Perl dist you are using as is shown in 'perlbrew list' or 'perlbrew available'. (See Update below for alternative)


    Perlbrew is fantastic! (minor rant) It is a bit disappointing that this ticket has been around for 11 months without being addressed. It is not an obvious(to me) issue to find or address. My searches(both here and google) rendered very little. The docs here don't make any mention of this either.
    My hope is that someone may save themselves some time finding this here when faced with this issue.


    Note:

    Was unsure where to post this, but based on FAQ Re: Posting this seems the best place... please correct me if not.

    Update:

    Found a workaround listed Stack Overflow which states that when installing a Perl via PerlBrew, one can use the '--as' install option to name the Perl install, accomplishing something like the alias command would. While it is good to know how to work around this problem, I would still rather have the 'alias' command work. I don't always know ahead of time what I might want to name a given install.

    Replaced the  <br> with  <p> for readability.

    ...the majority is always wrong, and always the last to know about it...
    Insanity: Doing the same thing over and over again and expecting different results...
Lotto checker...
3 direct replies — Read more / Contribute
by fishy
on Apr 15, 2014 at 10:41
    or nice map/grep exercise...
    #!/usr/bin/perl use strict; use warnings; my $draw = [ qw( 13 15 18 22 41 48 ) ]; my $bets = [ [ qw( 09 13 18 33 39 42 ) ], [ qw( 02 18 32 36 39 42 ) ], [ qw( 05 12 21 22 28 42 ) ], [ qw( 03 14 18 33 34 36 ) ], [ qw( 15 22 26 41 38 48 ) ], [ qw( 06 14 24 26 42 48 ) ], [ qw( 10 28 30 35 36 43 ) ], [ qw( 03 05 08 14 16 35 ) ], [ qw( 08 18 21 35 46 47 ) ], [ qw( 03 15 22 25 46 48 ) ], [ qw( 01 11 38 44 45 49 ) ], [ qw( 14 23 38 39 48 49 ) ], [ qw( 07 17 21 32 45 48 ) ], [ qw( 07 36 37 39 40 41 ) ], [ qw( 07 12 20 29 36 43 ) ] ]; map { my $bet = $_; my $hits = 0; map { my $one = $_; $hits += grep { $one eq $_ } @$bet; } @$draw; print join $", @$bet, "-->", $hits, $hits > 2 ? "*" : "", "\n"; } @$bets;
-Ofun times
4 direct replies — Read more / Contribute
by raiph
on Apr 12, 2014 at 00:35
    »»» This post is about the immature Perl 6, not the rock solid Perl 5 «««

    In the last few months jnthn has added optimizing stages to the Rakudo/NQP/backends compiler stack. In his latest blog post he outlines these stages and notes some early results from a few things he and timotimo have already done ("Array and hash access is more than 3 times faster, most multi-dispatches are now enormously cheaper").

    There's other news too, so even if you're not ready for -Ofun the linked blog post is still worth a read if you are interested in P6.

RFC: API for declarative parameterized web queries
3 direct replies — Read more / Contribute
by smls
on Apr 10, 2014 at 17:17

    Hello all!

    Since I'm doing web querying/scraping of tabular data in several of my scripts, I want to refactor this functionality into a convenient module, and I would appreciate some input/criticism/wisdom from the other resident monks on that topic... :)

    By "query", I mean a complete recipe for downloading a document from the web and extracting relevant pieces from it using XPath expressions and/or regexes.
    By "tabular data", I mean that when a query is executed, it returns a list of items where each item has the same set of pre-defined "fields".

    The module's API should allow query definitions to be:

    • encapsulated - Everything that defines a particular query, should appear together as one self-contained unit in the user's source code.
    • declarative - Don't make the user write unnecessary boilerplate code or worry about implementation details.
    • reusable - Once a query is defined, it should be very easy for the user to execute it many times with different parameters during the program's execution.
Carrying (mini)CPAN
1 direct reply — Read more / Contribute
by fishy
on Apr 05, 2014 at 10:47
    Thanks to minicpan, I keep a local copy of the latest versions hosted on CPAN.
    Running minicpan weekly, I keep it up to date.
    My .minicpanrc file:
    local: /home/netbook/minicpan/miniCPAN_20140405/ remote: http://your.favorite.cpan.mirror/ also_mirror: indices/ls-lR.gz
    Now, I want to carry my local minicpan keeping it on a memory stick.
    Changing .minicpanrc to:
    local: /media/USB16GB/miniCPAN_20140405/ remote: file://home/netbook/minicpan/miniCPAN_20140405/ also_mirror: indices/ls-lR.gz
    and running minicpan again, sweeps my minicpan onto my stick.
    Fine.
    Now, I can install any module offline (as long as specific version dependencies are satisfied).
    Just mount my stick and either, first time running cpan:
    ... Would you like to configure as much as possible automatically? [yes] ... sites for you? (This means connecting to the Internet) [yes] no ... Would you like to pick from the CPAN mirror list? [yes] no ... Please enter your CPAN site: [] file:///mnt/minicpan Enter another URL or ENTER to quit: [] New urllist file:///mnt/minicpan/ Autoconfiguration complete. commit: wrote '/home/userOne/.cpan/CPAN/MyConfig.pm' ...
    or by modifying manually ~/.cpan/CPAN/MyConfig.pm
    ... 'urllist' => [q[file:///mnt/minicpan]], ...
    So, it's easy installing modules on offline systems or installing apps on user (e.g. /home/user) Perls.

    Have fun!

    UPDATE: After discovering how to comment, my .minicpanrc looks like:
    ## web ---> local disk (computer A) #local: /home/netbook/minicpan/miniCPAN_20140414/ #remote: http://your.favorite.cpan.mirror/ #also_mirror: indices/ls-lR.gz ## local disk (computer A) ---> USB local: /media/USB16GB/miniCPAN_20140414/ remote: file://home/netbook/minicpan/miniCPAN_20140414/ also_mirror: indices/ls-lR.gz ## USB ---> local disk (computer B) #local: /home/dan/miniCPAN/miniCPAN_20140414/ #remote: file://media/usb/miniCPAN_20140414/ #also_mirror: indices/ls-lR.gz
Wrong + Right = Even Worse
8 direct replies — Read more / Contribute
by choroba
on Apr 03, 2014 at 09:39
    In a legacy project at work, we have lots of scripts that should in fact be modules. But they declare no package, use the .pl extension and call each other via require. Originally, the full paths were used in require, which constituted one of the obstacles to run the project locally. I replaced all the occurrences of
    require '/path/to/some/script.pl';

    with

    use lib '/path/to/some'; require 'script.pl';

    and I was able to run some of the scripts locally (I had to add some paths to @INC).

    After several days, we noticed some of the scripts failed. I inspected the code and discovered that there was one newer OO module that was written "correctly": it lived in a .pm file and declared a package. It used lib and only required the script names.

    Combining "right" and "wrong" led to "even worse": The OO module required several .pl files. All the subroutines they declared were therefore created in the namespace of the module. Later, when a calling script required the same .pl file, it already existed in %INC, so it was not read again. No import was called anywhere, so the subroutines did not appear in the main:: package.

    Here are sample files so you can try it yourself:

    module.pm

    package module; use warnings; use strict; require 'required1.pl'; subroutine(); warn 'module INC: ', $INC{'required1.pl'}; __PACKAGE__

    required1.pl

    #!/usr/bin/perl use warnings; use strict; warn "Loading 1"; sub subroutine { my $file = (caller)[1]; $file =~ s=.*/==; warn 'subroutine defined in ', $file; } subroutine(); 1;

    script.pl

    #!/usr/bin/perl use warnings; use strict; use FindBin; use lib $FindBin::Bin; require 'required1.pl'; use module; warn 'script INC ', $INC{'required1.pl'}; subroutine();

    Update:

    The Conclusion

    We now have 2 options:

    1. Revert to the original full-path style require with no possibility to run the project locally.
    2. Refactor everything to proper modules. 100,000+ lines.

    Update2:

    I just had an idea: there is a third option. In the OO module, store %INC at the beginning, do all you need, then set %INC back to what it was.

    my %_INC = %INC; # ... %INC = %_INC;
    لսႽ† ᥲᥒ⚪⟊Ⴙᘓᖇ Ꮅᘓᖇ⎱ Ⴙᥲ𝇋ƙᘓᖇ

Add your Meditation
Title:
Meditation:
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!
  • 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
  • Outside of code tags, you may need to use entities for some characters:
            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 taking refuge in the Monastery: (8)
    As of 2014-08-23 16:13 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The best computer themed movie is:











      Results (174 votes), past polls