Поиск дубликатов в NSMutableArray

Question

У меня есть класс (colorClass), который содержит 2 NSStrings (idNumber и favoriteColor). Существует NSMutableArray (arrayColor), который содержит более 50 000 объектов colorClass. Каков самый быстрый способ найти все дубликаты idNumbers из всех объектов colorClass и вернуть их в массив? Прямо сейчас я использую цикл 1 для цикла, который копирует arrayColor, а затем фильтрует скопированный массив с использованием NSPredicate. Это занимает более 5 минут, чтобы отсортировать массив. Как это можно сделать более эффективно?

Answer 1

Вы когда-нибудь думали об использовании NSMutableSet? Наборы не позволяют дублировать в первую очередь, поэтому ваша проблема не будет существовать. Однако набор не будет работать, если порядок цветов будет иметь значение (поскольку наборы не имеют понятия упорядочения). Я не уверен в вашем конкретном случае.

Answer 2

«быстрый» потребует профилирования, но моя склонность будет сделать NSCountedSet из массива, огибать, что и возвращает массив элементов из считанного набора, имеет countForObject: больше 1.

Answer 3

Первых вопрос: действительно ли порядок? Если нет, используйте 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:, то сортировка этого массива, а затем проходит через него один раз, чтобы искать дубликаты. Он бы 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)) операцию. Если вы можете как минимум сохранить свои объекты в своем списке, вы можете избежать затрат на их сортировку. Предотвращение дубликатов лучше всего, поэтому сортировка списка лучше, а алгоритм, который я дал выше, является, вероятно, наихудшим.

Answer 4

Итак, чтобы немного рассказать о моих предыдущих комментариях: мне непонятно, из контекста, в котором эти данные используются. В частности, необходимо ли сохранить все эти объекты в большом длинном массиве. Если этого не происходит, словарь может быть лучшим выбором структуры данных вместо массива.

Поскольку словари являются неотъемлемо важными структурами данных, 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]; 
} 

Если есть необходимость в приложении к как имеют гигантский список цветов в общем порядке, и, чтобы быстро найти дубликаты, а затем классическое пространство противвременная компромисс: используйте только массив или поддерживайте как этот массив, так и словарь.

Answer 5

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

Answer 6

Это может быть быстрее:

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