Search list items from other list, better way?

Question

Today I have to search items of list from another list individually. I am just thinking about some better approach. Below is scenario described.

Lets say I have two arrays, arr1 having 100 elements (may have duplicate entries) and arr2 having 1000 unique elements. now i need to find elements of arr1 from arr2 and perform some action on it. Should i loop through arr1 items and then search them in arr2 and perform desired action. or iterate on arr2 and search its items from arr1 and if found, perform desired action on arr2 item. which will be efficient way? Obvious choice seems to be first way, but i wanted to compare its perofrmance (dis)advantages over the other.

In my opinion both will be almost same.

Answer 1

If we refer to arr1's size as m and arr2's size as n, and assuming that by "search" you mean a simple linear search, then the naive brute force algorithm you're describing will take O(nm) time. It is true that which array you iterate over has no effect on this; you're only choosing between n iterations of an O(m) search versus m iterations of an O(n) search.

The obvious way to do this faster than O(nm) is don't use linear searches at all, but pre-process arr1 to make faster searches possible. By far the simplest option is to sort arr1 at the beginning, and then use binary searches, which should get the full search down to O(n*log(m)), so I'd start with that. If even that isn't enough, then I'd look into hash tables. Given an ideal hash function (which depending on your data may be hard or even impossible), that could theoretically get the full search down to amortized O(m + n).

By the way, 100*1000 comparisons is nothing on a modern computer. Make sure this code is actually causing performance problems before trying to optimize it.