CODEWITHSUNDEEP
cstringperformancealgorithm
user1912027
user1912027

Reputation: 45

Comparing two String array in most efficient way

This problem is about searching a string in a master array (contains the list of all UIDs). The second array contains all the strings to be searched.

For example:

First array(Master List) contains: UID1 UID2 UID3... UID99

Second array contains: UID3 UID144 UID50

If a match is found in first array then 1 is returned otherwise 0 is return. So the output for the above example should be 101.

What could be the most efficient approach (targeting C) to solve the above keeping in mind that the traditional way dealing with this would be n^2!!!

Upvotes: 0

Views: 658

Answers (4)

Maxime Chéramy
Maxime Chéramy

Reputation: 18831

There are mainly two good approaches for this problem:

  • Use a binary search: a binary search requires the UIDs in the first array to be sorted and allows you to find a solution in O(log n) where n is the number of elements in the master array. The total complexity would be O(m log n) with m the number of elements to be searched.

  • Use a hashmap: You can store the elements of the master array in a hashmap (O(n)) and then check whether your elements of the second array are in the hashmap (O(m)). The total complexity would be O(n+m).

While the complexity of the second approach looks better, you must keep in mind that if your hash is bad, it could be O(m*n) in the worst case (but you would be very very unlikely). Also you would use more memory and the operations are also slower. In your case, I would use the first approach.

Upvotes: 0

Leeor
Leeor

Reputation: 19706

Another option is to build a hash for the strings in the Master list, it's a single O(M) (assuming the lengths are O(1)), then assuming the hash is distributed evenly, searching a single element should take on average O(M/S), with S being the size the hash (the even distribution means that on average this is the amount of elements mapping into the same hash entry). You can further control the size to fine tune the trade off between space and efficiency

Upvotes: 0

unwind
unwind

Reputation: 399813

Efficient in terms of what?

I would go with @Trying's suggestion as a good compromise between decent running speed, low memory usage, and very (very!) low complexity of implementation.

Just use qsort() to sort the first master array in place, then use bsearch() to search it.

Assuming n elements in the master array and m in the second array, this should give O(m*log n) time complexity which seems decent.

Upvotes: 0

Trying
Trying

Reputation: 14278

sort the master string array and do binary search.

Upvotes: 1

Related Questions