# Fast hamming distance function in Julia that returns a distance matrix

**URL:** <https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716>\
**Category:** Performance\
**Tags:** question, distances\
**Created:** [February 21, 2021, 1:34pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716 "2021-02-21T13:34:02Z")\
**Posts on this page:** 13\
**Page:** 1

<div class="post-metadata">

**Author:** ![giac](https://avatars.discourse-cdn.com/v4/letter/g/77aa72/32.png) [@giac](https://discourse.julialang.org/u/giac)\
**Post date:** [February 21, 2021, 1:34pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/1 "2021-02-21T13:34:02Z")

</div>

I am trying to compute the hamming distance on a very large dataset. I need to get back a distance matrix between rows in order to run further analysis on this matrix.

For my purposes, it is useful that the data are stored in a DataFrame type.

```
using DataFrames

```

The data looks something like this

```
a = [1 0 1 0 ; 1 1 1 1; 0 0 0 0; 0 0 0 0 ; 0 0 0 1]

df = convert(DataFrame, a);

nrows = size(df, 1)
ncols = size(df, 2)

```

I made a function in `Julia` that returns a distance matrix

```
function hamjulia(df)

    nrows = size(df, 1)
    ncols = size(df, 2)
    m, n = nrows, nrows
    A = fill(0, (m, n))

    for i in 1:nrows
    for k in 1:nrows
        
        v = 0
        for j in 1:ncols
            if df[i,j] != df[k,j]
            v += 1
            end
        end
        A[i,k] = v
    end
    end
    return A
end

p = hamjulia(df)
p

```

My issue is that this code is slow compared to some R packages. For instance, when I compared this function to the `rdist` package, `rdist(df, metric = 'hamming')`, `R` is faster.

How could I make this code really efficient? Especially that I would need to run it on a very large dataframe. I tried the package `Distances` but the documentation is too scarce.

Also, does anyone know if there is an efficient code for the `Needleman–Wunsch algorithm`?

Thanks.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 21, 2021, 1:56pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/2 "2021-02-21T13:56:19Z")

</div>

> [@giac](#):
>
> I am trying to compute the hamming distance on a very large dataset. I need to get back a distance matrix between rows in order to run further analysis on this matrix.

I would first convert your dataset into an array of [BitVectors](https://docs.julialang.org/en/v1/base/arrays/#Base.BitArray). Then you can compute the Hamming distance between two BitVectors very cheaply using bitwise operations — for example, see the code posted [here](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/6). Since conversion is O(n) and computing the distance matrix is O(n^2) where n is the size of your dataset, it is worth it to pay the conversion cost in order to speed up the distance computation.

(Note also that you can trivially double the speed of your code since `A` is symmetric — you only need to compute the Hamming distance once for each pair.)

(How large is your dataset? It can’t have that many rows or you wouldn’t be able to store the distance matrix. If you have ≤ 64 columns you can convert your data to an array of `UInt64` bitstrings, which will be even faster than `BitVector`s.)

---

<div class="post-metadata">

**Author:** ![giac](https://avatars.discourse-cdn.com/v4/letter/g/77aa72/32.png) [@giac](https://discourse.julialang.org/u/giac)\
**Post date:** [February 21, 2021, 2:02pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/3 "2021-02-21T14:02:38Z")

</div>

Thanks for your reply. I will try this conversion.  
What do you mean by unable to store the distance matrix? It has about a million rows.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 21, 2021, 2:03pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/4 "2021-02-21T14:03:53Z")

</div>

> [@giac](#):
>
> What do you mean by unable to store the distance matrix? It has about a million rows.

If you have a million rows, then your distance matrix is 10^6 \times 10^6, which will require 8 terabytes of memory. Probably you need to re-think your algorithms.

---

<div class="post-metadata">

**Author:** ![giac](https://avatars.discourse-cdn.com/v4/letter/g/77aa72/32.png) [@giac](https://discourse.julialang.org/u/giac)\
**Post date:** [February 21, 2021, 2:09pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/5 "2021-02-21T14:09:24Z")

</div>

Thanks. What do you think would be a reasonable size then with this code? 10,000? 100,000?

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 21, 2021, 3:56pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/6 "2021-02-21T15:56:13Z")

</div>

> [@giac](#):
>
> What do you think would be a reasonable size then with this code? 10,000? 100,000?

The memory usage for an n\times n matrix of 64-bit integers is 8n^2 bytes. If you can afford to use 16GB of memory, that comes out to about n = 44,000 rows.

As I said, you really need to re-think your algorithms if you are relying on computing this matrix explicitly for huge datasets. Think about how you are going to _use_ this matrix (you haven’t said), e.g whether you can compute the entries as needed, and in general how the computational and memory costs grow with n. If you are working with large data, you need to think like a computer scientist.

> Also, does anyone know if there is an efficient code for the Needleman–Wunsch algorithm?

Maybe look at [GitHub - BioJulia/BioAlignments.jl: Sequence alignment tools](https://github.com/BioJulia/BioAlignments.jl)

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [February 21, 2021, 4:19pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/7 "2021-02-21T16:19:18Z")

</div>

As an additional comment, please consider searching packages with this functionality already before re-inventing the wheel. For example, the widely used Distances.jl package has a Hamming distance that produces the distance as you want: [GitHub - JuliaStats/Distances.jl: A Julia package for evaluating distances (metrics) between vectors.](https://github.com/JuliaStats/Distances.jl)

---

<div class="post-metadata">

**Author:** ![giac](https://avatars.discourse-cdn.com/v4/letter/g/77aa72/32.png) [@giac](https://discourse.julialang.org/u/giac)\
**Post date:** [February 21, 2021, 4:37pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/8 "2021-02-21T16:37:59Z")

</div>

I did try to use this package, but I couldn’t find in the documentation on how to retrieve a distance matrix. The documentation of this package is sparse. But thanks.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [February 21, 2021, 4:49pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/9 "2021-02-21T16:49:58Z")

</div>

pairwise(Hamming(…), dataframe, dims=1) should do it. Maybe you need to convert the DataFrame to Matrix(dataframe). The dims=1 specifies the calculation over rows

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [February 21, 2021, 5:00pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/10 "2021-02-21T17:00:13Z")

</div>

> [@juliohm](#):
>
> For example, the widely used Distances.jl package has a Hamming distance that produces the distance as you want: [GitHub - JuliaStats/Distances.jl: A Julia package for evaluating distances (metrics) between vectors.](https://github.com/JuliaStats/Distances.jl)

(It doesn’t seem to have an optimized Hamming method for BitArrays; this might make a useful PR.)

---

<div class="post-metadata">

**Author:** ![cgeoga](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cgeoga/32/216186_2.png) [@cgeoga](https://discourse.julialang.org/u/cgeoga)\
**Post date:** [February 21, 2021, 5:33pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/11 "2021-02-21T17:33:38Z")

</div>

If you can’t store the whole matrix, there’s also a few convenient options for an extra abstraction that might make working with the matrix feel the same. The package `LazyArrays.jl` implements something like this, I’m pretty sure, and [KernelMatrices.jl](https://bitbucket.org/cgeoga/kernelmatrices.jl/src/master/) (disclaimer: this is my project) provides exactly this abstraction because I am constantly working with matrices that are way too large to store in RAM but whose elements I need to access in a consistent way with regular `Matrix` objects:

```julia
using KernelMatrices

# This is the optimmized hamming distance that stevengj referenced.
function hamming(A::BitArray, B::BitArray)
    #size(A) == size(B) || throw(DimensionMismatch("sizes of A and B must match"))
    Ac,Bc = A.chunks, B.chunks
    W = 0
    for i = 1:(length(Ac)-1)
        W += count_ones(Ac[i] ⊻ Bc[i])
    end
    W += count_ones(Ac[end] ⊻ Bc[end] & Base._msk_end(A))
    return W
end

example_points = [BitArray(rand(Bool, 8)) for _ in 1:1000]
K = KernelMatrix(example_points, example_points, hamming)

# K[1:10, 1:10], K[3,6], K[:,10], etc works as expected. 
# But K is really just a struct that stores the function and the points, 
# not a big memory buffer for the matrix elements.

```

As a disclaimer, KM is GPL licensed, not officially registered, and probably not as optimized as it could be. So maybe `LazyArrays` or some other similar package would be a better choice. I just am not familiar with those, so maybe take the KM example here primarily as a demonstration of this particular abstraction.

EDIT: if you think you might use this, let me know and I’ll do a pass over the source and plop in whatever low-hanging optimizations aren’t in there currently that would apply to what you’re doing. Of course I welcome contributions from anybody and would love that even more, but to some degree I mostly make improvements to the base functionality when I have an excuse to, so that’s always invited.

---

<div class="post-metadata">

**Author:** ![lungben](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lungben/32/12314_2.png) [@lungben](https://discourse.julialang.org/u/lungben)\
**Post date:** [February 21, 2021, 6:13pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/12 "2021-02-21T18:13:46Z")

</div>

I do not know if this is the most efficient way for matrices, but for pair-wise Hamming distance this way was the fastest I could find:

> [@Optimization: How to make sure XOR is performed in chunks](https://discourse.julialang.org/t/optimization-how-to-make-sure-xor-is-performed-in-chunks/33947/32):
>
> A bit late to the party, but I just had a similar use case today. The fastest method I could find was working on UInt8 instead of BitArrays, count\_ones and LoopVectorization: function hamming\_distance(h1, h2) s = 0 @avx for i = 1:length(h1) s += count\_ones(xor(h1[i], h2[i])) end s end h1 = Vector{UInt8}(randstring(hash\_length)) h2 = Vector{UInt8}(randstring(hash\_length)) julia\> @btime hamming\_distance($h1, $h2) 11.813 ns (0 allocations: 0 bytes) The method above (b…

---

<div class="post-metadata">

**Author:** ![giac](https://avatars.discourse-cdn.com/v4/letter/g/77aa72/32.png) [@giac](https://discourse.julialang.org/u/giac)\
**Post date:** [February 21, 2021, 6:20pm UTC](https://discourse.julialang.org/t/fast-hamming-distance-function-in-julia-that-returns-a-distance-matrix/55716/13 "2021-02-21T18:20:28Z")

</div>

Thank you for this. My next step is to run clustering analysis on the distance matrix. Is this approach helpful for this? Sorry I am not a computer scientist, so I don’t think I am able to contribute to your project, but it seems really interesting.