# What's the best way to compare items in an array to every other item?

**URL:** <https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806>\
**Category:** General Usage\
**Tags:** performance, strings, arrays\
**Created:** [July 25, 2019, 6:17pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806 "2019-07-25T18:17:04Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [July 25, 2019, 6:17pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/1 "2019-07-25T18:17:04Z")

</div>

Say I have the following array:

```julia
names = ["John Doe", "Bugs Bunny", "Cosmo Kramer", "Jon Doe", "Elmer Fudd", "Kosmo Cramer"]

```

I would like to compare each string in the array with every other string in the array and compute the distance between the two via the StringDistances.jl package (which will allow me to group similar strings together). For example, `"John Doe"` and `"Jon Doe"` are similar enough that I would want to remove both of those elements from the array (and store them somewhere else for later).

I wrote a function that achieves this, but I know that the amazing Julia community can figure out a way to make it more performant! My first attempt to accomplish the above uses recursion and looks like this:

```julia
using StringDistances

names = ["John Doe", "Bugs Bunny", "Cosmo Kramer", "Jon Doe", "Elmer Fudd", "Kosmo Cramer"]
all_matches = Array[]

function matches(arr::Array)
    if length(arr) > 1
        indexes = findall(x -> compare(Jaro(), x, arr[1]) > 0.8, arr)
        push!(all_matches, [arr[i] for i in indexes])
        deleteat!(arr, indexes)
        matches(arr)
    else
        return filter(x -> length(x) > 1, all_matches)
    end
end

matched = matches(names)
2-element Array{Array,1}:
 ["John Doe", "Jon Doe"]
 ["Cosmo Kramer", "Kosmo Cramer"]

```

I don’t know much about Julia performance but I do know that there is usually a much faster way to do things relative to whatever it is that I usually come up with 😁

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [July 25, 2019, 7:32pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/2 "2019-07-25T19:32:11Z")

</div>

The very first thing to do is to give `all_matches` a proper concrete type. Use `Vector{String}[]`.

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [July 25, 2019, 7:37pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/3 "2019-07-25T19:37:06Z")

</div>

Ah, thanks!

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [July 25, 2019, 7:47pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/4 "2019-07-25T19:47:44Z")

</div>

Well… Deleting from an arbitrary position of an array is pretty slow as it involves data movement. I think a double loop with some bookkeeping would do:

```julia
function matches(arr::Vector{String})
    all_matches = Vector{String}[]
    first_unprocessed = 1
    num_unprocessed = nmax = length(arr)
    indexes = Int[]
    unprocessed = trues(nmax)
    while num_unprocessed > 0
        compar = arr[first_unprocessed]
        unprocessed[first_unprocessed] = false
        empty!(indexes)
        push!(indexes, first_unprocessed)
        for j = first_unprocessed + 1:nmax
            if unprocessed[j] && compare(Jaro(), arr[j], compar) > 0.8
                push!(indexes, j)
                (j == first_unprocessed + 1) && (first_unprocessed = j)
                unprocessed[j] = true
                num_unprocessed -= 1
            end
        end
        length(indexes) == 1 || push!(all_matches, [arr[i] for i in indexes])
        first_unprocessed += 1
        num_unprocessed -= 1
    end
    all_matches
end

```

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [July 25, 2019, 7:57pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/5 "2019-07-25T19:57:44Z")

</div>

> [@Vasily\_Pisarev](#):
>
> function matches(arr::Vector{String}) all\_matches = Vector{String} first\_unprocessed = 1 num\_unprocessed = nmax = length(arr) indexes = Int unprocessed = trues(nmax) while num\_unprocessed \> 0 compar = arr[first\_unprocessed] unprocessed[first\_unprocessed] = false empty!(indexes) push!(indexes, first\_unprocessed) for j = first\_unprocessed + 1:nmax if unprocessed[j] && compare(Jaro(), arr[j], compar) \> 0.8 push!(indexes, j) (j == first\_unprocessed + 1) && (first\_unprocessed = j) unprocessed[j] = true num\_unprocessed -= 1 end end length(indexes) == 1 || push!(all\_matches, [arr[i] for i in indexes]) first\_unprocessed += 1 num\_unprocessed -= 1 end all\_matches end

Thanks for the response, Vasily! On my machine, this version seems to be quite a bit slower than my original function:

```julia
all_matches = Vector{String}[]
names = ["John Doe", "Bugs Bunny", "Cosmo Kramer", "Jon Doe", "Elmer Fudd", "Kosmo Cramer"]

function matches(arr::Array)
    if length(arr) > 1
        indexes = findall(x -> compare(Jaro(), x, arr[1]) > 0.8, arr)
        push!(all_matches, [arr[i] for i in indexes])
        deleteat!(arr, indexes)
        matches(arr)
    else
        return filter(x -> length(x) > 1, all_matches)
    end
end

function matches1(arr::Vector{String})
    all_matches = Vector{String}[]
    first_unprocessed = 1
    num_unprocessed = nmax = length(arr)
    indexes = Int[]
    unprocessed = trues(nmax)
    while num_unprocessed > 0
        compar = arr[first_unprocessed]
        unprocessed[first_unprocessed] = false
        empty!(indexes)
        push!(indexes, first_unprocessed)
        for j = first_unprocessed + 1:nmax
            if unprocessed[j] && compare(Jaro(), arr[j], compar) > 0.8
                push!(indexes, j)
                (j == first_unprocessed + 1) && (first_unprocessed = j)
                unprocessed[j] = true
                num_unprocessed -= 1
            end
        end
        length(indexes) == 1 || push!(all_matches, [arr[i] for i in indexes])
        first_unprocessed += 1
        num_unprocessed -= 1
    end
    return all_matches
end

@btime matched1 = matches1(names)
  5.282 μs (54 allocations: 6.09 KiB)
  2-element Array{Array{String,1},1}:
  ["John Doe", "Jon Doe"]
  ["Cosmo Kramer", "Kosmo Cramer"]

@btime matched = matches(names)
  320.235 ns (2 allocations: 128 bytes)
  2-element Array{Array{String,1},1}:
  ["John Doe", "Jon Doe"]
  ["Cosmo Kramer", "Kosmo Cramer"]

```

---

<div class="post-metadata">

**Author:** ![Vasily\_Pisarev](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vasily_pisarev/32/7929_2.png) [@Vasily\_Pisarev](https://discourse.julialang.org/u/Vasily_Pisarev)\
**Post date:** [July 25, 2019, 8:48pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/6 "2019-07-25T20:48:08Z")

</div>

```julia
julia> @btime matched = matches(names)
  269.757 ns (2 allocations: 128 bytes)
2-element Array{Array{String,1},1}:
 ["John Doe", "Jon Doe"]         
 ["Cosmo Kramer", "Kosmo Cramer"]

julia> names
1-element Array{String,1}:
 "Elmer Fudd"

```

Rings a bell? 🙂  
Your function deletes matches from the original array, so that anything but the first run don’t do anything.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 26, 2019, 5:17am UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/7 "2019-07-26T05:17:47Z")

</div>

I generally prefer a functional approach, eg something like

```julia
using StringDistances

function filter_matches(str, other_strs)
    filter(x -> compare(Jaro(), x, str) < 0.8, other_strs)
end

function remove_duplicates(strs)
    i = 1
    while i < length(strs)
        strs = vcat(@view(strs[1:i]),
                    filter_matches(strs[i], @view(strs[(i + 1):end])))
        i += 1
    end
    strs
end

```

Which runs as

```julia

julia> names = ["John Doe", "Bugs Bunny", "Cosmo Kramer",
       "Jon Doe", "Elmer Fudd", "Kosmo Cramer"]
6-element Array{String,1}:
 "John Doe"    
 "Bugs Bunny"  
 "Cosmo Kramer"
 "Jon Doe"     
 "Elmer Fudd"  
 "Kosmo Cramer"

julia> remove_duplicates(names)
4-element Array{String,1}:
 "John Doe"    
 "Bugs Bunny"  
 "Cosmo Kramer"
 "Elmer Fudd"  

```

I would not worry about performance too much, I think your bottleneck is `compare`, not the vector operations.

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [July 26, 2019, 11:52am UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/8 "2019-07-26T11:52:46Z")

</div>

Thanks, Tamas! I was actually just reading in the McNicholas/Tait book (Data Science with Julia) that splitting up complex/repeated computations into separate functions can result in significant performance gains. Your approach separates the filter/compare piece from the rest, so I’ll give it a shot and see if it’s more performant!

I’m trying to optimize for performance as much as possible because when passing in an array that has hundreds of thousands of items, it is very slow (takes several minutes to complete). I’m going to look into the `compare` function from StringDistances.jl and see if maybe there are some optimizations there that could speed things up for me.

Thanks again.

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [July 26, 2019, 1:43pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/9 "2019-07-26T13:43:36Z")

</div>

I think Tamas’ point is exactly right, `compare` will be your issue here - I asked a similar question [a while ago](https://discourse.julialang.org/t/why-do-these-two-functions-benchmark-the-same/12831) and the advice (rightly as it turned out) was a similar one.

What that means I guess is that it can pay to think a bit more about how you can minimize the number of comparisons you have to do, e.g. normalise strings (lowercase and remove spaces) and remove exact duplicates first, maybe remove duplicates immediately so that they don’t get compared again etc. and any other tricks which might be problem specific!

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [July 26, 2019, 1:55pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/10 "2019-07-26T13:55:42Z")

</div>

Great advice. I am currently implementing a check to see if one string is significantly longer than the other and, if this is the case, I will skip the comparison. For example, “JR Smith” won’t be compared to “Jonathan Reed Smithsonian” because, due to the significant difference in length, the result of the `compare` function won’t meet the threshold that I’m establishing anyways.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [July 26, 2019, 2:01pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/11 "2019-07-26T14:01:19Z")

</div>

> [@mthelm85](#):
>
> I’m going to look into the `compare` function from StringDistances.jl and see if maybe there are some optimizations there that could speed things up for me.

The very first thing I would do before any of this is some profiling on the actual data. Unfortunately, worst case scenarios are O(n^2) for your problem.

> [@nilshg](#):
>
> remove exact duplicates first, maybe remove duplicates immediately so that they don’t get compared again

Yes, this could help if there are a lot of duplicates.

Also, investing in a string comparison function that can bail out early if the difference metric is guaranteed to be above some threshold could be worthwhile.

---

<div class="post-metadata">

**Author:** ![mthelm85](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mthelm85/32/224164_2.png) [@mthelm85](https://discourse.julialang.org/u/mthelm85)\
**Post date:** [July 26, 2019, 2:08pm UTC](https://discourse.julialang.org/t/whats-the-best-way-to-compare-items-in-an-array-to-every-other-item/26806/12 "2019-07-26T14:08:52Z")

</div>

> [@Tamas\_Papp](#):
>
> Also, investing in a string comparison function that can bail out early if the difference metric is guaranteed to be above some threshold could be worthwhile.

This is a really nice idea…I’m not sure I have the ability to execute it, but I’m going to take a look and maybe see if the author of StringDistances.jl is interested in adding this functionality. I think when people are computing string distances for purposes of ranking, they want to compute the actual distance each time, but if the distances are being computed with a threshold in mind (for filtering rather than ranking), the ability to stop the execution as soon as the threshold is met would be awesome.