RE: RE (tilly) 3: Fisher-Yates Shuffle

[Adam]

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.