# Fast Jaccard Distance between sets of strings?

**URL:** <https://discourse.julialang.org/t/fast-jaccard-distance-between-sets-of-strings/84125>\
**Category:** Performance\
**Tags:** dataframes\
**Created:** [July 12, 2022, 8:51pm UTC](https://discourse.julialang.org/t/fast-jaccard-distance-between-sets-of-strings/84125 "2022-07-12T20:51:38Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![tp2750](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tp2750/32/207806_2.png) [@tp2750](https://discourse.julialang.org/u/tp2750)\
**Post date:** [July 12, 2022, 8:51pm UTC](https://discourse.julialang.org/t/fast-jaccard-distance-between-sets-of-strings/84125/1 "2022-07-12T20:51:38Z")

</div>

My friend needs to compute the jaccard distance between sets of strings.  
The number of sets is hundreds and the number of strings in each set is thousands. The length of the strings is \<= 20. He has thousands of datasets of this type.

He has a function to do it in python, but I would like to show that Julia can do it faster 😄

His python function looks like this:

```python
from scipy.spatial import distance
import pandas as pd
from scipy.spatial.distance import pdist, jaccard
from scipy.spatial.distance import squareform
from collections import Counter

def calcDistances(d):
        df = pd.DataFrame({k:Counter(v) for k, v in d.items()}).T.fillna(0).astype(int)
        jaccard_distances = pdist(df, metric='jaccard')
        jaccard_distances = squareform(jaccard_distances)
        resdf=pd.DataFrame(jaccard_distances, index=df.index, columns=df.index)
        results=resdf.to_dict()
        return(results)

```

Here’s my attempt in Julia, which does not do the final conversion back to dict, but already takes twice as long:

```julia
using Distances, DataFrames, StatsBase

function j1(g)
    x = coalesce.(vcat(DataFrame.([countmap(x) for x in values(g)])..., cols = :union), 0)
    pairwise(Jaccard(), Matrix(x), dims=1)
end

```

On a large dataset the python function runs in 7.5 sec where my Julia function takes 14 sec.

```julia
julia> @time j1(l1);
 13.485393 seconds (34.85 M allocations: 2.139 GiB, 10.61% gc time)

```

Most of the time is building the DataFrame:

```julia
julia> @time vcat(DataFrame.([countmap(x) for x in values(l1)])..., cols = :union);
 10.882624 seconds (34.69 M allocations: 1.940 GiB, 7.80% gc time, 0.81% compilation time)

```

How can I make this faster?

In the details below I show what the functions are doing on a small data set:

> ****
>
> Python:
> 
> ```python
> import collections
> from scipy.spatial import distance
> import pandas as pd
> from scipy.spatial.distance import pdist, jaccard
> from scipy.spatial.distance import squareform
> from collections import Counter
> 
> testDict = collections.defaultdict(set)
> testDict["EFB1"]=set(['a','b','c','d','e','e'])
> testDict["EFB2"]=set(['a','f','c','d'])
> testDict["EFB3"]=set(['a','f'])
> d = testDict
> >>> df = pd.DataFrame({k:Counter(v) for k, v in d.items()}).T.fillna(0).astype(int)
> >>> df
> c e b d a f
> EFB1 1 1 1 1 1 0
> EFB2 1 0 0 1 1 1
> EFB3 0 0 0 0 1 1
> 
> >>> jaccard_distances = pdist(df, metric='jaccard')
> array([0.5 , 0.83333333, 0.5])
> >>> jaccard_distances = squareform(jaccard_distances)
> >>> jaccard_distances
> array([[0. , 0.5 , 0.83333333],
> [0.5 , 0. , 0.5],
> [0.83333333, 0.5 , 0.]])
> 
> >>> resdf=pd.DataFrame(jaccard_distances, index=df.index, columns=df.index)
> >>> resdf
> EFB1 EFB2 EFB3
> EFB1 0.000000 0.5 0.833333
> EFB2 0.500000 0.0 0.500000
> EFB3 0.833333 0.5 0.000000
> 
> ```
> 
> And for Julia
> 
> ```julia
> t1 = Dict(
> "EFB1" => Set(["a","b","c","d","e","e"]),
> "EFB2" => Set(["a","f","c","d"]),
> "EFB3" => Set(["a","f"]),
> )
> x = coalesce.(vcat(DataFrame.([countmap(x) for x in values(t1)])..., cols = :union), 0)
> 
> # 3×6 DataFrame
> # Row │ a f b c d e     
> # │ Int64 Int64 Int64 Int64 Int64 Int64 
> # ─────┼──────────────────────────────────────────
> # 1 │ 1 1 0 0 0 0
> # 2 │ 1 0 1 1 1 1
> # 3 │ 1 1 0 1 1 0
> 
> pairwise(Jaccard(), Matrix(x), dims=1)
> # 3×3 Matrix{Float64}:
> # 0.0 0.833333 0.5
> # 0.833333 0.0 0.5
> # 0.5 0.5 0.0
> 
> ```

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [July 12, 2022, 10:36pm UTC](https://discourse.julialang.org/t/fast-jaccard-distance-between-sets-of-strings/84125/2 "2022-07-12T22:36:48Z")

</div>

> [@tp2750](#):
>
> How can I make this faster?

Build fewer temporary data structures.

```julia
julia> orig(sets) = coalesce.(vcat(DataFrame.([countmap(x) for x in values(sets)])...,cols = :union),0)
orig (generic function with 1 method)

julia> @time orig(t1) # 2nd time not to measure compilation
  0.000239 seconds (468 allocations: 33.062 KiB)

julia> function bar(sets)
         df = DataFrame([c => zeros(Int,3) for c in union(values(sets)...)],copycols=false)
         populateRows!(df,sets)
         end

julia> function populateRows!(df, sets)
         for (row, set) in enumerate(values(sets))
           for col in set
             df[row,col] = 1
             end
             end
             df
             end

julia> @time bar(t1) # second run not to measure compilation
   0.000040 seconds (46 allocations: 3.719 KiB)

```

---

<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:** [July 13, 2022, 6:15am UTC](https://discourse.julialang.org/t/fast-jaccard-distance-between-sets-of-strings/84125/3 "2022-07-13T06:15:03Z")

</div>

I would not use `DataFrame` for this task (you could do your DataFrames.jl code faster, but in this case it is better not to use it if you need performance).

Instead I recommend you use a `Matrix` directly:

```julia
julia> function fun(t1)
           colmap = Dict(x => i for (i, x) in enumerate(union(values(t1)...)))
           mat = zeros(Int, length(t1), length(colmap))
           for (i, x) in enumerate(values(t1))
               for v in x
                   mat[i, colmap[v]] += 1
               end
           end
           return mat
       end
fun (generic function with 1 method)

julia> @time fun(t1)
  0.115027 seconds (169.71 k allocations: 9.692 MiB, 99.98% compilation time)
3×6 Matrix{Int64}:
 1 0 0 0 1 0
 0 1 1 1 1 1
 1 1 0 0 1 1

julia> @time fun(t1)
  0.000015 seconds (17 allocations: 1.266 KiB)
3×6 Matrix{Int64}:
 1 0 0 0 1 0
 0 1 1 1 1 1
 1 1 0 0 1 1

```

---

<div class="post-metadata">

**Author:** ![tp2750](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tp2750/32/207806_2.png) [@tp2750](https://discourse.julialang.org/u/tp2750)\
**Post date:** [July 13, 2022, 5:11pm UTC](https://discourse.julialang.org/t/fast-jaccard-distance-between-sets-of-strings/84125/4 "2022-07-13T17:11:33Z")

</div>

Thank you very much @Jeff_Emanuel and @bkamins !

With the optimization by @bkamins my the julia version is now only half the runtime of the python one. Julia rules 😄

The best part of Julia is the community!

Thanks again.