Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Re^2: rand + shift || pop

by magnus (Pilgrim)
on Dec 21, 2010 at 15:32 UTC ( #878289=note: print w/replies, xml ) Need Help??

in reply to Re: rand + shift || pop
in thread rand + shift || pop

While splice is helpful, shuffle + shift || pop is a very simple and elegant solution. Didn't even twig on that one. Thanks very much.

Replies are listed 'Best First'.
Re^3: rand + shift || pop
by lidden (Curate) on Dec 21, 2010 at 15:58 UTC
    Shuffleing is O(n) and spliceing is O(1), this may matter if your array is large.

    Update: Oops, my understanding of splice was wrong. See JavaFan and ikegami below.

      Actually, the expected running time of splicing is Ω(n), as a random splice will have to move n/4 elements on average.

      If you want to repeatedly get a random element (without duplication), shuffle the array and use pop or shift, for a linear running time. Repeatedly splicing a random element has an expected running time of Ω(n2).

      It's only O(1) if you remove from the start or the end.

Log In?

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

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2023-12-09 02:44 GMT
Find Nodes?
    Voting Booth?
    What's your preferred 'use VERSION' for new CPAN modules in 2023?

    Results (37 votes). Check out past polls.