Какой самый быстрый способ удалить дубликаты из массива в Objective-C
Готовимся к собеседованию. Я пытаюсь попрактиковаться, решая следующую проблему: учитывая входной массив NSNumbers, где некоторые числа дублируются, как вы можете создать другой массив, который имеет только уникальные значения в исходном массиве.
Я вижу 2 подхода:
Brute-force: цикл по каждому элементу в массиве, в то время как в элементе сравнивайте его с набором чисел в уникальном списке, если есть совпадение, не сохраняйте его, иначе добавьте его в уникальный список. O(n^2) худшее время?
Подход на основе хеш-таблицы: иметь хеш-таблицу длиной N. Каждый элемент хеш-таблицы - это NSSet. Каждое число отображается в 0,...N-1 с помощью функции хеширования. Если он существует в NSSet, соответствующем "сопоставленному индексу", он не добавляется в "уникальный массив". если нет, он добавляется в набор и уникальный массив.
Это сложность O(N)?
- Я искал два способа реализации подхода 2 A. NSMutableArray с размером N, все инициализируются объектами [NSNull null] при запуске. B. NSMutableDictionary где ключ = хэшированное целое число отображения
Код для каждого подхода ниже.
Я заметил, что я. Время работы 2A (подход с использованием массива) составляет половину времени работы 2B (подход с использованием Mutabledictionary) для входного массива длиной 403, показанного ниже (0,055 мс против 12 мс).
II. Продолжительность 1 в ~ 5 раз хуже 0,25 мс. Если дубликатов нет, это расхождение еще хуже.
Мои вопросы:
- Есть ли лучший алгоритм, чем 2?
- Есть ли лучшая реализация алгоритма 2?
- Почему словарный подход медленнее? Как я могу ответить на это для себя, используя инструменты профилирования. Т.е. как узнать точное время, затраченное на каждый шаг с помощью инструментов?
Код
Функция хэш-кода
#define NUM_BUCKETS 127
#define RANDOMIZER 11
#define NUM_ITER 40000
int hashcode(int value)
{
int retVal = (value*RANDOMIZER)%NUM_BUCKETS ;
if(retVal<0)
{
retVal+=NUM_BUCKETS ;
}
return retVal ;
}
1. Подход грубой силы
NSMutableArray *smooshedArr=[[NSMutableArray alloc] init] ;
double startTime ;
startTime=CFAbsoluteTimeGetCurrent() ;
for(int iter=0;iter<=NUM_ITER;iter++)
{
[smooshedArr removeAllObjects] ;
[smooshedArr addObject:ints[0]] ;
int i,j ;
for(i=1;i<[ints count];i++)
{
for(j=0;j<[smooshedArr count];j++)
{
if([ints[i] intValue] == [smooshedArr[j] intValue])
{
break ;
}
}
if(j==[smooshedArr count])
{
[smooshedArr addObject:ints[i]] ;
}
}
}
NSLog(@"Bruteforce took %.3fms to remove duplicates from array of length %lu",(CFAbsoluteTimeGetCurrent()-startTime)*1000/NUM_ITER,(unsigned long)[ints count]) ;
NSLog(@"Smooshed arary is %@",smooshedArr) ;
2А. Хэш-таблица на основе массива
NSMutableArray *hashTable = [[NSMutableArray alloc] init] ;
startTime=CFAbsoluteTimeGetCurrent() ;
for(int iter=0;iter<=NUM_ITER;iter++)
{
[smooshedArr removeAllObjects];
for (NSInteger i = 0; i < NUM_BUCKETS; ++i)
{
[hashTable addObject:[NSNull null]];
}
[smooshedArr addObject:ints[0]] ;
int indexToInsert = hashcode([ints[0] intValue]) ;
hashTable[indexToInsert]=[[NSMutableSet alloc] init] ;
[hashTable[indexToInsert] addObject:ints[0]] ;
int i ;
for(i=1;i<[ints count];i++)
{
//Find hascode of element i
//If the list at index = hashcode in hashCodeArary is empty, then create a NSMutableSet, set toInsert = True
//If not empty, check if the element exists in the set. If yes, setToInsert=False. If no, setToInsert=True
int indexToInsert = hashcode([ints[i] intValue]) ;
BOOL toInsert=false ;
if(hashTable[indexToInsert] == [NSNull null])
{
hashTable[indexToInsert]=[[NSMutableSet alloc] init] ;
toInsert=true ;
}
else
{
if(![hashTable[indexToInsert] containsObject:ints[i]])
toInsert=true ;
}
if(toInsert)
{
[hashTable[indexToInsert] addObject:ints[i]] ;
[smooshedArr addObject:ints[i]] ;
}
}
}
NSLog(@"MutableArray (no cheat) took %.3fms to remove duplicates from array of length %lu",(CFAbsoluteTimeGetCurrent()-startTime)*1000/NUM_ITER,(unsigned long)[ints count]) ;
2B. Словарь на основе хэш-таблицы
NSMutableDictionary *hashDict = [[NSMutableDictionary alloc] init] ;
//NSLog(@"Start of hashcode approach %.6f", CFAbsoluteTimeGetCurrent()) ;
startTime=CFAbsoluteTimeGetCurrent() ;
for(int iter=0;iter<=NUM_ITER;iter++)
{
//if(iter <4) NSLog(@"iter start: %.6f", CFAbsoluteTimeGetCurrent()) ;
//if(iter <4) NSLog(@"init start: %.6f", CFAbsoluteTimeGetCurrent()) ;
[smooshedArr removeAllObjects];
[hashDict removeAllObjects] ;
//if (iter<4) NSLog(@"init end: %.6f", CFAbsoluteTimeGetCurrent()) ;
[smooshedArr addObject:ints[0]] ;
int indexToInsert = hashcode([ints[0] intValue]) ;
hashDict[@(indexToInsert)]=[[NSMutableSet alloc] init] ;
[hashDict[@(indexToInsert)] addObject:ints[0]] ;
int i ;
for(i=1;i<[ints count];i++)
{
//Find hascode of element i
//If the list at index = hashcode in hashCodeArary is empty, then create a NSMutableSet, set toInsert = True
//If not empty, check if the element exists in the set. If yes, setToInsert=False. If no, setToInsert=True
int indexToInsert = hashcode([ints[i] intValue]) ;
BOOL toInsert=false ;
if(hashDict[@(indexToInsert)] == nil)
{
hashDict[@(indexToInsert)]=[[NSMutableSet alloc] init] ;
toInsert=true ;
}
else
{
if(![hashDict[@(indexToInsert)] containsObject:ints[i]])
toInsert=true ;
}
if(toInsert)
{
[hashDict[@(indexToInsert)] addObject:ints[i]] ;
[smooshedArr addObject:ints[i]] ;
}
}
}
NSLog(@"Dictionary approach: %.3fms to remove duplicates from array of length %lu",(CFAbsoluteTimeGetCurrent()-startTime)*1000/NUM_ITER,(unsigned long)[ints count]) ;
Вход протестирован, 430 элементов с некоторыми дуплексами и в среднем более 40000 итераций
NSArray *ints = @[@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2727272),@(112),@(3),@(4),@(1),@(612211),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(7272),@(1232),@(3),@(4),@(1),@(60),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2727272),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2727272),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(72),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(13272),@(2),@(3),@(4),@(18),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(972),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(3272),@(2),@(3),@(4),@(1),@(69),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(1272),@(2),@(3),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(2272),@(2),@(3),@(4),@(1),@(6),@(91),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(7272),@(2),@(3),@(4),@(12),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(111),@(27272),@(2),@(321),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(4545411),@(12341),@(34210),@(123),@(1234),@(1111),@(727272),@(11187),@(9086),@(876543),@(74532),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(13272),@(2),@(3),@(4),@(18),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(658),@(45454),@(12934),@(38421),@(1243),@(12345),@(1112),@(72),@(52),@(3),@(498),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(45454),@(1234),@(650),@(45454),@(1234),@(3421),@(123),@(1234),@(111),@(27272),@(2),@(321),@(4),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(65),@(4545411),@(12341),@(34210),@(123),@(1234),@(1111),@(727272),@(11187),@(9086),@(876543),@(74532),@(464642),@(65),@(45454),@(1234),@(3421),@(123),@(1234),@(11111),@(13272),@(2),@(3),@(4),@(18),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(45454),@(464642),@(658),@(45454),@(12934),@(38421),@(1243),@(19992345),@(119875412),@(72),@(52),@(3),@(498),@(1),@(6),@(9),@(2),@(2),@(3),@(21),@(22),@(450454),@(46908764642),@(6753435),@(45498754),@(100234),@(65)] ;
3 ответа
Если вы готовитесь к собеседованию, я бы посоветовал вам использовать уже внедренные базовые классы. Не переопределяйте колесо. Попробуйте решить проблему сверху вниз. Не думайте о деталях (хеш-функциях), думайте о структуре алгоритма:
В псевдокоде:
for number in input {
if number appears for the first time {
add number to output
}
}
Единственная проблема, которую мы имеем, состоит в том, как реализовать number appears for the first time, Это единственный момент, который имеет некоторые последствия для производительности здесь.
В Objective-C мы можем использовать NSSet который является классом, созданным именно для этой проблемы.
NSArray *input = @[... array of numbers];
NSMutableSet *foundNumbers = [NSMutableSet set];
NSMutableArray *output = [NSMutableArray array];
for (NSNumber *number in input) {
if (![foundNumbers containsObject:number])) {
[foundNumbers addObject:number];
[output addObject:number];
}
}
NSLog(@"Output: %@", output);
Вам нужен только один проход входного массива. Единственный способ улучшить производительность - использовать структуру, отличную от NSSet, тем не мение NSSet уже оптимизирован, и вряд ли вы найдете лучший вариант.
Если вы хотите придумать что-то нестандартное и числа в вашем входе ограничены достаточно маленьким диапазоном (например, 0...65000), вы можете создать BOOL массив с 65000 элементов, все инициализированы в NO и использовать это в качестве быстрой реализации набора. Однако это займет много памяти и не окупится, если input массив очень длинный.
Определенно не реализуйте свои собственные хеш-таблицы, NSDictionary это уже хеш-таблица. То, что вы делаете в своей второй реализации, является просто очень запутанным повторным воплощением NSDictionary, Бакеты работают только тогда, когда вы можете хранить их как простой массив. Как только вы добавите к нему хэш-функцию, вы потеряете прирост производительности.
Также обратите внимание, что общее качество кода очень важно для интервью. Не использовать #define объявить константу. Сохраняйте хороший стиль кодирования (я настоятельно рекомендую использовать пробелы вокруг операторов). Используйте итераторы вместо for(;;) Попробуйте назвать ваши переменные лучше, чем hashDict (назовите ваши переменные для данных, которые они содержат).
Теперь маленький секрет, есть также класс NSOrderedSet который сочетает в себе NSArray а также NSSet в один объект и может решить вашу проблему еще проще:
NSOrderedSet *orderedSet = [NSOrderedSet orderedSetWithArray:ints];
NSLog(@"Output: %@", orderedSet);
Если вы не хотите использовать дополнительный пробел (хеш), если последовательность чисел в массиве не имеет значения, но вы все равно не хотите быть медленным, как грубая сила, тогда вы можете отсортировать массив, а затем удалить дубликаты в одном проходить. Временная сложность nlog(n) + n
На самом деле использование NSOrderedSet даже не нужно - можно обойтись только с помощью NSSet:
NSSet *set = [NSSet setWithArray:ints];
Если вам нужен массив в качестве вывода, здесь поможет кодирование значения ключа:
NSArray *array = [ints valueForKeyPath:@"@distinctUnionOfObjects.self"];