Finding duplicates in an NSMutableArray

Question

I have a class (colorClass) which holds 2 NSStrings (idNumber and favoriteColor). There is an NSMutableArray (arrayColor) that holds over 50,000 colorClass objects. What is the fastest way to find all duplicate idNumbers from all colorClass objects and return them in an array? Right now I'm using 1 for loop that goes copies arrayColor, then filters the copied array using an NSPredicate. This takes over 5 minutes to sort the array. How can this be done more efficiently?

Answer 1

First question is: does order really matter? If not, then use an NSMutableSet or NSMutableDictionary (depending on what makes sense for your app)

The simplest way to eliminate duplicates is to prevent them from occurring in the first place. Before you add anything to your NSMutableArray, you could check to see if the value already exists. For example:

- (void)addColor:(NSString *)color withID:(NSString *)id {
    NSArray *duplicates = [myArray filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:@"id == %@", id]];
    if ([duplicates count] > 0) {
        // Optionally report an error/throw an exception
        return;
    }
}

Otherwise, you're probably best off getting a list of IDs using valueForKeyPath:, then sorting that array, and then running through it once to look for duplicates. It would go soemthing like this:

- (NSSet *)checkForDuplicateIDs {
    NSArray *allIDs = [myArray valueForKeyPath:@"id"];
    NSArray *sortedIDs = [allIDs sortedArrayUsingSelector:@selector(compare:)];

    NSString *previousID = nil;
    NSMutableSet *duplicateIDs = [NSMutableSet set];
    for (NSString *anID in sortedIDs) {
        if ([previousID isEqualToString:anID]) {
            [duplicateIDs addObject:anID];
        }
        previousID = anID;
    }

    return [[duplicateIDs copy] autorelease];
}

Keep in mind, though, that sorting the list is still, at best, probably an O(n log(n)) operation. If you can at least keep your objects in order in your list, you can avoid the expense of sorting them. Preventing duplicates is best, keeping the list sorted is next best, and the algorithm I gave above is probably the worst.

Answer 2

"Fastest" would require profiling, but my inclination would be to make an NSCountedSet from the array, loop over that and return an array of items from the counted set that have a countForObject: greater than 1.