List comparing techniques for faster performance

Question

I need to cross names from two lists, and find all occurrences of one name in the other. The lists are too big, one have 50k elements and the other 400k.

For a small list I would use two foreach cycles or Linq, but I can't be running the program for days.

What is your advice to perform a fast comparisons?

EDIT: In some cases I need to find more than occurrence on the second list, by other words, all the names are repeated and have different information associated. Then the intention is to merge the information from the two sources.

Answer 1

My suggestion would be to slurp the large list into a hash set, then use that to match items from the small list.

A hash set is a structure that stores elements in an indexable memory structure, like an array, where the position of the element is equal to some hash value calculated using the object. That means that looking for a value in the hashset is a relatively fast operation; calculate the hash of the object you're looking for, go to that index, and check the actual objects stored there, which for a good implementation will be a very small number (hashset implementations have to strike a balance between the size of the hash and therefore the number of first-dimension elements, and the number of collisions and therefore the average number of items in each element).

Ideally, hashsets approach a constant lookup time (specifically it's O(log_2^HN) where H is the bitsize of the hash function, so for all N < 2^H it's effectively constant), so overall, your matching algorithm would approach linear complexity. Two major downsides are first that unless you have access to a built-in efficient implementation (Java's HashMap is built on this structure, as is .NET's Dictionary class), you have to roll your own which is quite a bit of code, and second, hashsets are real memory hogs because there's virtually guaranteed to be a lot of empty spaces in the array unless your implementation varies its hash function based on expected or actual capacity (which could, if naively done, involve re-hashing every element several times as the first dimension is extended to limit growth in the second dimension).

Answer 2

Sort both lists with an efficient sorting algorithm (or ensure that the lists are "pre-sorted" by whoever/whatever created them).

Then, if the first name in both lists is the same you've found a match, otherwise discard whichever name is "earlier"; and do that until one of the lists are empty.

Some crude pseudo-code:

    do {
        status = compare(shortList[i], longList[j]);
        if(status == EQUAL) {
            // Found match!
            i++;
            j++;
        } else if(status == EARLIER) {
            // No match, discard first entry in short list
            i++;
        } else {
            // No match, discard first entry in long list
            j++;
        }
    } while( (i < shortListEntries) && (j < longListEntries) );

Answer 3

Sort the small list with an efficient sorting algorithm, traverse the big list and for every item in the big list use a binary search to find whether there's a matching item in the small list.

Answer 4

Finding things in one set that match those in another set and merging data is something that relational databases excel at. If this is something you need to do a lot, loading your lists into tables in your choice of SQL DB is probably your best option.