keep unique object's id in NSMutableArray

Question

I have NSMutableArray that hold sorted(time) objects. each object has unique URL string ID.

From performance perspective, what is better approach ?

1. using filteredArrayUsingPredicate to check if object URL is already exist if not add to array.
2. using NSMutableDictionary and NSMutableArray. each time I add an object that not exist, I also store it in the dictionary. before adding new object, I'll check the NSDictionary key if the object id exist.

I think using NSDictionary for checking is less expensive, but I prefer to understand why.

Is there better approach for this case ? Thanks in advance.

Answer 1

Have you considered to use NSMutableSet to keep the unique URL string ID?

Since you are already storing the objects in the sorted array, you don't need to store them again in the dictionary. Just keep the string in a set. Checking sets with "contains" is very fast. The speed of "contains" in a set should be near constant, no matter how many items it contains.

You can also consider switching to a NSMutableOrderedSet instead of an Array altogether. It will both keep items unique and sorted.

You can see more about Collection class performance here https://www.objc.io/issues/7-foundation/collections/

Answer 2

I can recommend use NSOrderedSet (if u need order) or NSSet (otherwise):

NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:yourArray];
NSArray *arrayWithoutDuplicates = [orderedSet array];

Or, you can use operators from KeyValueCording:

uniquearray = [yourarray valueForKeyPath:@"@distinctUnionOfObjects.self"];

If you wanna remove duplicates by your property, like name, its really simple via that operator:

@distinctUnionOfObjects.name

NSSet declares the programmatic interface for static sets of distinct objects. You establish a static set’s entries when it’s created, and thereafter the entries can’t be modified. NSMutableSet, on the other hand, declares a programmatic interface for dynamic sets of distinct objects. A dynamic—or mutable—set allows the addition and deletion of entries at any time, automatically allocating memory as needed.

So, you can read about Cocoa Collections in Apple Docs

If you wanna insert unique object to Array, it costs O(1)-O(N), but if u wanna insert unique object to Set, it costs 0(1), it is instantly. Read about complexity here

For this case, Set faster than Array.