12

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.

3
  • 2
    Um, just hash the names? Or do you need their positions in the list as well?
    – Ordous
    Apr 28, 2015 at 11:49
  • Well, I just need to merge the informations associated with the names, from booth sources.
    – cap7
    Apr 28, 2015 at 11:51
  • 50k and 400k aren't particularly big lists. two foreach cycles or Linq this will get you O(n^2) time complexity and yes that is a slow approach.
    – Pieter B
    Apr 28, 2015 at 12:29

4 Answers 4

9

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(log2^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).

1
  • I've created an HashSet with C#, even in a two foreach cycles the program runs 10x faster then comparing strings directly.
    – cap7
    Apr 29, 2015 at 8:16
9

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) );
4
  • That is good, but I've forget to mention that the same name can appear multiple times on the lists, with different information associated. Clearing the lists might not be a good idea.
    – cap7
    Apr 28, 2015 at 13:09
  • +1 @cap7: This is what I would do - sort both lists and use a merge loop. You're not clearing the lists, just indexing through them. Apr 28, 2015 at 20:27
  • @cap7: If one of the lists can contain duplicates (e.g. 6 copies of "Fred" in the long list) then it won't matter. If both lists can contain duplicates (e.g. 6 copies of "Fred" on the long list and 3 copies of "Fred" on the short list) then you'll get duplicated matches. To avoid that the most efficient way is to remove duplicates while sorting (sorting also has a "compare if earlier, equal or later" step where you can discard or mark the entry as "to be skipped later" if equal).
    – Brendan
    Apr 29, 2015 at 6:49
  • Since I just need the names that match I guess I can ignore the duplicates. Then I can get all the "Freds" from both lists using a Linq expression, and having the complete set of possible correspondences.
    – cap7
    Apr 29, 2015 at 8:21
2

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.

1
  • If the big list is still unsorted this I don't think there's need to sort the small list, and the big-o would be the same. Or no?
    – trusktr
    Apr 15, 2020 at 21:04
0

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.

4
  • 3
    he wants to join on names (which are most likely strings), and relational databases are particularly bad at joining on strings. not to mention that you'd have to send your data to the database, pair it and then read it back. not a pretty prospect.
    – devnull
    Apr 28, 2015 at 12:26
  • @devnull: If the lists are that big and they're used more than once, they probably should be put into a database from square one.
    – Blrfl
    Apr 28, 2015 at 12:36
  • 1
    @Blrfl it's a question about algorithms, not databases. one should not assume the presence of a database engine to solve a problem that doesn't need a database.
    – devnull
    Apr 28, 2015 at 12:39
  • I came here having task to find difference between two tables in my DB Mar 14, 2018 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.