On 22/03/2012 20:52, Jonathan Street wrote:
Unfortunately my laptop crashed and then crashed again so we decided
against using it to develop our solution. The dice generating code was
just itertools.product and then some list slicing to generate the right
number of dice with the right number of sides.
It's great to see improved code for the scoring. Having quickly tested
the different solutions it seems that the fast approach is actually
slower than the simple approach for the supplied dice. Do you get that
as well? I wonder what size the dice need to be for the fast version to
perform better. An optimised method that checks the sizes of the dice
and then calls the faster method could be useful.
Yeah I considered adding a note that better big-O isn't the same thing
as fast for this situation. But the technique seemed worth showing off
regardless.
My guess for which one is actually fastest is the unreadable one liner -
just based on the fact that implicit loops like reduce are highly
optimized. Actually my guess for the fastest version in python would be
something along the lines of:
def oneline(a, b):
# uses on True == 1 and False == 0
return reduce(lambda v, w: (v[0]+w[0], v[1]+w[1]),
((ra>rb, ra<rb) for ra, rb in itertools.product(a, b)))
because of reduced memory use of a generator v a list comprehension.
This is all theoretical though, I've not timed any of them and really
what we want to be doing is comparing less dice rather than comparing
them faster.
I think some improved approach to generating the dice is also needed.
Running through the output of itertools.product with the code below on
smaller numbers of repeats and extrapolating indicates it would take
over 170 days to run through all the iterations for 3 6-sided dice
>>> def exhaustive(num):
... g = itertools.product(range(1,7), repeat=num)
... for h in g:
... pass
...
With num = 3 this method will use (1, 1, 3), (1, 3, 1) and (3, 1, 1) as
different dice but they will all roll and compare the same. Stripping
those out with
>>> def transformed_exhaustive(num):
... g = itertools.product(range(1,7), repeat=num)
... g = (i for i in g if list(i) == sorted(i))
... for h in g:
... pass
takes you down from 216 dice to 56. Calling that 1/4 the size that
should cut the time for three blocks of dice down by about 1/(4^3) or
1/64. Not bad for one extra line, and it should get better as num goes
up :)
That probably still puts you at more than a day though. I guess the next
step would be looking at how you generated the sets of dice and removing
duplicates there.
After that ... well I'd probably need to actually write and time some
code rather than just playing with theory. Or I could read yours. Or you
could just rent some time in the cloud again ;)
On the subject of talks I've heard a couple of other groups raise the
possibility of picking one or more pycon talks and watching them before
further discussion.
An idea worth stealing.
Ed
--
To post: [email protected]
To unsubscribe: [email protected]
Feeds: http://groups.google.com/group/python-north-west/feeds
More options: http://groups.google.com/group/python-north-west
