NSArray: удаление объектов с дублирующимися свойствами

Question

У меня есть NSMutableArray, который содержит несколько пользовательских объектов. Два объекта имеют одинаковые свойства, такие как заголовок и автор. Я хочу удалить дубликат объекта и оставить другой.

Asset *asset;
NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease];

// First
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

// Second
asset = [[Asset alloc] init];
asset.title = @"Writer";
asset.author = @"Steve Johnson";
[items addObject:asset];
[asset release];

// Third
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

Так как они НЕ являются одним и тем же объектом, но имеют только повторяющиеся свойства, как я могу удалить дубликат?

Answer 1

Вы можете создать HashSet и, зацикливаясь, вы можете добавить сцепленный набор "title + author" в HashSet (NSMutableSet).Когда вы прибудете к каждому элементу, если HashSet содержит ваш ключ, либо удалите его, либо не копируйте (удаляя или создавая копию без дубликатов).

Это делает порядок n (1 цикл)

Вот класс NSMutableSet:

http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/Reference/NSMutableSet.html#//apple_ref/occ/cl/NSMutableSet

РЕДАКТИРОВАТЬ с кодом:

Основой кода является один цикл.

void print(NSMutableArray *assets)
{
    for (Asset *asset in assets)
    {
        NSLog(@"%@/%@", [asset title], [asset author]);
    }
}

int main (int argc, const char * argv[])
{

    NSAutoreleasePool * pool = [[NSAutoreleasePool alloc] init];

    //
    // Create the initial data set
    //
    Asset *asset;
    NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease];

    // First
    asset = [[Asset alloc] init];
    asset.title = @"Developer";
    asset.author = @"John Smith";
    [items addObject:asset];
    [asset release];

    // Second
    asset = [[Asset alloc] init];
    asset.title = @"Writer";
    asset.author = @"Steve Johnson";
    [items addObject:asset];
    [asset release];

    // Third
    asset = [[Asset alloc] init];
    asset.title = @"Developer";
    asset.author = @"John Smith";
    [items addObject:asset];
    [asset release];

    NSLog(@"****Original****");
    print(items);

    //
    // filter the data set in one pass
    //
    NSMutableSet *lookup = [[NSMutableSet alloc] init];
    for (int index = 0; index < [items count]; index++)
    {
        Asset *curr = [items objectAtIndex:index];
        NSString *identifier = [NSString stringWithFormat:@"%@/%@", [curr title], [curr author]];

        // this is very fast constant time lookup in a hash table
        if ([lookup containsObject:identifier])
        {
            NSLog(@"item already exists.  removing: %@ at index %d", identifier, index);
            [items removeObjectAtIndex:index];
        }
        else
        {
            NSLog(@"distinct item.  keeping %@ at index %d", identifier, index);
            [lookup addObject:identifier];
        }
    }

    NSLog(@"****Filtered****");
    print(items);

    [pool drain];
    return 0;
}

Вот вывод:

Craplet[11991:707] ****Original****
Craplet[11991:707] Developer/John Smith
Craplet[11991:707] Writer/Steve Johnson
Craplet[11991:707] Developer/John Smith
Craplet[11991:707] distinct item.  keeping Developer/John Smith at index 0
Craplet[11991:707] distinct item.  keeping Writer/Steve Johnson at index 1
Craplet[11991:707] item already exists.  removing: Developer/John Smith at index 2
Craplet[11991:707] ****Filtered****
Craplet[11991:707] Developer/John Smith
Craplet[11991:707] Writer/Steve Johnson

Answer 2

Вы можете использовать уникальность NSSet, чтобы получить отдельные элементы из вашего исходного массива. Если у вас есть исходный код для Assest, вам нужно переопределить метод hash и isEqual: для класса Asset.

@interface Asset : NSObject
@property(copy) NSString *title, *author;
@end

@implementation Asset
@synthesize title, author;

-(NSUInteger)hash
{
    NSUInteger prime = 31;
    NSUInteger result = 1;

    result = prime * result + [self.title hash];
    result = prime * result + [self.author hash];

    return result;
}

-(BOOL)isEqual:(id)object
{
    return [self.title isEqualToString:[object title]] && 
    [self.author isEqualToString:[object author]];
}

- (void)dealloc {
    [title release];
    [author release];
    [super dealloc];
}

@end

Затем реализовать:

Asset *asset;
NSMutableArray *items = [[[NSMutableArray alloc] init] autorelease];

// First
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

// Second
asset = [[Asset alloc] init];
asset.title = @"Writer";
asset.author = @"Steve Johnson";
[items addObject:asset];
[asset release];

// Third
asset = [[Asset alloc] init];
asset.title = @"Developer";
asset.author = @"John Smith";
[items addObject:asset];
[asset release];

NSLog(@"Items: %@", items);

NSSet *distinctItems = [NSSet setWithArray:items];

NSLog(@"Distinct: %@", distinctItems);

И если вам нужен массив в конце, вы можете просто позвонить [distinctItems allObjects]

Answer 3

Во-первых, я бы переопределил isEqual: метод для Актива следующим образом:

-(BOOL)isEqual:(Asset *)otherAsset {
    return [self.title isEqual:otherAsset.title] && [self.author isEqual:otherAsset.author];
}

Тогда, если вы хотите избежать размещения дубликатов в массиве, сначала:

NSUInteger idx = [items indexOfObject:asset];  // tests objects for equality using isEqual:
if (idx == NSNotFound) [items addObject:asset];

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

NSMutableArray *itemsWithUniqueElements = [NSMutableArray arrayWithCapacity:[items count]];

for (Asset *anAsset in items) {
    if ([items indexOfObject:anAsset] == NSNotFound)
        [itemsWithUniqueElements addObject:anAsset];
}

[items release];
items = [itemsWithUniqueElements retain];

В худшем случае (все элементы уже уникальны) количество итераций равно:

1 + 2 + 3 + ... + n =  n * (n+1) / 2

Что по-прежнему равно O (n ^ 2), но немного лучше, чем алгоритм @Justin Meiners. Без обид! :)

Answer 4

Если вы хотите, чтобы ваши пользовательские подклассы NSObject считались равными, когда их имена равны, вы можете реализовать isEqual: и hash.Это позволит вам добавить объекты в NSSet / NSMutableSet (набор отдельных объектов).

Затем вы можете легко создать отсортированный NSArray, используя NSSet 's *Метод 1009 *.

MikeAsh написал довольно солидную статью о реализации пользовательского равенства: Пятница, вопросы и ответы 2010-06-18: Реализация равенства и хеширования

Answer 5

Это один из способов сделать это :

NSMutableArray* toRemove = [NSMutableArray array];

    for (Asset* asset1 in items)
    {
        for (Asset* asset2 in items)
        {
            if (asset1 != asset2)
            {
                if ([asset1.title isEqualToString:asset2.title] && [asset1.author isEqualToString:asset2.author])
                {
                    [toRemove addObject:asset2];
                }
            }
        }
    }

    for (Asset* deleted in toRemove)
    {
        [items removeObject:toRemove];
    }