[Tutor] Deal a Random Deck - Challenge
Zak Arntson
zak@harlekin-maus.com
Fri Jul 25 16:15:02 2003
Here's an interesting problem a coworker (former mentor) uses when hiring:
* Write an algorithm to deal out a set of "cards"
It's pretty straightforward in C, and here's a port of the C code in Python:
###
import random
def deck(size):
d = range(size)
for i in range(size):
r = random.randrange(i, size)
temp = d[i]
d[i] = d[r]
d[r] = d[i]
return d
###
You can replace the swap code, but weirdly it's slower to process.
###
import random
def deck2(size):
d = range(size)
for i in range(size):
r = random.randrange(i, size)
d[i], d[r] = d[r], d[i]
return d
###
Then my coworker turned around with this solution, which turns out to be
the fastest of the three:
###
import random
def deck3(size):
d = [(random.random(), i) for i in range(size)]
d.sort()
return [d[i][1] for i in range(size)]
###
So my challenge, then: Can anyone come up with an even faster solution
than option 3?
As an aside, I tried this with deck(100000) through the profiler and go
cumtimes as follows: deck = 5.126, deck2 = 5.693, deck3 = 3.327
---
Zak Arntson
www.harlekin-maus.com - Games - Lots of 'em