Find the length of the intersection of two lists including duplicates

Question

I have 2 Lists. The first one includes all the numbers from 1 to 10.

listA={1,2,3,4,5,6,7,8,9,10}

The second includes random numbers, like this:

listB={2,10,2,5,7,15,1000,7,25,600}

I want to find an algorithm that will take any number of the second list listB and compare it to all numbers in listA. If the number in listB is equal to a number in listA, I"ll get 1 as a result. If not it will be 0. As a final result I would like to sum all equal numbers.

Here, for example we have the result 6 because we can find 2 (twice), 7 (twice), 5 and 10 in the two lists. I need a general way because my lists includes data of 10,000 numbers.

Answer 1

This should be much more efficient for anything beyond small lists:

(Tr[Tally[#1~Join~#2][[;; Length@#1, 2]]] - Length[#1]) &[listA, listB]

Answer 2

The previous answers seem to have been addressing a rather different (or much more generalized) sort of problem, because as I see this now, we have the following problem statement:

len = 10; (* let's have 10 to be specific, but this is an arbitrary positive integer *)
max = 10^3; (* maximum value of numbers in listB *)
listA = Range[len];
listB = RandomInteger[{1, max}, len];

Then of course a member of listB is a member of listA if it is less than (or equal to) len. So to get the matching numbers we do:

Pick[listB, # <= len &/@ listB]
(* {2, 10, 2, 5, 7, 7} *)

And to get the count of that, simply

Length@%
(* 6 *)

This is slower than @ciao's answer. However, this is almost 2 orders of magnitude faster:

Pick[listB, Sign[listB - len - 1], -1]

And this one is a tiny bit slower, but slightly more general (handles negative integers properly):

Pick[listB, Quotient[listB, len, 1], 0]

Here are the timings for the solutions:

len = 1000000;
max = 10000000;
listA = Range[len];
listB = RandomInteger[{1, max}, len];
(Tr[Tally[#1~Join~#2][[;; Length@#1, 2]]] - Length[#1]) &[listA, 
   listB] // AbsoluteTiming // First
Pick[listB, # <= len & /@ listB] // AbsoluteTiming // First
Pick[listB, Sign[listB - len - 1], -1] // AbsoluteTiming // First
Pick[listB, Quotient[listB, len, 1], 0] // AbsoluteTiming // First

0.556392 (* ciao *)
0.803501 (* boolean comparison *)
0.0136436 (* Sign *)
0.0171063 (* Quotient *)

Be aware, that while my solution is easily adaptable to the variations of the problem, as stated right now, if listA is also to have random numbers, as originally suggested, ciao's way is probably the fastest (and IMO, really elegant).

Answer 3

I am not sure what the exact aim is. In the following it is assumed:

• 2 random samples from a range of integers (distinct elements) of equal length

• the aim is to determine size of intersection:

  f[n_, s_] := Module[{a = RandomSample[Range[n], s], b = RandomSample[Range[n], s], j, u, c, r}, c = Intersection[a, b]; r = # -> Style[#, Bold, Red] & /@ c; {a /. r, b /. r, Length@c}]

Much of above is just window dressing.

Examples:

Grid[Table[f[10, 5], {5}]]

or

Grid[Table[f[20, 10], {5}]]

Answer 4

Now that the question has been restated, you can use a shortened version of the answer suggested by mgamer,

B = {2, 10, 2, 5, 7, 15, 1000, 7, 25, 600};
A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Count[B, #] & /@ A // Total
(* 6 *)

Or you could use MemberQ and Boole,

Boole@MemberQ[A, #] & /@ B // Total
(* 6 *)

Or Select, MemberQ, and Length

Select[B, MemberQ[A, #] &] // Length
(* 6 *)

If speed is an issue, and the B list is very large, then the Boole method is slightly faster, and the Select method is by far the slowest.

SeedRandom[28];
A = Range[100];
B = RandomInteger[10000, 10^6];
Count[B, #] & /@ A // Total // AbsoluteTiming
Boole@MemberQ[A, #] & /@ B // Total // AbsoluteTiming
Select[B, MemberQ[A, #] &] // Length // AbsoluteTiming
(* {0.113349, 10012} *)
(* {0.135395, 10012} *)
(* {4.06878, 10012} *)

If the A list gets larger, then the difference between the Count and Boole methods is minimal, but Select is much worse,

SeedRandom[28];
A = Range[1000];
B = RandomInteger[10000, 10^6];
Count[B, #] & /@ A // Total // AbsoluteTiming
Boole@MemberQ[A, #] & /@ B // Total // AbsoluteTiming
Select[B, MemberQ[A, #] &] // Length // AbsoluteTiming
(* {0.896079, 100334} *)
(* {0.865092, 100334} *)
(* {25.8521, 100334} *)