0

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.

3

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.

  • thanks for your analysis. size of array were just to mention that one is approx. 10 times than the other one. Sorting is a good option :) – Kashif Apr 27 '16 at 11:05
  • @Kashif Glad I could help. Also, if this solved your problem, be sure to click the checkmark to mark this answer as "accepted". – Ixrec Apr 27 '16 at 11:23
  • This is a case where taking a step back and looking for a better solution usually isn't premature optimization. If the search term is fairly simple and the language of your choice perhaps supports something like keyed collections your algorithm becomes trivial in which case the solution is far less errorprone even if it isn't noticeably faster. – Bent Apr 27 '16 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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