Filtering an NSSet based on equality with different objects in another NSSet

Question

I have 2 types of objects.

Class A is a subclass of NSManagedObject. Class B is a subclass of NSObject.

S(A) is an NSSet containing objects of class A. S(B) is an NSSet containing objects of class B.

I have a custom comparator on class A to figure out if it matches an object of class B.

I need to filter S(A) such that after the filtering operation, only those objects remain in S(A) which have a valid match in S(B).

My current naive solution iterates over S(A), and for each object iterates over S(B) which has a time complexity of O(mn) (m is the size of S(A), n is the size of S(B)).

The biggest constraint here is that A is a subclass of NSManagedObject and therefore I cannot override the -isEqual: and -hash methods to take advantage of the -intersectSet: method on NSMutableSet.

I'm looking for a solution better than O(mn). Any leads would be greatly appreciated.

Answer 1

I was able to find an O(m+n) solution to this problem by using the following method.

The custom comparator between class A and B relied on a string comparison and an integer equality.

Lets say these properties are

• NSString *s
• NSInteger i

I created an NSMutableDictionary with objects of class A and key as a hash of the string s and integer i. This process is O(m) as it involves iteration over S(A).

After this I iterate over S(B), and create the same hash using the string s and integer i from objects of class B, and look up objects in the above create NSMutableDictionary. If a match exists, I perform desired operation. This process is O(n).

While this solution takes a larger space, but is an order of magnitude faster.