Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
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.

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 all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (8)
As of 2017-02-24 06:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Before electricity was invented, what was the Electric Eel called?






    Results (353 votes). Check out past polls.