VB.NET array intersection

Question

This may be terribly trivial, but it's hard for me to find an answer that runs in less than 2 times. Let's say I have two string arrays, and I want to know which strings exist in both arrays. How can I do this, efficiently, in VB.NET or is there a way to do this differently than double looping?

Answer 1

An easy way (apart from .NET 3.5) is to drop rows from one array in the hash table, and then loop through another array that checks the hash table. This should be much faster than searching for n ^ 2.

Answer 2

If you sort both arrays, you can go through them each time to find all the matching rows.

Pseudo Code:

while(index1 < list1.Length && index2 < list2.Length) { if(list1[index1] == list2[index2]) { // You've found a match index1++; index2++; } else if(list1[index1] < list2[index2]) { index1++; } else { index2++; } } 

Then you reduced it to the time needed for sorting.

Answer 3

Sort both lists. Then you can know with confidence that if the next entry in list A is "cobble" and the next entry in list B is "defined", then "cobble" is not in list B. Just move the pointer / counter so that the list has more low ranked result and climb the ranking.

For instance:

List 1: D, B, M, A, I
List 2: I, A, P, N, D, G

sorted by:

List 1: A, B, D, I, M
List 2: A, D, G, I, N, P

A vs A → match, store A, advancing as
B vs D → B D vs D → match, store D, advance both
I am against G → I> G, moving forward 2
I vs i → match, store I, promoting how
M vs N → M List 1 has no more items, drop it.

List of matches: A, D, I

2 sorts the list O (n log (n)), and O (n) comparisons do this O (n (log (n) + 1)).

Answer 4

If one of the arrays is sorted, you can perform a binary search in the inner loop, this will reduce the time to O(n log n)