Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: mem usage

by jwkrahn (Monsignor)
on May 26, 2010 at 18:07 UTC ( #841772=note: print w/ replies, xml ) Need Help??


in reply to mem usage

Your shuffle algorithm is not very good.    Better to use the one from the FAQ: How do I shuffle an array randomly? or use the shuffle function from the List::Util module.


Comment on Re: mem usage
Re^2: mem usage
by ikegami (Pope) on May 26, 2010 at 18:30 UTC

    Your shuffle algorithm is not very good.

    It looks like a Fisher-Yates shuffle, which is what List::Util uses. Or did you spot a bug?

      Sorry, but the way he implemented it threw me off.

Re^2: mem usage
by halfcountplus (Hermit) on May 26, 2010 at 18:43 UTC
    Yeah, that's Fisher-Yates (aka Knuth #12 or something). It works in place and I've never had any problems with it,* dunno why you think it's "not very good". Kind of a wacky place to put i-- but that's pretty trivial, style wise.

    *(eg, just shuffled those 12 millon lines, no errors, since I am feeding that into something else I will notice if something gets duplicated et. al.)

      You can trim your shuffle a little by omitting the line:         next if $i==$j;.

      Swapping an item with itself doesn't affect the algorithm's fairness, and doing it once costs less, than testing n times and avoiding it once.

      And you save a little more by avoiding the list assignment:

      my $tmp = $array[ $i ]; $array[ $i ] = $array[ $j ]; $array[ $j ] = $tmp;

      Doesn't look as nice though.


      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
        You can trim your shuffle a little by omitting the line: next if $i==$j;

        Good point!
        Including cleaning up the counter,
        sub shuffle { my $array = shift; my $i = @$array; while ($i) { my $j = int rand($i--); my $t = $array->[$i]; $array->[$i] = $array->[$j]; $array->[$j] = $t; } }

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://841772]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (9)
As of 2014-09-23 09:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (216 votes), past polls