*Tonight* - 15th March 2012 - Python Northwest Coding Meetup - MadLab @ 7pm
safe....@sandacre.com
Dave Hughes
> * When: Tonight Thursday 15th March @ 7pm.
>
> * Where: MadLab, Manchester
> - URL: http://madlab.org.uk/
> - Address: 36-40 Edge Street, Manchester, M4 1HN in the Norther
> Quarter (just opposite Common Bar/Cafe/Restaurant).
> - Map: http://bit.ly/hgTNln
>
> Sadly it's looking unlikely that I'll be able to make it tonight, but
> have a great time!
Many apologies, but I'm unable to make this evening either (sorry for
the last minute realization!). Hopefully with my better half back next
time, I'll be better organized!
Have fun!
Dave.
Jonathan Street
In the pub afterwards a piece of code, I think written in matlab, was mentioned which cycled through all possible RGB colours and displayed them in an image. Apparently this code took 30 minutes to run. I was curious to see how long it would take in python so on the train home I wrote a snippet of code to check (https://gist.github.com/2049532). On my laptop it never takes more than 30 seconds.
Less than half the people there yesterday were also there for the last coding session so we didn't continue with the noughts and crosses bots. I had revisited the code yesterday afternoon and adjusted the interface on the bot I had been involved in writing to match the runner. I then fixed some further bugs in our bot on the train home. Currently both bots work and can't be beaten by their opponent. I suspect a more skilled opponent could out-fox both bots though. It's interesting that they're so closely matched. I've sent a pull request with my changes (https://bitbucket.org/safehammad/dojo-oxo/pull-request/1/it-works)
--
To post: python-north-west@googlegroups.com
To unsubscribe: python-north-west-unsubscribe@googlegroups.com
Feeds: http://groups.google.com/group/python-north-west/feeds
More options: http://groups.google.com/group/python-north-west
safe....@sandacre.com
The session last night seemed to go fairly well. We decided to work on a generator of nontransitive dice (https://en.wikipedia.org/wiki/Nontransitive_dice). Both groups began with writing generators for all possible dice given upper and lower bounds and fixed number of dice and sides. As such much time was spent on getting (re)acquainted with itertools.
In the pub afterwards a piece of code, I think written in matlab, was mentioned which cycled through all possible RGB colours and displayed them in an image. Apparently this code took 30 minutes to run. I was curious to see how long it would take in python so on the train home I wrote a snippet of code to check (https://gist.github.com/2049532). On my laptop it never takes more than 30 seconds.
Less than half the people there yesterday were also there for the last coding session so we didn't continue with the noughts and crosses bots. I had revisited the code yesterday afternoon and adjusted the interface on the bot I had been involved in writing to match the runner. I then fixed some further bugs in our bot on the train home. Currently both bots work and can't be beaten by their opponent. I suspect a more skilled opponent could out-fox both bots though. It's interesting that they're so closely matched. I've sent a pull request with my changes (https://bitbucket.org/safehammad/dojo-oxo/pull-request/1/it-works)
On 15 March 2012 17:55, Dave Hughes <da...@waveform.org.uk> wrote:
On 15/03/12 07:43, safe....@sandacre.com wrote:Many apologies, but I'm unable to make this evening either (sorry for the last minute realization!). Hopefully with my better half back next time, I'll be better organized!
* When: Tonight Thursday 15th March @ 7pm.
* Where: MadLab, Manchester
- URL: http://madlab.org.uk/
- Address: 36-40 Edge Street, Manchester, M4 1HN in the Norther Quarter (just opposite Common Bar/Cafe/Restaurant).
- Map: http://bit.ly/hgTNln
Sadly it's looking unlikely that I'll be able to make it tonight, but have a great time!
Have fun!
Dave.
--
To post: python-north-west@googlegroups.com
To unsubscribe: python-north-west-unsubscribe@googlegroups.com
Feeds: http://groups.google.com/group/python-north-west/feeds
More options: http://groups.google.com/group/python-north-west
Edward Saxton
> On 16 March 2012 11:14, Jonathan Street <streetj...@gmail.com
>
> The session last night seemed to go fairly well. We decided to work
> on a generator of nontransitive dice
> (https://en.wikipedia.org/wiki/Nontransitive_dice). Both groups
> began with writing generators for all possible dice given upper and
> lower bounds and fixed number of dice and sides. As such much time
> was spent on getting (re)acquainted with itertools.
>
>
> Seems like an interesting evening. I often find my self getting
> (re)(re)(re)acquainted with itertools every time I start a new project.
> Any code to share?
This isn't from that night, but over the weekend I realized there was an
O(n+m) solution to part of the problem (scoring the dice) where
everything we wrote on the day was O(nm).
https://gist.github.com/2147071 .
Full and simple are about what was written on the night from what I
remember, and oneline is me playing with reduce.
Actually generating dice and finding nontransitive sets is left as an
exercise for the reader ;)
> In the pub afterwards a piece of code, I think written in matlab,
>was mentioned which cycled through all possible RGB colours and displayed
> them in an image. Apparently this code took 30 minutes to run. I was
> curious to see how long it would take in python so on the train home I
> wrote a snippet of code to check (https://gist.github.com/2049532). On my
> laptop it never takes more than 30 seconds.
>
>
> Another nice use of itertools.
>
Yeah very nice, I'm always impressed by how much hard work suddenly
hides when you remember itertools. Normally closely followed by my CPU
maxing out as I ask it to do something far too big for it.
Ed
Jonathan Street
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.
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
...
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.
On 19/03/2012 05:50, safe....@sandacre.com wrote:
On 16 March 2012 11:14, Jonathan Street <streetj...@gmail.com
Edward Saxton
> 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
safe....@sandacre.com
Jonathan Street
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
Edward Saxton
> 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.
My computer shows a similar speedup from 4500 days to 2000 days. Still
too slow. Then I discovered, once again that itertools is awesome (in
this case in 2.7 (and probably 3.x) only). Replacing sorted generator with
def sorted_exhaustive(num):
for h in itertools.combinations_with_replacement(range(1,7), num):
stub_comparison(h)
Cuts the time down to about a day.
There is some bad news however. The way you're using this to generate
dice sets, building one list for the whole set and splitting it, doesn't
work with this optimization. You'll get a 'low dice', 'higher dice' and
'highest dice', not what's needed at all.
> 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.
Keeping the fast die generation technique and generating sets of dice with
def split_dice(num, high=7):
pool = itertools.combinations_with_replacement(range(1,high), num)
for a, b in itertools.combinations(pool, 2):
dice.simple(a, b)
should let us trade some ram for speed.
On my computer running this with num = 9 (which would be sets of two
nine sided dice with numbers from 1-6 on each side) takes about 35 seconds.
Trying something similar with sets of three dice:
def full_split_dice(num, high=7, size=3):
pool = itertools.combinations_with_replacement(range(1,high), num)
for selection in itertools.combinations(pool, size):
for a, b in itertools.combinations(selection, 2)
dice.simple(a, b)
on my computer takes:
num time
3 0.3sec
4 5sec
5 50 sec
and running it with num=3 and high=10 (which the example dice
effectively had as each number from 1 to 9 was used twice the same die)
takes 7 seconds.
Fast enough for you? :)
https://gist.github.com/2176168
It still needs a way to identify valid sets. Also scaling it up to all
sets of six sided dice (num=6 and high=19) or sets of more than three
dice is probably going to take more work. If I can find the time those
are problems for Sunday.
> 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
That depends, it's only two of us so far. Are other people following
along interestedly?
Ed
Edward Saxton
> It still needs a way to identify valid sets. Also scaling it up to all
> sets of six sided dice (num=6 and high=19) or sets of more than three
> dice is probably going to take more work. If I can find the time those
> are problems for Sunday.
Here's completed code that manages to find the example dice we were
looking at.
https://gist.github.com/2320601
Running it on my computer for all sets of three, three sided dice it
takes about 8 seconds to find 57 sets if duplicated sides on a dice are
allowed e.g. (3, 6, 9), (4, 7, 7), (5, 5, 8) and just under a second if
they're not finding (1, 5, 9), (2, 6, 7), (3, 4, 8) and (1, 6, 8), (2,
4, 9), (3, 5, 7). All of these results have the same 4/9 v 5/9 bias.
If anyone can see improvements to let fast enough to search dice with
more sides, or how to make it search sets of more dice I'd be glad to
hear them.
Ed