CODEWITHSUNDEEP
arraysjulia
Alec
Alec

Reputation: 4482

How to count matches in two arrays?

If I have two arrays, how can I count the number of matching elements?

E.g. with

x = [1,2,3,4,5]
y = [3,4,5,6]

I'd like to get the count (3) of the three matching elements 3,4,and 5.

Upvotes: 3

Views: 518

Answers (3)

Bill
Bill

Reputation: 6086

A lot depends on the sizes of the arrays. If the arrays are just a few dozen integers in length, a simple O(N^2) count wins over the count_matches sorting method and the intersect count_matches0 methods above, because of zero allocation setup time:

function count_matches2(x, y)
    count(n -> any(==(n), x), y)
end

@btime count_matches(x, y)  setup=(x = rand(1:100,50); y = rand(1:100,50)) evals=1
@btime count_matches0(x, y) setup=(x = rand(1:100,50); y = rand(1:100,50)) evals=1
@btime count_matches2(x, y)  setup=(x = rand(1:100,50); y = rand(1:100,50)) evals=1

2.400 μs (0 allocations: 0 bytes)
3.700 μs (10 allocations: 3.59 KiB)
1.500 μs (0 allocations: 0 bytes)

The simplicity advantage vanishes with arrays of size > 1000.

Upvotes: 3

AboAmmar
AboAmmar

Reputation: 5559

The following algorithm can be near 4X faster than Set intersection. The idea is to sort the arrays first, that has O(n log n) complexity for each array. Then merge-compare the sorted versions for equal elements, that has O(m + n) linear complexity. So, the overall algorithm complexity can be O(n log n).

This algorithm counts duplicate elements into the final matches result, but can be modified with a small overhead to behave similarly to sets. The modification can include adding a variable to keep track of the last matched elements and increment the number of matches only for new different matched pairs.

function count_matches(x,y)
    sort!(x) # or x = sort(x) 
    sort!(y) # or y = sort(y)
    i = j = 1
    matches = 0
    while i <= length(x) && j <= length(y)
        if x[i] == y[j]
            i += 1 
            j += 1
            matches += 1
        elseif x[i] < y[j]
            i += 1
        else 
            j += 1
        end
    end 
    matches
end

Comparing with:

function count_matches0(x,y)
    length(intersect(Set(x), Set(y)))
end

and timing with n = 10000 arrays, we get:

@btime count_matches(x, y)  setup=(x = rand(1:1000,10000); y = rand(1:1000,10000)) evals=1
@btime count_matches0(x, y) setup=(x = rand(1:1000,10000); y = rand(1:1000,10000)) evals=1
  246.700 μs (31 allocations: 338.31 KiB)
  63.200 μs (2 allocations: 15.88 KiB)

Upvotes: 2

Sash Sinha
Sash Sinha

Reputation: 22370

You can use intersect:

julia> x = [1, 2, 3, 4, 5]
5-element Vector{Int64}:
 1
 2
 3
 4
 5

julia> y = [3, 4, 5, 6]
4-element Vector{Int64}:
 3
 4
 5
 6

julia> intersect(Set(x), Set(y))
Set{Int64} with 3 elements:
  5
  4
  3

julia> length(intersect(Set(x), Set(y)))
3

Upvotes: 2

Related Questions