# Fast String processing in Julia vs. Python

**URL:** <https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443>\
**Category:** General Usage\
**Created:** [March 4, 2017, 3:24pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443 "2017-03-04T15:24:02Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 4, 2017, 3:24pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/1 "2017-03-04T15:24:02Z")

</div>

I am trying to convert [this notebook on probability by Peter Norvig](http://nbviewer.jupyter.org/url/norvig.com/ipython/Probability.ipynb). 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:

```julia
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:

```python
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?

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 3:25pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/2 "2017-03-04T15:25:47Z")

</div>

> [@mbeltagy](#):
>
> cross(A, B)=[“$a$b” for a in A for b in B]

Try `cross(A, B) = (string(a, b) for a in A for b in B)`.  
This avoids string interpolation, and uses a generator instead of an array.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 4, 2017, 3:30pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/3 "2017-03-04T15:30:22Z")

</div>

Just note that you don’t need to avoid string interpolateion. The two are exactly the same.

```julia
julia> expand(:("$a$b"))
:((Base.string)(a, b))

```

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 4, 2017, 3:31pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/4 "2017-03-04T15:31:51Z")

</div>

The performance blocks are in a combination of `P`, `count_o` and `four_kinds`. Not sure how to make them any faster.

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 4, 2017, 3:36pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/5 "2017-03-04T15:36:21Z")

</div>

You appear to be using `set` in python and `Array` in julia and you are intersecting them. The `Set` should be the correct datastructure to use in julia.

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 4, 2017, 3:52pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/6 "2017-03-04T15:52:22Z")

</div>

Using sets improved things a bit. So I modified `combos` to

```julia
function combos(items, n)
    Set(join(combo," ") for combo in combinations(items,n))
end

```

Now I get  
`19.393026 seconds (5.20 M allocations: 119.007 MB, 0.25% gc time)`

Certainly twice a fast as before, but not yet near python’s 4 seconds.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 3:55pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/7 "2017-03-04T15:55:00Z")

</div>

You need a `Set` in `cross` too.

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 4, 2017, 3:59pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/8 "2017-03-04T15:59:48Z")

</div>

That wouldn’t work, because `combinations` from `StatsBase` requires an indexable object, a `Set` is not indexable.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:06pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/9 "2017-03-04T16:06:44Z")

</div>

Just doing `Hands = combos(deck, 5)` is already terribly slow.  
I don’t understand why it’s necessary to convert these to strings.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:10pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/10 "2017-03-04T16:10:46Z")

</div>

> [@mbeltagy](#):
>
> Set(join(combo," ") for combo in combinations(items,n))

Doing `combinations(deck, 5)` seems to be much faster on Julia v0.6 (where it now lives in the `Combinatorics.jl` package).

---

<div class="post-metadata">

**Author:** ![mbeltagy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbeltagy/32/130_2.png) [@mbeltagy](https://discourse.julialang.org/u/mbeltagy)\
**Post date:** [March 4, 2017, 4:18pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/11 "2017-03-04T16:18:34Z")

</div>

Basically each possible 5 card hand is represented as a string. This is keeping with the python implementation. Arguably, I could create a `hand` type and define operators on it. But that would be more code, and I would like to have simple (yet fast) tutorial. I am still puzzled as to why Julia is so much slower that python here (4 seconds total run time).  
On my computer, the `combo` version with the `Set` ran at 17 seconds, while `Array` version ran 7 seconds. The `Set` implementation was faster, however, in the `intersect`.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:24pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/12 "2017-03-04T16:24:25Z")

</div>

Can you post the current version of the code?

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:26pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/13 "2017-03-04T16:26:20Z")

</div>

By the way, the Python version is checking for a flush and the Julia for four hands. Not sure how much difference that makes.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:49pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/14 "2017-03-04T16:49:06Z")

</div>

Did you actually check the function `count_o`? I’m not sure it works correctly:

```julia
julia> count_o(s,l)=count(x->x==l,s)
count_o (generic function with 1 method)

julia> count_o("ABCA", "A")
0

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:51pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/15 "2017-03-04T16:51:22Z")

</div>

```julia
julia> s = "ABCA"
"ABCA"

julia> count(x->x=="A", s)
0

julia> count(x->x=='A', s)
2

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:55pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/16 "2017-03-04T16:55:27Z")

</div>

Ignore me, this is irrevelant since

```julia
julia v0.5> [suit for suit in "ABCD"]
4-element Array{Char,1}:
 'A'
 'B'
 'C'
 'D'

```

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 4:58pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/17 "2017-03-04T16:58:38Z")

</div>

Defining

```julia
have_flush(hand) = any(suit->count_o(hand, suit) == 5, suits)

```

and reducing everything to

```julia
count(have_flush, Hands)

```

gives 6.1 seconds on my machine, compared to 4.9 for Python.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 5:00pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/18 "2017-03-04T17:00:27Z")

</div>

This completely avoids the intersection though.

---

<div class="post-metadata">

**Author:** ![dpsanders](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpsanders/32/3573_2.png) [@dpsanders](https://discourse.julialang.org/u/dpsanders)\
**Post date:** [March 4, 2017, 5:03pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/19 "2017-03-04T17:03:17Z")

</div>

On Julia 0.6 latest master, using an iterator for `combos`:

```julia
function combos(items, n)
    (join(combo, " ") for combo in combinations(items,n))
end

Hands = combos(deck, 5)

```

I get

```julia
julia> @time count(have_flush, Hands) // length(Hands)
  2.866761 seconds (36.41 M allocations: 1.628 GiB, 6.31% gc time)
33//16660

```

---

<div class="post-metadata">

**Author:** ![bkamins](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bkamins/32/208538_2.png) [@bkamins](https://discourse.julialang.org/u/bkamins)\
**Post date:** [March 4, 2017, 6:15pm UTC](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443/20 "2017-03-04T18:15:57Z")

</div>

I thought it is worth to elaborate more on what @dpsanders proposed.

Apart from using `Set` in the computations I think that the problem is that

```julia
four_kind(hand)=any(count_o(hand,rank) == 4 for rank in ranks)

```

uses `ranks` that is a global variable. Using local variable in your definition of `four_kind` like this:

```julia
function four_kind(hand)
    r::String = ranks
    any(count_o(hand,rank) == 4 for rank in r)
end

```

speeds things up.

@dpsanders definition of `have_flush` avoids this problem although global variable is used.

[Next page](https://discourse.julialang.org/t/fast-string-processing-in-julia-vs-python/2443.md?page=2)