First of all... don't worry about ranting. I took no offense, I'm just trying to understand this shuffle algorithm. Specifically I don't understand why the branch test is in there.

Ok, on with the math! I almost failed numerical analysis and its been years since I've opened a calc book, so I'll trust you on your calculation of averages. Actually, your math makes sense up till the bit about trapezoids. <grin>

However, I do NOT believe that I miss read the Fisher-Yates algorithm... its exactly as you said, I just re-conceptualized it. Either way you look at it, the size of the range for rand is decremented one each time. This means that the range for the first pass at an array of size N is the same as the size of the range for the second pass of an array of size N+1. I think we're on the same page, I'm just off on the fringes. Which is ok.

What this all boils down to is that the branch is not needed.

Oh,
As a side note, please don't tell me not think about it in terms of assembly... everything has to boil down to machine code at some point, and the easiest way to think in terms of machine code is assembly. I don't really care what path it takes to get there... C, perl op codes, whatever. The reality is that its all 1s and 0s. And every extra mucking about with them takes time. The trick to optimizing an algorithm like this is to determine the best way to minimize the extra electron traffic. What varies from language to language is how much control you have over that traffic. Perl doesn't give you much, but I am trying to learn where it does.

In reply to RE: RE (tilly) 3: Fisher-Yates Shuffle by Adam
in thread Fisher-Yates Shuffle by Adam

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, details, 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, summary, 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.