I've just put some code together to test the advantage seen with skipping combinations which aren't sorted. It's significantly slower compared to pass-ing everything but putting a quick method together to do some actual work shows the improvement. Unfortunately doing some actual work pushes up the time taken. My quick check (running this code https://gist.github.com/2174656 ) suggests skipping unsorted iterations brings down the total running time from 7000 to 4000 days.
I suspect to see 'reasonable' run times we would need to fundamentally rethink the approach we're using. At the moment I don't think we can even brute force it by 'bursting' to the cloud. I don't know how the other providers compare but taking aws http://aws.amazon.com/ec2/#instance as an example the individual cores aren't anything special. The advantage comes when you can use lots of them, either on a instance with lots of cores or on multiple instances. Given the discussion here I'm tempted by the tutorials on high performance python but at 3 hours they might be a little long. http://pyvideo.org/video/614/high-performance-python-i http://pyvideo.org/video/620/high-performance-python-ii http://pyvideo.org/video/618/optimize-performance-and-scalability-with-paralle On 23 March 2012 07:23, [email protected] <[email protected]>wrote: > On 22 March 2012 23:17, Edward Saxton <[email protected]> wrote: > >> 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. > > > I'm quite keen on this too. The interesting challenge will be to choose > which talks to air. If there are no objections, perhaps we could mail > through suggestions then take a vote several days before the next meeting. > (Do take into account the quality of the recording when making > suggestions!) > > Safe > > >> >> >> Ed >> >> -- >> To post: >> python-north-west@**googlegroups.com<[email protected]> >> To unsubscribe: >> python-north-west-unsubscribe@**googlegroups.com<[email protected]> >> Feeds: >> http://groups.google.com/**group/python-north-west/feeds<http://groups.google.com/group/python-north-west/feeds> >> More options: >> http://groups.google.com/**group/python-north-west<http://groups.google.com/group/python-north-west> >> > > -- > 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 > -- 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
