在NSMutableArray中查找重复项

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

来源

2009-10-19 SeriouslyBob

您是否想过改用NSMutableSet？集合首先不允许重复，所以你的问题不会存在。然而，如果颜色的顺序很重要，那么一组将不起作用（因为组没有排序的概念）。我不确定你的具体情况。

来源

2009-10-19 17:30:09

或者可能是'NSMutableDictionary'，因为我们正在谈论的键值对.... –

他存储对象以键值对，而不是一个原始的对。字典是没有意义的。 –

我不同意。大量的对象，每个对象都是一个关键+值，他关心重复查找，这对于字典来说似乎是一个理想的情况。除非在其他地方有一些令人信服的需求，因为它们都是按顺序排列的。 –

“最快”需要分析，但我的倾向是从数组，循环，使一个NSCountedSet从数集中返回的项目的数组有一个countForObject:大于1

来源

2009-10-19 17:30:16 Chuck

第一问题是：订单真的很重要吗？如果没有，则使用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列表。它会去soemthing这样的：

- (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))操作。如果你至少可以在你的列表中保持你的对象的顺序，你可以避免排序他们的花费。防止重复是最好的，保持列表排序是次佳，而我上面给出的算法可能是最差的。

来源

2009-10-19 18:39:48 Alex

因此，对我早些时候的评论略加阐述：从这个问题来看，我不清楚这个数据实际使用的上下文。尤其是，是否需要将所有这些对象都放在一个很长的阵列中。如果没有，那么字典可能是更好的数据结构选择而不是数组。由于字典固有地是键值数据结构，所以ColorClass可能完全被消除，但是我在这里假设除了我们从问题中知道的信息外，还有其他原因可以保留它。

如果重复不应该被允许在所有发生，那么字典可存储的单品，而代码可能是这个样子：

// colors is an NSMutableDictionary - (ColorClass*)addColorIfPossible:(ColorClass*)color { ColorClass *existingColor = [[colors objectForKey:[color idNumber]] retain]; if(existingColor == nil) { [colors setObject:color forKey:[color idNumber]]; } return [existingColor autorelease]; }

如果允许重复，但存在对具有共同ID快速获取所有的对象，那么无论阵列或组的字典可以工作：

// colors is an NSMutableDictionary - (void)addColor:(ColorClass*)color { NSMutableSet *colorSet = [colors objectForKey:[color idNumber]]; if(!colorSet) { // kInitialSetCapacity is a constant with some reasonable value you choose colorSet = [NSMutableSet setWithCapacity:kInitialSetCapacity]; [colors setObject:colorSet forKey:[color idNumber]]; } [colorSet addObject:color]; } - (NSSet*)findDuplicatesForID:(NSString*)idNumber { // returns nil if no colors with that id, but could // return an empty set instead with little effort return [[[colors objectForKey:idNumber] copy] autorelease]; }

如果有必要在应用都有整体顺序的颜色的巨大列表，和快速查找重复，然后经典的空间vs.时间折衷来了：只使用一个数组，或维护这个数组和字典。

来源

2009-10-21 12:43:12

NSMutableSet *uniqueSet = [NSMutableSet setWithArray:arrayOfDuplicates]; 
    arrayOfDuplicates = [uniqueSet allObjects];

来源

2010-11-10 00:46:42 Sahil

这可能会更快：

if ([theArray containsObject:theNumber]) { 
// remove object 
}

来源

2011-05-19 10:56:40 nicc

在NSMutableArray中查找重复项

回答

相关问题