I am trying to convert this notebook on probability by Peter Norvig. I observe that Python runs much faster than Julia. I couldn’t pin down the problem in my Julia code.
What is happening here is that we are looping over a massive array of strings that represent all the possible combinations of 5 card draws from a standard deck and we are checking for certain straightforward patterns to work out the probabilities.
Here is the Julia code:
using Combinatorics
"counts the number of occurances of l in s "
count_o(s,l)=count(x->x==l,s)
"The set of ways of concatenating one item from collection A with one from B."
cross(A, B)=["$a$b" for a in A for b in B]
"All combinations of n items; each combo as a concatenated str."
function combos(items, n)
[join(combo," ") for combo in combinations(items,n)]
end
"""The probability of an event, given a sample space of equiprobable outcomes.
event can be either a set of outcomes, or a predicate (true for outcomes in the event)."""
function P(event, space)
event_ = such_that(event, space)
length(intersect(event_,space))//length(space)
end
#Making use of Julia's multiple dispatch
"The subset of elements in the collection for which the predicate is true."
function such_that(predicate::Function, collection)
filter(predicate,collection)
end
"Default return for a collection"
function such_that(event, collection)
event
end
suits = "SHDC"
ranks = "A23456789TJQK"
deck = cross(ranks, suits)
Hands = combos(deck, 5) #A massive list of all possible hands
four_kind(hand)=any(count_o(hand,rank) == 4 for rank in ranks)
P(four_kind, Hands) #Warm up
@time P(four_kind, Hands)
I get 46.577004 seconds (5.20 M allocations: 119.030 MB, 0.10% gc time)
The Python code:
import itertools
from fractions import Fraction
from math import factorial
def cross(A, B):
"The set of ways of concatenating one item from collection A with one from B."
return {a + b
for a in A for b in B}
def combos(items, n):
"All combinations of n items; each combo as a concatenated str."
return {' '.join(combo)
for combo in itertools.combinations(items, n)}
def choose(n, c):
"Number of ways to choose c items from a list of n items."
return factorial(n) // (factorial(n - c) * factorial(c))
def P(event, space):
"""The probability of an event, given a sample space of equiprobable outcomes.
event can be either a set of outcomes, or a predicate (true for outcomes in the event)."""
if is_predicate(event):
event = such_that(event, space)
return Fraction(len(event & space), len(space))
is_predicate = callable
def such_that(predicate, collection):
"The subset of elements in the collection for which the predicate is true."
return {e for e in collection if predicate(e)}
suits = 'SHDC'
ranks = 'A23456789TJQK'
deck = cross(ranks, suits)
Hands = combos(deck, 5)
def flush(hand):
return any(hand.count(suit) == 5 for suit in suits)
P(flush, Hands)
It runs in just 4 seconds.
Any ideas on how I could improve the code, or if I can’t, why is Julia slow here?