Hi,
I recently got the urge to calculate winning probabilities for Texas
Hold'em starting hands. I did not bother with some fancy statistical
methods (I don't know any), and brute force should be more than fast
enough on modern hardware.
I've been programming C++ professionally for a couple of years, but I
did not want to use it in this little pet project. It was time to give a
n interactive language a shot. I decided on Python since it's extremely
easy to get started with, once you know C++.
Calculating the winning probabilities was easier than i thought, and the
clear syntax and expressive powers of Python made the code very short
and sweet. And slow. I feared that it would be slow, but I was still
surprised when it took around one minute to get the percentages for two
hands, all the way to the river.
Now I'm facing a dilemma. I could factor out the time consuming parts of
the code to C++, but that would negate the purpose of choosing Python in
the first place. If only Python would come with a compiler. I think it's
time to give Lisp a shot. Lisp seems to have it all, at least that's
what I have heard.
Does any of you excellent sirs have a recommendation on what Lisp
implementation to choose? I need to compile the source to machine code
for speed, and preferably so on windows. It would also be nice if the
Lisp came with some facility to load dll's and generate bindings for the
functions it exports, but this is perhaps too much to ask. Other than
that it should be free. I'll use the clisp that comes with cygwin for
now, just to get things started.
Just one more thing: This is how i generate all possible poker hands in
Python (or all possible n length combinations of any list of items):
def comb(items, n):
if n==0: yield []
else:
for i in xrange(len(items)):
for cc in comb(items[i+1:],n-1):
yield [items[i]]+cc
This gives the hands one at a time using generators. This means that I
can iterate over the hands like so:
for hand in comb(deck, 5):
...
where deck is a list of the 52 cards (minus the starting hands).
I'm sure I can do this in Lisp in much the same way, but I'm not sure
how. Lisp code hurts my head, but I'm counting on it to stop :)
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
From: Bill Atkins
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <873bhzlfuw.fsf@rpi.edu>
Frode Øijord <·····@sim.no> writes:
> Hi,
> I recently got the urge to calculate winning probabilities for Texas
> Hold'em starting hands. I did not bother with some fancy statistical
> methods (I don't know any), and brute force should be more than fast
> enough on modern hardware.
>
> I've been programming C++ professionally for a couple of years, but I
> did not want to use it in this little pet project. It was time to give
> a n interactive language a shot. I decided on Python since it's
> extremely easy to get started with, once you know C++.
>
> Calculating the winning probabilities was easier than i thought, and
> the clear syntax and expressive powers of Python made the code very
> short and sweet. And slow. I feared that it would be slow, but I was
> still surprised when it took around one minute to get the percentages
> for two hands, all the way to the river.
>
> Now I'm facing a dilemma. I could factor out the time consuming parts
> of the code to C++, but that would negate the purpose of choosing
> Python in the first place. If only Python would come with a
> compiler. I think it's time to give Lisp a shot. Lisp seems to have it
> all, at least that's what I have heard.
>
> Does any of you excellent sirs have a recommendation on what Lisp
> implementation to choose? I need to compile the source to machine code
> for speed, and preferably so on windows. It would also be nice if the
> Lisp came with some facility to load dll's and generate bindings for
> the functions it exports, but this is perhaps too much to ask. Other
> than that it should be free. I'll use the clisp that comes with cygwin
> for now, just to get things started.
>
> Just one more thing: This is how i generate all possible poker hands
> in Python (or all possible n length combinations of any list of
> ITEMS):
>
> def comb(items, n):
> if n==0: yield []
> else:
> for i in xrange(len(items)):
> for cc in comb(items[i+1:],n-1):
> yield [items[i]]+cc
>
> This gives the hands one at a time using generators. This means that I
> can iterate over the hands like so:
>
> for hand in comb(deck, 5):
> ...
>
> where deck is a list of the 52 cards (minus the starting hands).
>
> I'm sure I can do this in Lisp in much the same way, but I'm not sure
> how. Lisp code hurts my head, but I'm counting on it to stop :)
>
> --
> Frode, SIM
>
> "Any fool can write code that a computer can understand.
> Good programmers write code that humans can understand"
With Lisp, you might see a slight speedup, but I think that your goal
is just inherently time consuming. Consider your example - for a deck
with 52 cards, enumerating all hands of 5 will take 52 x 51 x 50 x 49
x 48 = 311875200 operations. The fact that Psyco made no difference
makes me think the problem is just the complexity of counting all
these hands.
Here is a naive translation to Common Lisp, to get you started:
(defun comb (items n)
(declare (optimize (speed 3) (safety 0) (debug 0)))
(declare (fixnum n))
(if (zerop n)
'()
(loop for remaining on items by #'cdr
collecting (loop for cc in (comb remaining (1- n))
collecting (+ (car remaining) cc)))))
If you install the ITERATE package, you might be able to improve
performance by declaring cc to fit inside a machine word:
(defun comb (items n)
(declare (optimize (speed 3) (safety 0) (debug 0)))
(declare (fixnum n))
(if (zerop n)
'()
(iter (for remaining on items by #'cdr)
(collecting (iter (for cc in (comb remaining (1- n)))
(declare (fixnum cc))
(collecting (+ (car remaining) cc)))))))
(This code may not be completely correct - I just translated your
Python blindly.)
- Bill
Bill Atkins <············@rpi.edu> wrote:
> With Lisp, you might see a slight speedup, but I think that your goal
> is just inherently time consuming. Consider your example - for a deck
> with 52 cards, enumerating all hands of 5 will take 52 x 51 x 50 x 49
> x 48 = 311875200 operations. The fact that Psyco made no difference
> makes me think the problem is just the complexity of counting all
> these hands.
You are correct. I haven't delved into the specific code here, but I've
read some folks describing the attack on this very problem.
There's a lot of cominatorial explosion. The way to do this fast is
either to sample (and get an approximate result), or to do a lot of
memoizing. Essentially precalculate a bunch of information and store it
in tables that you can reference rather than calculate.
I think there's some description on the pokerstove website.
Alternately, if the information is the prime motivator here, one could
just download pokerstove -- it's free. It is, alas, written in C++ (or
maybe C), not lisp.
Michael
Michael Sullivan wrote:
> There's a lot of cominatorial explosion. The way to do this fast is
> either to sample (and get an approximate result), or to do a lot of
> memoizing. Essentially precalculate a bunch of information and store it
> in tables that you can reference rather than calculate.
As others have mentioned, changing your algorithm is likely to have a
bigger impact than changing the underlying language.
For example, one way to deal with the combinatorical explosion of
enumerating all the possible hands is to NOT enumerate all possible
hands. Instead take a statistical sampling.
I wrote a python program a few years back that did just that. It went
something like this:
for (i = 0; i < max_hands; ++i) {
[1] generate a random deck
[2] deal <n> hands from said deck.
[3] note the rank of all hands in histogram_a
[4] note the rank of the winning hand in histogram_b
}
It is important to have a good random number generator for this but I
believe Python uses a very good one.
For my program I was particularly interested in seeing how the presense
of <w> wild cards in the deck affected the average winning hand and
containing <c> cards so my program would iterate over
* a range of players dealt in the hand (e.g. 2-7)
* the number of cards dealt to each player (e.g. 5-7 -- representing
different variants)
* the number of wild cards in the deck
* the number of hands to deal for each permutation of the above
variables.
My program would then print out a histogram of the rank of hands dealt
along with odds of each ranked hand winning.
By sampling the space of poker hands statistically you can time how
long it takes to process a small sample (e.g. 50,000 hands dealt) and
then chose an appropriate number of iterations for a longer run.
"funkyj" <······@gmail.com> writes:
> Michael Sullivan wrote:
>
> > There's a lot of cominatorial explosion. The way to do this fast is
> > either to sample (and get an approximate result), or to do a lot of
> > memoizing. Essentially precalculate a bunch of information and store it
> > in tables that you can reference rather than calculate.
>
> As others have mentioned, changing your algorithm is likely to have a
> bigger impact than changing the underlying language.
>
> For example, one way to deal with the combinatorical explosion of
> enumerating all the possible hands is to NOT enumerate all possible
> hands. Instead take a statistical sampling.
I don't think that the combinatorics is all that difficult.
Four of a kind: There are thirteen possible kinds. This
consumes four cards leaving 52 - 4 = 48 choices for the
fifth card so 13 x 48 = 624
Full house: There are thirteen choices for the value of the
group of three, which leaves twelve choices for the value of
the group of two. 13 x 12 so far. But the group of 13 is
leaving out 1 card, which can be done in four ways, and the
group of two is leaving out 2 cards which can be done in
4x3/2=6 ways.
So it is 13 x 4 x 12 x 6 = 3744
Three of a kind: There are basically thirteen ways of
chosing the value of the group of three, then we have to
multiply by the four possible choices of which suit is left
out. 52 so far. That accounts for four of the possible 52
cards, 3 in, 1 out. So there are 48 choices for card number
4. It is not a full house, so that choice of one more card
knocks the other 3 of the same value out of the picture -
there are only 44 choices for the last card. Also the order
of the two unpaired cards doesn't matter so we have to
divide by two
13 x 4 x 48 x 44 / 2 = 54912
Two pair: 13 choices for the value of the first pair times
twelve choices for the value of the second pair, divided by
two because we don't care about order. But we do care about
the two-from-four choice of the suits in the pairs, so we
have 6 choices for each pair - 13 x 6 x 12 x 6 / 2 with one
card still to chose. It cannot be the same value as either
pair so our choice of the first four excludes 8, pick one of
the remaining 44
13 x 6 x 12 x 6 x 44 / 2 = 123552
Pair: 13 choices for the value of the pair times 6 choices
of 2 suits from four. Three cards still to go. Obviously 4
cards are excluded by chosing two for the pair and saying
that it is only a pair. So is it 48 x 47 x 46? No. Since it
is only a pair, each choice of another card eliminates the
other three of the same value, so it is 48 x 44 x 40 / 6.
Division by 3! = 6 because we don't care about order.
13 x 6 x 48 x 44 x 40 / 6 = 1098240
I'm not much of a mathematician, and could not do this
accurately from cold, but with the answers from brute force
calculation in front of me, it is not to difficult to catch
errors in the combinatorics and end up with the two
calculations agreeing.
Alan Crowe
Edinburgh, where John Knox is turning in his grave at all
this profane talk of gambling :-)
If I do this, I'll follow the maths like the following (read Alan).
Walking through all combination is just time consuming. For Alan's
implementation, I got:
CARD[26]> (time (count-cases 5 52))
Real time: 100.36259 sec.
Run time: 97.1875 sec.
Space: 425582356 Bytes
GC: 812, GC time: 2.59375 sec.
1098240 ;
123552 ;
54912 ;
3744 ;
624
using Clisp for windows 2000, Intel Celeron 1.7GHz.
BTW, thanks you all. This is a very good group (a lot of nice Lispers).
Alan Crowe schrieb:
> "funkyj" <······@gmail.com> writes:
>
> > Michael Sullivan wrote:
> >
> > > There's a lot of cominatorial explosion. The way to do this fast is
> > > either to sample (and get an approximate result), or to do a lot of
> > > memoizing. Essentially precalculate a bunch of information and store it
> > > in tables that you can reference rather than calculate.
> >
> > As others have mentioned, changing your algorithm is likely to have a
> > bigger impact than changing the underlying language.
> >
> > For example, one way to deal with the combinatorical explosion of
> > enumerating all the possible hands is to NOT enumerate all possible
> > hands. Instead take a statistical sampling.
>
> I don't think that the combinatorics is all that difficult.
>
> Four of a kind: There are thirteen possible kinds. This
> consumes four cards leaving 52 - 4 = 48 choices for the
> fifth card so 13 x 48 = 624
>
> Full house: There are thirteen choices for the value of the
> group of three, which leaves twelve choices for the value of
> the group of two. 13 x 12 so far. But the group of 13 is
> leaving out 1 card, which can be done in four ways, and the
> group of two is leaving out 2 cards which can be done in
> 4x3/2=6 ways.
>
> So it is 13 x 4 x 12 x 6 = 3744
>
> Three of a kind: There are basically thirteen ways of
> chosing the value of the group of three, then we have to
> multiply by the four possible choices of which suit is left
> out. 52 so far. That accounts for four of the possible 52
> cards, 3 in, 1 out. So there are 48 choices for card number
> 4. It is not a full house, so that choice of one more card
> knocks the other 3 of the same value out of the picture -
> there are only 44 choices for the last card. Also the order
> of the two unpaired cards doesn't matter so we have to
> divide by two
>
> 13 x 4 x 48 x 44 / 2 = 54912
>
> Two pair: 13 choices for the value of the first pair times
> twelve choices for the value of the second pair, divided by
> two because we don't care about order. But we do care about
> the two-from-four choice of the suits in the pairs, so we
> have 6 choices for each pair - 13 x 6 x 12 x 6 / 2 with one
> card still to chose. It cannot be the same value as either
> pair so our choice of the first four excludes 8, pick one of
> the remaining 44
>
> 13 x 6 x 12 x 6 x 44 / 2 = 123552
>
> Pair: 13 choices for the value of the pair times 6 choices
> of 2 suits from four. Three cards still to go. Obviously 4
> cards are excluded by chosing two for the pair and saying
> that it is only a pair. So is it 48 x 47 x 46? No. Since it
> is only a pair, each choice of another card eliminates the
> other three of the same value, so it is 48 x 44 x 40 / 6.
> Division by 3! = 6 because we don't care about order.
>
> 13 x 6 x 48 x 44 x 40 / 6 = 1098240
>
> I'm not much of a mathematician, and could not do this
> accurately from cold, but with the answers from brute force
> calculation in front of me, it is not to difficult to catch
> errors in the combinatorics and end up with the two
> calculations agreeing.
>
> Alan Crowe
> Edinburgh, where John Knox is turning in his grave at all
> this profane talk of gambling :-)
From: Frode Øijord
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <440C28E6.5020104@sim.no>
keyboard wrote:
> If I do this, I'll follow the maths like the following (read Alan).
> Walking through all combination is just time consuming. For Alan's
> implementation, I got:
>
> CARD[26]> (time (count-cases 5 52))
>
> Real time: 100.36259 sec.
> Run time: 97.1875 sec.
> Space: 425582356 Bytes
> GC: 812, GC time: 2.59375 sec.
> 1098240 ;
> 123552 ;
> 54912 ;
> 3744 ;
> 624
>
> using Clisp for windows 2000, Intel Celeron 1.7GHz.
I got comparable results on an Athlon 64 (1.79 GHz) with cygwin clisp. >
> BTW, thanks you all. This is a very good group (a lot of nice Lispers).
I second that, the quality and quantity of the response here have been
way better than I hoped. (It was my first post at comp.lang.lisp). I now
have alot of nice Lisp code to look into, and a flying start in getting
to know Lisp better. However, I cannot find any free Lisp implementation
that comes with a native-code compiler on windows, which is sort of a
(negative) surprise.
I guess I'll have to look into Scheme, since there seems to be a couple
of Scheme compilers out there that generates portable C-code. It's not
really what I want, but it will probably do the job...
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
From: Russell McManus
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <87wtf78y5g.fsf@cl-user.org>
Frode �ijord <·····@sim.no> writes:
> I second that, the quality and quantity of the response here have
> been way better than I hoped. (It was my first post at
> comp.lang.lisp). I now have alot of nice Lisp code to look into, and
> a flying start in getting to know Lisp better. However, I cannot
> find any free Lisp implementation that comes with a native-code
> compiler on windows, which is sort of a (negative) surprise.
I think ECL will work.
sbcl has an early port for windows, too.
-russ
Frode �ijord wrote:
> However, I cannot find any free Lisp implementation
> that comes with a native-code compiler on windows, which is sort of a
> (negative) surprise.
What do you mean with "native-code compiler"? I'm not sure, but I think
CLISP uses some kind of byte-code, but you can use
http://ecls.sourceforge.net/
If you mean that you can't create standalone executables, see
http://clisp.cons.org/impnotes/image.html and use :EXECUTABLE t.
If you want to create standalone applications without a console, try this
patch: http://www.frank-buss.de/lisp/clab/trunk/clisp/index.html
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: =?UTF-8?B?RnJvZGUgw5hpam9yZA==?=
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <440864CF.40109@sim.no>
Bill Atkins wrote:
> With Lisp, you might see a slight speedup, but I think that your goal
> is just inherently time consuming. Consider your example - for a deck
> with 52 cards, enumerating all hands of 5 will take 52 x 51 x 50 x 49
> x 48 = 311875200 operations. The fact that Psyco made no difference
> makes me think the problem is just the complexity of counting all
> these hands.
Actually, there are just 2,598,960 possible 5 card combinations since
the order of the cards does not matter. I tried to speed up the code by
installing a Python C extension that had a comb() function, and that
lowered the execution time from 30 seconds in pure Python to under a
second. Pure C would be much faster still. I'm hoping that a Lisp
version will be close to C speed, once it is compiled.
>
> Here is a naive translation to Common Lisp, to get you started:
>
> (defun comb (items n)
> (declare (optimize (speed 3) (safety 0) (debug 0)))
> (declare (fixnum n))
> (if (zerop n)
> '()
> (loop for remaining on items by #'cdr
> collecting (loop for cc in (comb remaining (1- n))
> collecting (+ (car remaining) cc)))))
>
> (This code may not be completely correct - I just translated your
> Python blindly.)
It did not run in clisp, but that does not really matter. It
demonstrates what is appealing about Lisp; first write the function as
simply as possible, then throw in some declarations to make it faster.
Then compile it to machine code. It also looks exactly like the Python
version, which is what I hoped for. I'm betting that the rest of my
Python code will be just as short and sweet in Lisp, only orders of
magnitude faster. Does this sound too optimistic?
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
From: Bill Atkins
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <87psl38per.fsf@rpi.edu>
Frode Øijord <·····@sim.no> writes:
> Bill Atkins wrote:
>
>> With Lisp, you might see a slight speedup, but I think that your goal
>> is just inherently time consuming. Consider your example - for a deck
>> with 52 cards, enumerating all hands of 5 will take 52 x 51 x 50 x 49
>> x 48 = 311875200 operations. The fact that Psyco made no difference
>> makes me think the problem is just the complexity of counting all
>> these hands.
>
> Actually, there are just 2,598,960 possible 5 card combinations since
> the order of the cards does not matter. I tried to speed up the code
Well, that may be, but your code is counting permutations, that is,
the number of ways to pick five cards where the order _does_ matter.
You can simply walk through the code's execution to see that this is
the case: The first deals with 52 cards. It iterates through all of
these cards, and for each one calls itself on 51 cards. Then each of
these individual calls makes 50 more recursive calls. The final tree
of calls is five levels deep, with the number of nodes I cited,
i.e. 311875200.
Counting combinations instead, if that's all you require, will improve
your performance much more than changing languages, and that
performance will be significantly better even for hands with more than
five cards.
> by installing a Python C extension that had a comb() function, and
> that lowered the execution time from 30 seconds in pure Python to
> under a second. Pure C would be much faster still. I'm hoping that a
> Lisp version will be close to C speed, once it is compiled.
>
>> Here is a naive translation to Common Lisp, to get you started:
>> (defun comb (items n)
>> (declare (optimize (speed 3) (safety 0) (debug 0)))
>> (declare (fixnum n))
>> (if (zerop n)
>> '()
>> (loop for remaining on items by #'cdr
>> collecting (loop for cc in (comb remaining (1- n))
>> collecting (+ (car remaining) cc)))))
>> (This code may not be completely correct - I just translated your
>> Python blindly.)
>
> It did not run in clisp, but that does not really matter. It
Ah, my this-may-be-staggeringly-incorrect disclaimer paid off. :)
> demonstrates what is appealing about Lisp; first write the function as
> simply as possible, then throw in some declarations to make it
> faster. Then compile it to machine code. It also looks exactly like
> the Python version, which is what I hoped for. I'm betting that the
> rest of my Python code will be just as short and sweet in Lisp, only
> orders of magnitude faster. Does this sound too optimistic?
I couldn't say for sure. I say search for combinations instead and
then decide what you need to do from there.
> --
> Frode, SIM
>
> "Any fool can write code that a computer can understand.
> Good programmers write code that humans can understand"
- Bill
No, the order doesn't matter. In the outer loop, choose the i-th card
out of 52. The next loop is over items[i+1:], which is not 51 cards,
but 51-i cards.
Here's another way to say it. The original poster's routine keeps each
hand sorted in the same order as the initial deck. There is no way to
get one of the 5! permutations of a given hand except the permutation
that's in sorted order. The Lisp code does the same because
'remaining' is shrinking by cdr at each step.
I'd also say that switching to a compiled language, any compiled
language, is very important.
From: Alexander Schmolck
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <yfs4q2fh39p.fsf@oc.ex.ac.uk>
Frode �ijord <·····@sim.no> writes:
> > Here is a naive translation to Common Lisp, to get you started:
>
> > (defun comb (items n)
>
> > (declare (optimize (speed 3) (safety 0) (debug 0)))
> > (declare (fixnum n))
> > (if (zerop n)
> > '()
> > (loop for remaining on items by #'cdr
> > collecting (loop for cc in (comb remaining (1- n))
> > collecting (+ (car remaining) cc)))))
> > (This code may not be completely correct - I just translated your
>
> > Python blindly.)
>
> It did not run in clisp, but that does not really matter.
I think it should be (comb (CDR remaining) ...)
> It demonstrates what is appealing about Lisp; first write the function as
> simply as possible, then throw in some declarations to make it faster. Then
> compile it to machine code. It also looks exactly like the Python version,
> which is what I hoped for.
Yeah -- but it behaves like
def comb2(items, n): return list(comb(items,n))
> I'm betting that the rest of my Python code will be just as short and sweet
> in Lisp, only orders of magnitude faster. Does this sound too optimistic?
If you expect that to happen in general then you're certainly too optimistic.
Python is more expressive in some things: it's much easier to write lazily
evaluated code or to iterate over something without knowing what it is in
python than it is in lisp -- so I don't think you can expect *everything* to
be as short and sweet in lisp as in python.
Also, for many tasks you can use highly optimized python builtins or extension
libraries (e.g. scipy) and then there's stuff like, psyco, boost, weave etc.
that can give rather good performance for certain narrowly circumscribed
tasks.
On the other hand, if you're exploring territory that is not well served by
any of the above common lisp will offer you superior compiler technology and
possibly better support for building your own sophisticated optimization
abstractions than any other language.
You could also try a fast scheme implementation like stalin or gambit -- for
the task you have in mind limited availablity of libraries etc. doesn't seem
to be such a huge issue.
'as
Bill Atkins wrote:
> Here is a naive translation to Common Lisp, to get you started:
>
> (defun comb (items n)
> (declare (optimize (speed 3) (safety 0) (debug 0)))
> (declare (fixnum n))
> (if (zerop n)
> '()
> (loop for remaining on items by #'cdr
> collecting (loop for cc in (comb remaining (1- n))
> collecting (+ (car remaining) cc)))))
This is not a translation of the Python code, because the Python code
doesn't generate the whole list, but provides a "generator". I think for a
full implementation of this concept, first we need a macro for call/cc or
Scheme. If "comb" returns a function, which returns the next hand on every
call and NIL if there are no more hands, a counting function for hands with
aces could be written like this:
(defmacro for-generator (item generator-constructor &body body)
(let ((generator (gensym)))
`(loop with ,generator = ,generator-constructor do
(let ((,item (funcall ,generator)))
(if ,item
(progn ,@body)
(loop-finish))))))
(defun mix (list1 list2)
(loop for i in list1 append
(loop for j in list2 collect (cons i j))))
(defun test ()
(let ((deck (make-array
52
:initial-contents (mix '(2 3 4 5 6 7 8 9 10 j q k a)
'(s h d c))))
(count 0)
(ace2 0)
(ace3 0)
(ace4 0))
(for-generator hand (comb deck 5)
(incf count)
(let ((ace-count 0))
(loop for card across hand do
(when (eql 'a (car card))
(incf ace-count)))
(when (= 2 ace-count) (incf ace2))
(when (= 3 ace-count) (incf ace3))
(when (= 4 ace-count) (incf ace4))))
(format t "number of hands: ~a~%aa: ~a%~%aaa: ~a%~%aaaa: ~a%"
count
(/ (* 100.0 ace2) count)
(/ (* 100.0 ace3) count)
(/ (* 100.0 ace4) count))))
Below is a first version of the comb function. I tried to implement it
fast, but it looks a bit ugly, any idea how to improve it without call/cc?
(defun comb (items n)
(labels ((inc-counter (counter
limit
&optional (pos (1- (length counter))))
(let ((digit (1+ (aref counter pos))))
(if (= digit limit)
(unless (zerop pos)
(let ((left-digit (inc-counter
counter
(1- limit)
(1- pos))))
(when left-digit
(setf (aref counter pos) (1+ left-digit)))))
(setf (aref counter pos) digit)))))
(let ((counter (make-array
n
:initial-contents (loop for i from 0 below n collect i)))
(selected-items (make-array n)))
(lambda ()
(when counter
(loop for i from 0 below n do
(setf (aref selected-items i)
(aref items (aref counter i))))
(unless (inc-counter counter (length items))
(setf counter nil))
selected-items)))))
(time (test))
Timing the evaluation of (TEST)
number of hands: 2598960
aa: 3.9929818081078587%
aaa: 0.17360790470034168%
aaaa: 0.0018468926031951242%
user time = 5.578
system time = 0.000
Elapsed time = 0:00:06
Allocation = 11728 bytes standard / 7513 bytes conses
0 Page faults
Calls to %EVAL 33
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
On Fri, 03 Mar 2006 17:27:27 +0100, Frank Buss wrote:
> This is not a translation of the Python code, because the Python code
> doesn't generate the whole list, but provides a "generator".
I have not used python generators, but isn't this generator facility:
http://series.sourceforge.net/ (well, series that can be turned
into generators) described in appendix A and B of CLtL?*
Matt
*Perhaps they are not equivalent concepts.
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
From: Alexander Schmolck
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <yfsveuvfjof.fsf@oc.ex.ac.uk>
Matthew D Swank <·······································@c.net> writes:
> On Fri, 03 Mar 2006 17:27:27 +0100, Frank Buss wrote:
>
> > This is not a translation of the Python code, because the Python code
> > doesn't generate the whole list, but provides a "generator".
>
> I have not used python generators, but isn't this generator facility:
> http://series.sourceforge.net/ (well, series that can be turned
> into generators) described in appendix A and B of CLtL?*
IIRC you can only create a (cltl appendix b) generator from a series, but
series are essentially written in a limited and somewhat obscure special
purpose language. On the other hand if you're prepared to invest a not
insignificant learning effort you can write pretty elegant series expression
that can still be compiled into very efficient code (but only for a limited
domain -- not everything that's easy with python/icon style generators can be
expressed well in series).
By contrast generators in python just look and work like functions, except
that instead of "return foo" you write "yield foo" to return foo and suspend
execution and you can also call generators at any point where you could call a
function, including of course from within a generator.
From a usability point of view python's generators (and handling of iteration
and container types in general) wins hands-down IMO, but it's sort of
difficult to see how to get optimal efficiency with that approach.
One thing that isn't handled by python, but is by series (and IIRC iterate,
for a few hard-coded cases even by loop) is accumulation. But in general
writing a reduction operation such as sum or list-collection out explicitly
for each loop is IMO far less of a hassle than not being able to use
generators, coroutines or a general iteration protocol.
Still, I'm really puzzled by the fact that I've never seen a complete
iteration facility for any language -- at least if efficiency is not a primary
concern it doesn't seem that hard (especially not in scheme).
'as
From: Bill Atkins
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <87bqwn8owj.fsf@rpi.edu>
Frank Buss <··@frank-buss.de> writes:
> Bill Atkins wrote:
>
>> Here is a naive translation to Common Lisp, to get you started:
>>
>> (defun comb (items n)
>> (declare (optimize (speed 3) (safety 0) (debug 0)))
>> (declare (fixnum n))
>> (if (zerop n)
>> '()
>> (loop for remaining on items by #'cdr
>> collecting (loop for cc in (comb remaining (1- n))
>> collecting (+ (car remaining) cc)))))
>
> This is not a translation of the Python code, because the Python code
> doesn't generate the whole list, but provides a "generator". I think for a
Good point.
> full implementation of this concept, first we need a macro for call/cc or
> Scheme. If "comb" returns a function, which returns the next hand on every
> call and NIL if there are no more hands, a counting function for hands with
> aces could be written like this:
>
>
> (defmacro for-generator (item generator-constructor &body body)
> (let ((generator (gensym)))
> `(loop with ,generator = ,generator-constructor do
> (let ((,item (funcall ,generator)))
> (if ,item
> (progn ,@body)
> (loop-finish))))))
>
> (defun mix (list1 list2)
> (loop for i in list1 append
> (loop for j in list2 collect (cons i j))))
>
> (defun test ()
> (let ((deck (make-array
> 52
> :initial-contents (mix '(2 3 4 5 6 7 8 9 10 j q k a)
> '(s h d c))))
> (count 0)
> (ace2 0)
> (ace3 0)
> (ace4 0))
> (for-generator hand (comb deck 5)
> (incf count)
> (let ((ace-count 0))
> (loop for card across hand do
> (when (eql 'a (car card))
> (incf ace-count)))
> (when (= 2 ace-count) (incf ace2))
> (when (= 3 ace-count) (incf ace3))
> (when (= 4 ace-count) (incf ace4))))
> (format t "number of hands: ~a~%aa: ~a%~%aaa: ~a%~%aaaa: ~a%"
> count
> (/ (* 100.0 ace2) count)
> (/ (* 100.0 ace3) count)
> (/ (* 100.0 ace4) count))))
>
>
> Below is a first version of the comb function. I tried to implement it
> fast, but it looks a bit ugly, any idea how to improve it without call/cc?
>
>
> (defun comb (items n)
> (labels ((inc-counter (counter
> limit
> &optional (pos (1- (length counter))))
> (let ((digit (1+ (aref counter pos))))
> (if (= digit limit)
> (unless (zerop pos)
> (let ((left-digit (inc-counter
> counter
> (1- limit)
> (1- pos))))
> (when left-digit
> (setf (aref counter pos) (1+ left-digit)))))
> (setf (aref counter pos) digit)))))
> (let ((counter (make-array
> n
> :initial-contents (loop for i from 0 below n collect i)))
> (selected-items (make-array n)))
> (lambda ()
> (when counter
> (loop for i from 0 below n do
> (setf (aref selected-items i)
> (aref items (aref counter i))))
> (unless (inc-counter counter (length items))
> (setf counter nil))
> selected-items)))))
>
>
> (time (test))
> Timing the evaluation of (TEST)
>
> number of hands: 2598960
> aa: 3.9929818081078587%
> aaa: 0.17360790470034168%
> aaaa: 0.0018468926031951242%
>
> user time = 5.578
> system time = 0.000
> Elapsed time = 0:00:06
> Allocation = 11728 bytes standard / 7513 bytes conses
> 0 Page faults
> Calls to %EVAL 33
>
> --
> Frank Buss, ··@frank-buss.de
> http://www.frank-buss.de, http://www.it4-systems.de
You could probably use closures to avoid call/cc. Here's an example
of how something like this might be done:
(defun card-generator ()
(let ((cards 52))
#'(lambda () (decf cards))))
(let ((gen (card-generator)))
(loop for x = (funcall gen)
while (> x 0)
do (princ x)))
- Bill
From: Bill Atkins
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <8764mv8oss.fsf@rpi.edu>
Bill Atkins <············@rpi.edu> writes:
> Frank Buss <··@frank-buss.de> writes:
>
>> Bill Atkins wrote:
>>
>>> Here is a naive translation to Common Lisp, to get you started:
>>>
>>> (defun comb (items n)
>>> (declare (optimize (speed 3) (safety 0) (debug 0)))
>>> (declare (fixnum n))
>>> (if (zerop n)
>>> '()
>>> (loop for remaining on items by #'cdr
>>> collecting (loop for cc in (comb remaining (1- n))
>>> collecting (+ (car remaining) cc)))))
>>
>> This is not a translation of the Python code, because the Python code
>> doesn't generate the whole list, but provides a "generator". I think for a
>
> Good point.
>
>> full implementation of this concept, first we need a macro for call/cc or
>> Scheme. If "comb" returns a function, which returns the next hand on every
>> call and NIL if there are no more hands, a counting function for hands with
>> aces could be written like this:
>>
>>
>> (defmacro for-generator (item generator-constructor &body body)
>> (let ((generator (gensym)))
>> `(loop with ,generator = ,generator-constructor do
>> (let ((,item (funcall ,generator)))
>> (if ,item
>> (progn ,@body)
>> (loop-finish))))))
>>
>> (defun mix (list1 list2)
>> (loop for i in list1 append
>> (loop for j in list2 collect (cons i j))))
>>
>> (defun test ()
>> (let ((deck (make-array
>> 52
>> :initial-contents (mix '(2 3 4 5 6 7 8 9 10 j q k a)
>> '(s h d c))))
>> (count 0)
>> (ace2 0)
>> (ace3 0)
>> (ace4 0))
>> (for-generator hand (comb deck 5)
>> (incf count)
>> (let ((ace-count 0))
>> (loop for card across hand do
>> (when (eql 'a (car card))
>> (incf ace-count)))
>> (when (= 2 ace-count) (incf ace2))
>> (when (= 3 ace-count) (incf ace3))
>> (when (= 4 ace-count) (incf ace4))))
>> (format t "number of hands: ~a~%aa: ~a%~%aaa: ~a%~%aaaa: ~a%"
>> count
>> (/ (* 100.0 ace2) count)
>> (/ (* 100.0 ace3) count)
>> (/ (* 100.0 ace4) count))))
>>
>>
>> Below is a first version of the comb function. I tried to implement it
>> fast, but it looks a bit ugly, any idea how to improve it without call/cc?
>>
>>
>> (defun comb (items n)
>> (labels ((inc-counter (counter
>> limit
>> &optional (pos (1- (length counter))))
>> (let ((digit (1+ (aref counter pos))))
>> (if (= digit limit)
>> (unless (zerop pos)
>> (let ((left-digit (inc-counter
>> counter
>> (1- limit)
>> (1- pos))))
>> (when left-digit
>> (setf (aref counter pos) (1+ left-digit)))))
>> (setf (aref counter pos) digit)))))
>> (let ((counter (make-array
>> n
>> :initial-contents (loop for i from 0 below n collect i)))
>> (selected-items (make-array n)))
>> (lambda ()
>> (when counter
>> (loop for i from 0 below n do
>> (setf (aref selected-items i)
>> (aref items (aref counter i))))
>> (unless (inc-counter counter (length items))
>> (setf counter nil))
>> selected-items)))))
>>
>>
>> (time (test))
>> Timing the evaluation of (TEST)
>>
>> number of hands: 2598960
>> aa: 3.9929818081078587%
>> aaa: 0.17360790470034168%
>> aaaa: 0.0018468926031951242%
>>
>> user time = 5.578
>> system time = 0.000
>> Elapsed time = 0:00:06
>> Allocation = 11728 bytes standard / 7513 bytes conses
>> 0 Page faults
>> Calls to %EVAL 33
>>
>> --
>> Frank Buss, ··@frank-buss.de
>> http://www.frank-buss.de, http://www.it4-systems.de
>
> You could probably use closures to avoid call/cc. Here's an example
> of how something like this might be done:
>
> (defun card-generator ()
> (let ((cards 52))
> #'(lambda () (decf cards))))
>
> (let ((gen (card-generator)))
> (loop for x = (funcall gen)
> while (> x 0)
> do (princ x)))
>
> - Bill
I should point out that I've never used generators before, so I've
missed the spirit of them entirely, then I apologize.
- Bill
On Fri, 03 Mar 2006 11:38:04 -0500, Bill Atkins wrote:
> You could probably use closures to avoid call/cc. Here's an example
> of how something like this might be done:
>
> (defun card-generator ()
> (let ((cards 52))
> #'(lambda () (decf cards))))
>
> (let ((gen (card-generator)))
> (loop for x = (funcall gen)
> while (> x 0)
> do (princ x)))
Which brings us around to the ruby use of yield which basically
dyanamically binds a block in the context of a function; a simple lisp
version:
(defvar *yield-body* (constantly nil))
(defun yield (&rest args)
(apply *yield-body* args))
(defmacro with-yield (yield-fun &body body)
`(let ((*yield-body* ,yield-fun))
,@body))
;;;silly example, but in keeping with the post
(defun my-counter ()
(dotimes (x 52) (yield (1+ x))))
(with-yield #'(lambda (x) (princ x))
(my-counter))
I haven't explored it much, but it looks like if one were to turn the
python generator "inside out", the generators could be replaced with code
similar to the above.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
On Sun, 05 Mar 2006 00:33:15 -0600, Matthew D Swank wrote:
> (defun my-counter ()
> (dotimes (x 52) (yield (1+ x))))
>
> (with-yield #'(lambda (x) (princ x))
> (my-counter))
>
> I haven't explored it much, but it looks like if one were to turn the
> python generator "inside out", the generators could be replaced with code
> similar to the above.
Though considering the kind of state generators need to track, an
implementation using simple closures or ruby style yields would have to do
its own stack bookkeeping.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
From: Frode Øijord
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <44087763.10409@sim.no>
Frank Buss wrote:
---8<-- [snip] --------8<-- [snip] --------8<-- [snip] -----
>I think for a
> full implementation of this concept, first we need a macro for call/cc or
> Scheme. If "comb" returns a function, which returns the next hand on every
> call and NIL if there are no more hands, a counting function for hands with
> aces could be written like this:
>
> number of hands: 2598960
> aa: 3.9929818081078587%
> aaa: 0.17360790470034168%
> aaaa: 0.0018468926031951242%
>
> user time = 5.578
> system time = 0.000
> Elapsed time = 0:00:06
> Allocation = 11728 bytes standard / 7513 bytes conses
> 0 Page faults
> Calls to %EVAL 33
>
---8<-- [snip] --------8<-- [snip] --------8<-- [snip] -----
This looks quite promising. I ran your code on my Athlon 64 2800 (1.79
GHz), and this is the results I got:
number of hands: 2598960
aa: 3.992982%
aaa: 0.1736079%
aaaa: 0.0018468926%
Real time: 13.569 sec.
Run time: 13.406 sec.
Space: 3844 Bytes
I compiled the code first (in cygwin) using
clisp -c -l test.cl -o test
I guess this produces some kind of byte-code?
What kind of hardware and Lisp implementation do you use? The execution
time on your system seems to be quite good :)
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
Frode �ijord wrote:
> What kind of hardware and Lisp implementation do you use? The execution
> time on your system seems to be quite good :)
I've tried it on my Pentium 4, 3 GHz with LispWorks.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <87ek1io53h.fsf@qrnik.zagroda>
Frank Buss <··@frank-buss.de> writes:
> This is not a translation of the Python code, because the Python
> code doesn't generate the whole list, but provides a "generator".
> I think for a full implementation of this concept, first we need a
> macro for call/cc or Scheme.
Python generators are not as powerful as call/cc: yields must be
contained in a single function. To delegate some work to another
function, it must return its own generator, which is then iterated
over from the first function to propagate its results.
The implementation of generators in CPython was very simple. Since a
stack frame is already heap-allocated, and the instruction pointer is
an explicit variable from the point of view of the C language hosting
the interpreter, it just needs to not free the stack frame when yielding,
and to store the instruction pointer somewhere, so it can be resumed.
C# has something very similar to Python. Its implementation was more
complicated because its target languages (the .NET bytecode or the
native code generated from them) don't allow to prolong the lifetime
of a stack frame. So it must generate code which keeps local variables
in a heap-allocated object instead of a stack frame, and which can be
resumed from any yield point.
In both languages yield points must be contained within one function,
so the transformation is local to that function. Other stack frames
can be allocated in the true stack way, there is no need to make the
control stack tree-shaped as with call/cc.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: Alexander Schmolck
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <yfsfylyfn0f.fsf@oc.ex.ac.uk>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> Frank Buss <··@frank-buss.de> writes:
>
> > This is not a translation of the Python code, because the Python
> > code doesn't generate the whole list, but provides a "generator".
> > I think for a full implementation of this concept, first we need a
> > macro for call/cc or Scheme.
>
> Python generators are not as powerful as call/cc
True, but is there an easier way to emulate generators in common lisp than
emulating call/cc?
'as
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <873bhyl5io.fsf@qrnik.zagroda>
Alexander Schmolck <··········@gmail.com> writes:
>> Python generators are not as powerful as call/cc
>
> True, but is there an easier way to emulate generators in common
> lisp than emulating call/cc?
Depends on how well do we want them to behave.
Making them work like in Python or C# would mean to analyze the outer
structure of the function, and implement differently all control
structures which would permit YIELD inside them. E.g. LET and DO
would be translated as setting object slots instead of creating local
variables, or as manipulating first-class variable objects bound
to object slots if the programmer makes use of the fact that each
iteration creates a new variable. Forms which can't be implemented
in a single emulated stack frame, e.g. LAMBDA, would not permit YIELD
inside them, unless the context which uses them can be fully analyzed
and reimplemented (YIELD inside LAMBDA inside MAPCAR could work if
MAPCAR got inlined such that it uses only the parent's stack frame).
I'm not saying that this would be a good idea. I couldn't adapt
Python/C# generators to my language because my control structures
heavily rely on higher order functions. It would be impractical if
YIELD was limited to certain contexts, and it would be painful to
reimplement even these contexts.
Instead I use more explicitly created lazy sequences, where yielding
is not expressed as a statement with a side effect. The code is
uglier, but the semantics is clear and there are no artificial
limitations of constructs used. Limitations are easily explainable
and the programmer can explicitly work around them.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Alexander Schmolck wrote:
> Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
>
> > Frank Buss <··@frank-buss.de> writes:
> >
> > > This is not a translation of the Python code, because the Python
> > > code doesn't generate the whole list, but provides a "generator".
> > > I think for a full implementation of this concept, first we need a
> > > macro for call/cc or Scheme.
> >
> > Python generators are not as powerful as call/cc
>
> True, but is there an easier way to emulate generators in common lisp than
> emulating call/cc?
Another option is to use a lazy list (also known as a `stream' in
Scheme):
(defun hands-stream (cards n)
(cond ((zerop n) (lazy-cons '() '()))
((null cards) '())
(t
(let ((first (car cards))
(rest (cdr cards)))
(lazy-list/append-delayed
(lazy-list/map (lambda (hand)
(cons first hand))
(hands-stream rest (- n 1)))
(delay (hands-stream rest n)))))))
(hands-stream *deck* 5)
=> #<LAZY-LIST (((:ACE . :DIAMONDS) (:ACE . :HEARTS) (:ACE . :CLUBS)
(:ACE . :SPADES) (2 . :DIAMONDS)) ...) 20608C7C>
(lazy-list/elt (hands-stream *deck* 5) 1234)
=> ((:ACE . :DIAMONDS) (:ACE . :HEARTS) (:ACE . :SPADES) (2 . :HEARTS)
(5 . :HEARTS))
Unfortunately, it isn't very fast:
(defvar *hs* (hands-stream *deck* 5))
(time (lazy-list/elt *hs* 654321))
Timing the evaluation of (LAZY-LIST/ELT *HS* 654321)
user time = 50.828
system time = 0.015
Elapsed time = 0:00:52
Allocation = 698248336 bytes standard / 122984510 bytes fixlen
0 Page faults
((:ACE . :CLUBS) (5 . :SPADES) (8 . :DIAMONDS) (:QUEEN . :DIAMONDS)
(:KING . :HEARTS))
But since it memoizes, it's much faster the second time:
(time (lazy-list/elt *hs* 654321))
Timing the evaluation of (LAZY-LIST/ELT *HS* 654321)
user time = 0.078
system time = 0.000
Elapsed time = 0:00:00
Allocation = 0 bytes standard / 0 bytes fixlen
0 Page faults
((:ACE . :CLUBS) (5 . :SPADES) (8 . :DIAMONDS) (:QUEEN . :DIAMONDS)
(:KING . :HEARTS))
Matthew D Swank wrote:
> On Mon, 06 Mar 2006 10:08:29 -0800, Joe Marshall wrote:
>
> >
> > Another option is to use a lazy list (also known as a `stream' in
> > Scheme):
>
> Is that your own lazy-list implementation?
Yes. I was thinking of posting it along with the other code, but it is
a bit large.
"Joe Marshall" <··········@gmail.com> writes:
> Matthew D Swank wrote:
> > On Mon, 06 Mar 2006 10:08:29 -0800, Joe Marshall wrote:
> >
> > >
> > > Another option is to use a lazy list (also known as a `stream' in
> > > Scheme):
> >
> > Is that your own lazy-list implementation?
>
> Yes. I was thinking of posting it along with the other code, but it is
> a bit large.
You could post it to the lisp sources list, if it is still alive.
Bj�rn
Bill Atkins <············@rpi.edu> wrote in ···················@rpi.edu:
> Frode Øijord <·····@sim.no> writes:
>
>> Hi,
>> I recently got the urge to calculate winning probabilities for Texas
>> Hold'em starting hands. I did not bother with some fancy statistical
>> methods (I don't know any), and brute force should be more than fast
>> enough on modern hardware.
>>
>> I've been programming C++ professionally for a couple of years, but I
>> did not want to use it in this little pet project. It was time to
give
>> a n interactive language a shot. I decided on Python since it's
>> extremely easy to get started with, once you know C++.
>>
>> Calculating the winning probabilities was easier than i thought, and
>> the clear syntax and expressive powers of Python made the code very
>> short and sweet. And slow. I feared that it would be slow, but I was
>> still surprised when it took around one minute to get the percentages
>> for two hands, all the way to the river.
>>
>> Now I'm facing a dilemma. I could factor out the time consuming parts
>> of the code to C++, but that would negate the purpose of choosing
>> Python in the first place. If only Python would come with a
>> compiler. I think it's time to give Lisp a shot. Lisp seems to have
it
>> all, at least that's what I have heard.
>>
>> Does any of you excellent sirs have a recommendation on what Lisp
>> implementation to choose? I need to compile the source to machine
code
>> for speed, and preferably so on windows. It would also be nice if the
>> Lisp came with some facility to load dll's and generate bindings for
>> the functions it exports, but this is perhaps too much to ask. Other
>> than that it should be free. I'll use the clisp that comes with
cygwin
>> for now, just to get things started.
>>
>> Just one more thing: This is how i generate all possible poker hands
>> in Python (or all possible n length combinations of any list of
>> ITEMS):
>>
>> def comb(items, n):
>> if n==0: yield []
>> else:
>> for i in xrange(len(items)):
>> for cc in comb(items[i+1:],n-1):
>> yield [items[i]]+cc
>>
>> This gives the hands one at a time using generators. This means that
I
>> can iterate over the hands like so:
>>
>> for hand in comb(deck, 5):
>> ...
>>
>> where deck is a list of the 52 cards (minus the starting hands).
>>
>> I'm sure I can do this in Lisp in much the same way, but I'm not sure
>> how. Lisp code hurts my head, but I'm counting on it to stop :)
>>
>> --
>> Frode, SIM
>>
>> "Any fool can write code that a computer can understand.
>> Good programmers write code that humans can understand"
>
> With Lisp, you might see a slight speedup, but I think that your goal
> is just inherently time consuming. Consider your example - for a deck
> with 52 cards, enumerating all hands of 5 will take 52 x 51 x 50 x 49
> x 48 = 311875200 operations. The fact that Psyco made no difference
> makes me think the problem is just the complexity of counting all
> these hands.
>
Actually, in looking at the Psyco website, the reason why Psyco didn't
speed things up much is that they don't optimize generators. I'd say
that if he rewrote the generator as an iterator class or just
accumulated the results in a list and returned that, that he would get
more of a speed-up from Psyco.
-- Eric
Frode �ijord wrote:
> Calculating the winning probabilities was easier than i thought, and the
> clear syntax and expressive powers of Python made the code very short
> and sweet. And slow.
I've never tried it myself, but you may like Psycho:
http://psyco.sourceforge.net/
Psyco is a Python extension module which can massively speed up the
execution of any Python code.
From: Frode Øijord
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <44084EC6.1070403@sim.no>
Mark Carter wrote:
> Frode �ijord wrote:
>
>> Calculating the winning probabilities was easier than i thought, and
>> the clear syntax and expressive powers of Python made the code very
>> short and sweet. And slow.
>
>
> I've never tried it myself, but you may like Psycho:
> http://psyco.sourceforge.net/
> Psyco is a Python extension module which can massively speed up the
> execution of any Python code.
Tried it without any significant speed-ups. Maybe I used it wrong or
something, but I don't think it would be enough anyway. I'm looking for
near C/C++ speed on this, so I would really like to try a Lisp that
could give me this...
--
Frode, SIM
"Any fool can write code that a computer can understand.
Good programmers write code that humans can understand"
You can write a routine that iterates over the possible hands:
(defun map-hands (f cards n)
(cond ((zerop n) (funcall f '()))
((null cards) '())
(t
(let ((first (car cards))
(rest (cdr cards)))
(map-hands
(lambda (hand)
(funcall f (cons first hand)))
rest
(- n 1))
(map-hands f rest n)))))
Then we can define a counting routine that counts how many hands match
a predicate:
(defun count-hands (list n pred)
(let ((count 0))
(map-hands (lambda (h)
(when (funcall pred h)
(incf count)))
list
n)
count))
Here is a deck:
(defvar *deck*
(mapcan (lambda (value)
(map 'list (lambda (suit)
(cons value suit))
'(:diamonds
:hearts
:clubs
:spades)))
'(:ace 2 3 4 5 6 7 8 9 10 :Jack :Queen :King)))
Count all the hands:
(count-hands *deck* 5 (constantly 't))
=> 2598960
(defun pair-or-better (hand)
(destructuring-bind (a b c d e) hand
(or (eql (car a) (car b))
(eql (car a) (car c))
(eql (car a) (car d))
(eql (car a) (car e))
(eql (car b) (car c))
(eql (car b) (car d))
(eql (car b) (car e))
(eql (car c) (car d))
(eql (car c) (car e))
(eql (car d) (car e)))))
(count-hands *deck* 5 #'pair-or-better)
=> 1281072
(count-hands *deck* 5 (complement #'pair-or-better))
=> 1317888
Joe Marshall wrote:
> (defun pair-or-better (hand)
> (destructuring-bind (a b c d e) hand
> (or (eql (car a) (car b))
> (eql (car a) (car c))
> (eql (car a) (car d))
> (eql (car a) (car e))
> (eql (car b) (car c))
> (eql (car b) (car d))
> (eql (car b) (car e))
> (eql (car c) (car d))
> (eql (car c) (car e))
> (eql (car d) (car e)))))
You could destructure deeper.
But then there is that pesky ignoring you have to do, since a dotted
list is not allowed to match a non-dotted pattern:
(defun pair-or-better (hand)
(destructuring-bind ((a . v) (b . w) (c . x) (d . y) (e . z)) hand
(declare-ignore (v w x y z))
(or (eql a b) (eql a c) ... (eql d e))))
From: Alexander Schmolck
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <yfsr75jfauo.fsf@oc.ex.ac.uk>
"Joe Marshall" <··········@gmail.com> writes:
> Here is a deck:
> (defvar *deck*
> (mapcan (lambda (value)
> (map 'list (lambda (suit)
Is there a specific reason you don't use mapcar?
> (cons value suit))
> '(:diamonds
> :hearts
> :clubs
> :spades)))
> '(:ace 2 3 4 5 6 7 8 9 10 :Jack :Queen :King)))
'as
Alexander Schmolck wrote:
> "Joe Marshall" <··········@gmail.com> writes:
>
> > Here is a deck:
> > (defvar *deck*
> > (mapcan (lambda (value)
> > (map 'list (lambda (suit)
>
> Is there a specific reason you don't use mapcar?
Nope.
From: Alexander Schmolck
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <yfsmzg7faed.fsf@oc.ex.ac.uk>
"Joe Marshall" <··········@gmail.com> writes:
> (defun pair-or-better (hand)
a more concise and much less efficient variant:
(< 5 (length (remove-duplicates hand :key #'car))))
> (destructuring-bind (a b c d e) hand
> (or (eql (car a) (car b))
> (eql (car a) (car c))
> (eql (car a) (car d))
> (eql (car a) (car e))
> (eql (car b) (car c))
> (eql (car b) (car d))
> (eql (car b) (car e))
> (eql (car c) (car d))
> (eql (car c) (car e))
> (eql (car d) (car e)))))
'as
Joe Marshall wrote:
> You can write a routine that iterates over the possible hands:
> (defun map-hands (f cards n)
> (cond ((zerop n) (funcall f '()))
> ((null cards) '())
> (t
> (let ((first (car cards))
> (rest (cdr cards)))
> (map-hands
> (lambda (hand)
> (funcall f (cons first hand)))
> rest
> (- n 1))
> (map-hands f rest n)))))
That's nice. Timing shows that it is as fast as my "optimized" vector
solution, so I tried the "un-optimized" straight forward solution (see
below), which is 5 times faster than my "optimized" version. And the usual
result: the best optimization tip is not to optimize :-)
(defun map-combinations (items n fun &optional (selected '()))
(if (zerop n)
(funcall fun selected)
(loop for (item . rest) on items do
(push item selected)
(map-combinations rest (1- n) fun selected)
(pop selected))))
(defun mix (list-1 list-2)
(loop for i in list-1 append
(loop for j in list-2 collect (cons i j))))
(defun count-hands ()
(let ((deck (mix '(2 3 4 5 6 7 8 9 10 :jack :queen :king :ace)
'(:diamonds :hearts :clubs :spades)))
(count 0)
(ace2 0)
(ace3 0)
(ace4 0))
(map-combinations deck 5
#'(lambda (hand)
(incf count)
(loop for card in hand
with ace-count = 0
finally (when (= 2 ace-count) (incf ace2))
(when (= 3 ace-count) (incf ace3))
(when (= 4 ace-count) (incf ace4))
do (when (eql :ace (car card))
(incf ace-count)))))
(format t "number of hands: ~a~%" count)
(format t "two aces: ~,4f%~%" (/ (* 100.0 ace2) count))
(format t "three aces: ~,4f%~%" (/ (* 100.0 ace3) count))
(format t "four aces: ~,4f%~%" (/ (* 100.0 ace4) count))))
(time (count-hands))
Timing the evaluation of (COUNT-HANDS)
number of hands: 2598960
two aces: 3.9930%
three aces: 0.1736%
four aces: 0.0018%
user time = 1.078
system time = 0.000
Elapsed time = 0:00:01
Allocation = 5304 bytes standard / 31833736 bytes conses
0 Page faults
Calls to %EVAL 33
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
It took me a while of reading the code to figure out how map-hands
worked.
I was curious to see how the technique of recursively using lamda to
accumulate a result performed compared to simply accumulating the
result in an extra parameter so I wrote the some code (see below) and
tested in on cygwin/clisp.
CL-USER> (test 60 5)
timing 'extra variable' method:
Real time: 3.575 sec.
Run time: 3.545 sec.
Space: 47882056 Bytes
GC: 65, GC time: 1.641 sec.
timing 'lamda accumulator' method:
Real time: 12.487 sec.
Run time: 12.327 sec.
Space: 259159668 Bytes
GC: 349, GC time: 8.62 sec.
As you can see, in CLISP using lamda to accumulate a result is about 3
times slower than using a extra variable. I'm curious how the
performance varies in other lisps.
--jfc
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;; test the performance of two different mechansism for accumulating
;;;; a partial result during recursion:
;;;; + using an extra parameter as an accumulator
;;;; + using lamda to accumulate the result.
(defun f1 (f lst n &optional acc)
"invoke 'f' on each possible 'lst choose m' elements"
(cond ((= n 0) (funcall f acc))
((null lst) nil)
(t
(let ((first (car lst))
(rest (cdr lst)))
(f1 f rest (- n 1) (cons first acc))
(f1 f rest n acc)))))
(defun f2 (f lst n)
(cond ((= n 0) (funcall f nil))
((null lst) nil)
(t
(let ((first (car lst))
(rest (cdr lst)))
(f2 (lambda (l) (cons first l)) rest (- n 1))
(f2 f rest n)))))
(defun show-me (x) (format t "~A~%" x))
(defun list-n (n) (loop for x to (- n 1) collect x))
(defun test (n m)
"time 'n choose m' with f1 and f2"
(format t "timing 'extra variable' method: ~%")
(time (f1 #'identity (list-n n) m))
(format t "~%~%timing 'lamda accumulator' method: ~%")
(time (f2 #'identity (list-n n) m)))
funkyj wrote:
> It took me a while of reading the code to figure out how map-hands
> worked.
>
> I was curious to see how the technique of recursively using lamda to
> accumulate a result performed compared to simply accumulating the
> result in an extra parameter so I wrote the some code (see below) and
> tested in on cygwin/clisp.
>
> CL-USER> (test 60 5)
> timing 'extra variable' method:
> Real time: 3.575 sec.
> Run time: 3.545 sec.
> Space: 47882056 Bytes
> GC: 65, GC time: 1.641 sec.
>
> timing 'lamda accumulator' method:
> Real time: 12.487 sec.
> Run time: 12.327 sec.
> Space: 259159668 Bytes
> GC: 349, GC time: 8.62 sec.
>
> As you can see, in CLISP using lamda to accumulate a result is about 3
> times slower than using a extra variable. I'm curious how the
> performance varies in other lisps.
Your definition of F2 is buggy, here is a working definition:
(defun f2 (f lst n)
(cond ((= n 0) (funcall f nil))
((null lst) nil)
(t
(let ((first (car lst))
(rest (cdr lst)))
(f2 (lambda (l) (funcall f (cons first l))) rest (- n 1))
(f2 f rest n)))))
I get these timings:
CL-USER> (test 60 5)
timing 'extra variable' method:
Timing the evaluation of (F1 (FUNCTION IDENTITY) (LIST-N N) M)
user time = 0.500
system time = 0.000
Elapsed time = 0:00:01
Allocation = 0 bytes standard / 65837871 bytes fixlen
0 Page faults
timing 'lamda accumulator' method:
Timing the evaluation of (F2 (FUNCTION IDENTITY) (LIST-N N) M)
user time = 5.921
system time = 0.000
Elapsed time = 0:00:06
Allocation = 239408768 bytes standard / 300383919 bytes fixlen
0 Page faults
NIL
With a little tweaking we can take some of the pressure off the GC:
(defun f2 (f lst n)
(declare (type fixnum n)
(type list lst)
(optimize (speed 3) (safety 1)))
(cond ((= n 0) (funcall f nil))
((consp lst)
(let ((first (car (the cons lst)))
(rest (cdr (the cons lst))))
(flet ((inner (l) (funcall f (cons first l))))
(declare (dynamic-extent (function inner)))
(f2 #'inner rest (- n 1)))
(f2 f rest n)))
((null lst) nil)
(t (error "Improper list"))))
timing 'lamda accumulator' method:
Timing the evaluation of (F2 (FUNCTION IDENTITY) (LIST-N N) M)
user time = 3.843
system time = 0.000
Elapsed time = 0:00:04
Allocation = 576 bytes standard / 300383864 bytes fixlen
0 Page faults
On Wed, 08 Mar 2006 09:31:12 -0800, Joe Marshall wrote:
> I get these timings:
> CL-USER> (test 60 5)
> timing 'extra variable' method:
> Timing the evaluation of (F1 (FUNCTION IDENTITY) (LIST-N N) M)
>
> user time = 0.500
> system time = 0.000
> Elapsed time = 0:00:01
> Allocation = 0 bytes standard / 65837871 bytes fixlen
> 0 Page faults
>
> timing 'lamda accumulator' method:
> Timing the evaluation of (F2 (FUNCTION IDENTITY) (LIST-N N) M)
>
> user time = 3.843
> system time = 0.000
> Elapsed time = 0:00:04
> Allocation = 576 bytes standard / 300383864 bytes fixlen
> 0 Page faults
I suppose this is one of the reasons that techniques like monads get no
love in common lisp. Basically every step in a monadic computation gets
wrapped in a new lambda. Though, that doesn't seem to stop people from
using continuation passing style which is just as expensive.
What is the best strategy to get good (better) performance from techniques
that make extensive use of closures?
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> On Wed, 08 Mar 2006 09:31:12 -0800, Joe Marshall wrote:
>
> > I get these timings:
> > CL-USER> (test 60 5)
> > timing 'extra variable' method:
> > Timing the evaluation of (F1 (FUNCTION IDENTITY) (LIST-N N) M)
> >
> > user time = 0.500
> > system time = 0.000
> > Elapsed time = 0:00:01
> > Allocation = 0 bytes standard / 65837871 bytes fixlen
> > 0 Page faults
> >
> > timing 'lamda accumulator' method:
> > Timing the evaluation of (F2 (FUNCTION IDENTITY) (LIST-N N) M)
> >
> > user time = 3.843
> > system time = 0.000
> > Elapsed time = 0:00:04
> > Allocation = 576 bytes standard / 300383864 bytes fixlen
> > 0 Page faults
>
>
> I suppose this is one of the reasons that techniques like monads get no
> love in common lisp. Basically every step in a monadic computation gets
> wrapped in a new lambda. Though, that doesn't seem to stop people from
> using continuation passing style which is just as expensive.
>
> What is the best strategy to get good (better) performance from techniques
> that make extensive use of closures?
Inline where possible. This can make a *huge* difference.
Unfortunately, the map-hands function calls itself recursively so
inlining isn't really feasible here.
Matthew D Swank <·······································@c.net> writes:
> I suppose this is one of the reasons that techniques like monads get no
> love in common lisp. Basically every step in a monadic computation gets
> wrapped in a new lambda. Though, that doesn't seem to stop people from
> using continuation passing style which is just as expensive.
>
> What is the best strategy to get good (better) performance from techniques
> that make extensive use of closures?
A good (better) compiler. Try SBCL. In CPS, LAMBDA should be free,
except in the cases where you actually capture the continuation � la
call/cc.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
On Mon, 13 Mar 2006 12:05:00 -0800, Thomas F. Burdick wrote:
> Matthew D Swank <·······································@c.net> writes:
>
>>
>> What is the best strategy to get good (better) performance from techniques
>> that make extensive use of closures?
>
> A good (better) compiler. Try SBCL. In CPS, LAMBDA should be free,
> except in the cases where you actually capture the continuation à la
> call/cc.
This doesn't seem true in a case with tree recursion:
CL-USER> (defun make-zero-tree (depth)
(if (zerop depth)
nil
(let ((tree (make-zero-tree (- depth 1))))
(cons 0 (cons tree tree)))))
MAKE-ZERO-TREE
CL-USER> (defun num-node (tree)
(if (null tree)
0
(+ 1 (num-node (cadr tree)) (num-node (cddr tree)))))
NUM-NODE
CL-USER> (defun num-node-cps (tree &optional (k #'identity))
(if (null tree)
(funcall k 0)
(num-node-cps (cadr tree)
#'(lambda (n)
(num-node-cps (cddr tree)
#'(lambda (m)
(funcall k (+ 1 m n))))))))
NUM-NODE-CPS
CL-USER> (let ((tree (make-zero-tree 28)))
(time (num-node tree)))
Evaluation took:
12.308 seconds of real time
12.304769 seconds of user run time
0.0 seconds of system run time
0 page faults and
8,192 bytes consed.
268435455
CL-USER> (let ((tree (make-zero-tree 28)))
(time (num-node-cps tree)))
Evaluation took:
82.417 seconds of real time
77.42084 seconds of user run time
0.352022 seconds of system run time
0 page faults and
12,884,939,992 bytes consed.
268435455
CL-USER>
This is in sbcl 0.9.10. I don't know what the default optimizations are,
but the lambdas seem to be consing in this case.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Joe Marshall wrote:
> (defun pair-or-better (hand)
> (destructuring-bind (a b c d e) hand
> (or (eql (car a) (car b))
> (eql (car a) (car c))
> (eql (car a) (car d))
> (eql (car a) (car e))
> (eql (car b) (car c))
> (eql (car b) (car d))
> (eql (car b) (car e))
> (eql (car c) (car d))
> (eql (car c) (car e))
> (eql (car d) (car e)))))
This is poorly named, since it doesn't catch straights and flushes.
^L
Louis Theran wrote:
> Joe Marshall wrote:
> > (defun pair-or-better (hand)
> > (destructuring-bind (a b c d e) hand
> > (or (eql (car a) (car b))
> > (eql (car a) (car c))
> > (eql (car a) (car d))
> > (eql (car a) (car e))
> > (eql (car b) (car c))
> > (eql (car b) (car d))
> > (eql (car b) (car e))
> > (eql (car c) (car d))
> > (eql (car c) (car e))
> > (eql (car d) (car e)))))
>
> This is poorly named, since it doesn't catch straights and flushes.
True. Instead of complaining, though, how about supplying us an
improved version?
Frode Vatvedt Fjeld wrote:
> "Geoffrey Summerhayes" <·······@NhOoStPmAaMil.com> writes:
>
> > Needs one more condition, ace-high straight.
>
> Wouldn't it work to simply declare that :ace also comes after :king, like so:
>
> (defun pair-or-better (hand)
> (or (some (lambda (card)
> (<= 2 (count (car card) hand :key #'car)))
> hand)
> (= 5 (count (cdar hand) hand :key #'cdr))
> (= 4 (count-if (lambda (card)
> (find (second (member (car card)
> '(:ace 2 3 4 5 6 7 8 9 10 :Jack :Queen :King :ace)))
> hand :key #'car))
> hand))))
>
> %% (count-hands *deck* 5 (complement #'pair-or-better))
> => 1299480
That was my original thought too, but then a hand like A-2-3-Q-K will
pass.
Maybe
(let ((card-values (mapcar #'car hand)))
(= 5 (loop for (a b c d e) on '(:ace 2 3 4 5 6 7 8 9 10 :jack :queen
:king :ace)
until (null e)
maximizing (length (intersection (list a b c d e)
card-values))))))
--
Geoff
From: Alexander Schmolck
Subject: Re: Combinatorics and Poker, Python vs Lisp
Date:
Message-ID: <yfs8xrrh4ph.fsf@oc.ex.ac.uk>
Frode �ijord <·····@sim.no> writes:
> I'm sure I can do this in Lisp in much the same way, but I'm not sure how.
Actually I don't think you can (unless you include scheme in "Lisp"). Common
lisp doesn't have coroutines or generators and I see no easy way to emulate
them and no way to supply a full-blown equivalent.
'as
Frode �ijord <·····@sim.no> writes:
> Just one more thing: This is how i generate all possible poker hands in
> Python (or all possible n length combinations of any list of items):
>
> def comb(items, n):
> if n==0: yield []
> else:
> for i in xrange(len(items)):
> for cc in comb(items[i+1:],n-1):
> yield [items[i]]+cc
>
> This gives the hands one at a time using generators. This means that I
> can iterate over the hands like so:
>
> for hand in comb(deck, 5):
> ...
>
> where deck is a list of the 52 cards (minus the starting hands).
>
> I'm sure I can do this in Lisp in much the same way, but I'm not sure
> how. Lisp code hurts my head, but I'm counting on it to stop :)
I've had a bash at writing a brute force enumeration in
Common Lisp:
;; For efficiency, I'm representing the deck of cards as numbers
;; 0 - 51. Thus a subset, such as {12,13,...,51} gets represented
;; by the number 12. This routine is a straight forward walk of the
;; tree of possibilities that accumulates the path in the index stack
;; and passes it to the function at each leaf
;;
(defun card-indexes (hand-size deck-size func)
(declare (fixnum hand-size deck-size))
(declare (function func))
(labels ((walk (index count-down index-stack)
(declare (fixnum index count-down))
(if (zerop count-down)
(funcall func index-stack)
(loop for i fixnum from index to (- deck-size count-down)
do (walk (+ i 1)
(- count-down 1)
(cons i index-stack))))))
(walk 0 hand-size '())))
;; the usual idiom for creating an iteration macro out
;; of a higher order function that does a fancy iteration
;;
(defmacro do-combinations ((var r n) &body code)
`(flet ((f (,var) ,@code))
(card-indexes ,r ,n #'f)))
;; CL's built-in CASE uses EQL for its comparisons
;; a good choice for symbols and numbers, but useless
;; for short lists, so I've defined EQUAL-CASE to use EQUAL
;; instead.
;;
(defmacro equal-case (form &body clauses)
(let ((value (gensym)))
`(let ((,value ,form))
(cond ,@(loop for (key . actions) in clauses
collect `((equal ,value ',key) ,@actions))))))
;; Suits don't matter in poker
;;
(defun strip-suits (hand)
(mapcar (lambda (card)
(declare (type (integer 0 51) card))
(mod card 13))
hand))
;; groups cards of the same value
;; we only need to remember how many there are
;; turns (K 4 4 K K) into (3 2)
;; (Q 10 Q 4 4) into (2 1 2)
;; except that our cards are just numbers
;;
#|(defun group-hand (cards)
(when cards
(cons (count (car cards) cards)
(group-hand (remove (car cards) cards)))))|#
;; The commented out version is pretty code, but rather slow
;; This goes four times as fast:
(defun group-hand (cards)
(let ((counts (make-array '(13)
:element-type '(integer 0 4)
:initial-element 0)))
(declare (type (simple-array (integer 0 4) (13)) counts))
(dolist (card cards)
(incf (aref counts (the (integer 0 12) card))))
(loop for n of-type (integer 0 4) across counts
when (plusp n) collect n)))
;; reduce to cannonical form by sorting because
;; (1 1 1 2) = (1 1 2 1) = (1 2 1 1) = (2 1 1 1)
;; etc.
;;
(defun signature (hand)
(sort (group-hand (strip-suits hand)) #'>))
;; Brute force calculation of some poker hands
;; always (count-cases 5 52)
(defun count-cases (hand-size deck-size)
(let ((pair 0)
(two-pairs 0)
(three-of-a-kind 0)
(full-house 0)
(four-of-a-kind 0))
(declare (fixnum pair two-pairs three-of-a-kind full-house four-of-a-kind))
(do-combinations (hand hand-size deck-size)
(equal-case (signature hand)
((4 1) (incf four-of-a-kind))
((3 2) (incf full-house))
((3 1 1) (incf three-of-a-kind))
((2 2 1) (incf two-pairs))
((2 1 1 1) (incf pair))))
(values pair two-pairs three-of-a-kind full-house four-of-a-kind)))
CL-USER> (time (count-cases 5 52))
; Compiling LAMBDA NIL:
; Compiling Top-Level Form:
; Evaluation took:
; 43.78 seconds of real time
; 38.446655 seconds of user run time
; 0.194016 seconds of system run time
; 15,357,453,554 CPU cycles
; [Run times include 5.65 seconds GC run time]
; 0 page faults and
; 472,304,872 bytes consed.
;
1098240
123552
54912
3744
624
I believe that these are the correct numbers. I compiled it
with CMUCL (and turned the optimisations all the way
up). The times are for
CPU: Pentium II/Pentium II Xeon/Celeron (350.80-MHz 686-class CPU)
Origin = "GenuineIntel" Id = 0x652 Stepping = 2
so I guess that this will take about 4 seconds on a modern machine.
---------
You can see Common Lisp's strange property of being "building
material" rather than a finished language showing through
here. The code looks very clean
(do-combinations (hand hand-size deck-size)
(equal-case (signature hand)
((4 1) (incf four-of-a-kind))
((3 2) (incf full-house))
((3 1 1) (incf three-of-a-kind))
((2 2 1) (incf two-pairs))
((2 1 1 1) (incf pair))))
almost as though the language was specifically designed for
this kind of work.
And sure enough the fit to the application is because the
language is specifically designed for this kind of work,
but only because I've been busy finishing the design of the
language:
(defmacro do-combinations ((var r n) &body code)
`(flet ((f (,var) ,@code))
(card-indexes ,r ,n #'f)))
to take advantage of knowing more detail about the
application it is for :-)
Alan Crowe
Edinburgh
Scotland