cocoa - 在 NSMutableArray 中查找重复项

Question

我有一个类(colorClass)，其中包含2个NSString(idNumber和favoriteColor)。有一个 NSMutableArray (arrayColor)，它包含超过 50,000 个 colorClass 对象。从所有 colorClass 对象中查找所有重复的 idNumber 并将它们返回到数组中的最快方法是什么？现在我正在使用 1 个 for 循环来复制 arrayColor，然后使用 NSPredicate 过滤复制的数组。对数组进行排序需要 5 分钟以上。如何才能更有效地做到这一点？

Answer 1

第一个问题是:顺序真的很重要吗？如果没有，则使用 NSMutableSet 或 NSMutableDictionary (取决于对您的应用有意义的方式)

消除重复的最简单方法是从一开始就防止它们发生。在向 NSMutableArray 添加任何内容之前，您可以检查该值是否已存在。例如:

- (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;
    }
}

否则，您最好使用 valueForKeyPath: 获取 ID 列表，然后对该数组进行排序，然后运行一次以查找重复项。它会是这样的:

- (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];
}

但请记住，对列表进行排序充其量仍然可能是一个 O(n log(n)) 操作。如果您至少可以将对象按顺序排列在列表中，则可以避免对它们进行排序的费用。防止重复是最好的，保持列表排序是第二好的，而我上面给出的算法可能是最差的。