在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中查找重複項

回答

相關問題