Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^3: rand + shift || pop

by lidden (Curate)
on Dec 21, 2010 at 15:58 UTC ( #878294=note: print w/ replies, xml ) Need Help??


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

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.


Comment on Re^3: rand + shift || pop
Download Code
Replies are listed 'Best First'.
Re^4: rand + shift || pop
by JavaFan (Canon) on Dec 21, 2010 at 16:41 UTC
    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).

Re^4: rand + shift || pop
by ikegami (Pope) on Dec 21, 2010 at 17:21 UTC
    It's only O(1) if you remove from the start or the end.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (10)
As of 2015-07-29 23:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (269 votes), past polls