iOS Найти удаленный элемент в большом массиве (например:> 1 миллион элементов)

В интервью для позиции разработчиков iOS они спросили меня о самом быстром решении найти удаленные элементы в большом массиве (более 1 миллиона элементов), то есть: на локальном, у приложения был массив с сервера (нам не нужен метод для получения этого массива от сервера). Затем, на сервере, они удалили несколько элементов в этом массиве & на локальном, мы не знали. Итак, как мы можем найти удаленные элементы в локальной базе на новый массив на сервере и локальном массиве? Я думаю, что через 02 дней и найти этот цикл ниже, но это будет нормально, когда сервер удаляет элементы в начале или в конце массива. При удалении элементов в середине массива этот цикл занимает очень много времени.

#define rchar (rand() % ('z'-'a') + 'a') 

– (void) viewDidLoad:

 NSMutableArray * mar = [NSMutableArray new]; // represent server array. for (int i = 0; i<50000; i++) //10 50000 200000 400000 600000 800000 { NSString * str = [NSString stringWithFormat:@"%c%c%c%c",rchar, rchar, rchar, rchar]; [mar addObject:str]; } NSMutableArray *tmpServerArr = [[NSMutableArray alloc] initWithArray:mar copyItems:YES]; NSMutableArray *localArr = [[NSMutableArray alloc]initWithCapacity:50002]; // represent local array for (int i = 0; i<50002; i++) //10 50000 200000 { switch (i) { case 32111: [localArr addObject:[NSString stringWithFormat:@"%c%c%c%c",rchar, rchar, rchar, rchar]]; break; case 41234: [localArr addObject:[NSString stringWithFormat:@"%c%c%c%c",rchar, rchar, rchar, rchar]]; break; case 50000: [localArr addObject:mar[32111]]; break; case 50001: [localArr addObject:mar[41234]]; break; default: [localArr addObject:mar[i]]; break; } } NSUInteger localremainItem = [localArr count]; NSDate *start; NSUInteger loopWhile = 0; while (localremainItem > 0 ) { // while ([localArr count] > 0 ) { NSUInteger idxItemStr = (localremainItem -1 - pow(-1, loopWhile)*(localremainItem-1))/2; // -1; NSLog(@"idxstring: %li -- pow: %f", idxItemStr, pow(-1, loopWhile)); NSString *itemStr = localArr[idxItemStr]; NSLog(@"item checked : %@]", itemStr); NSPredicate *pre = [ NSPredicate predicateWithFormat:@"NOT (SELF like %@)", itemStr]; NSCountedSet * localCountedSet = [[ NSCountedSet alloc] initWithArray:localArr]; NSCountedSet * serverCountedSet = [[ NSCountedSet alloc] initWithArray:tmpServerArr]; if ([localCountedSet countForObject:itemStr] > [serverCountedSet countForObject:itemStr]) { NSLog(@"this item %@ was deleted in server.", itemStr); } //else { [localArr filterUsingPredicate: pre]; [tmpServerArr filterUsingPredicate:pre]; NSLog(@"localremain: %li", [localArr count]); NSLog(@"tmpserverremain: %li", [tmpServerArr count]); // } if ([localArr count] == [tmpServerArr count]) { localremainItem = 0; } else localremainItem = [localArr count]; loopWhile +=1; } NSLog(@"now server arr is controled! time: %f", -[start timeIntervalSinceNow]); 

Спасибо за помощь.
** Обновление 14 ноября 2015 г.: этот цикл ниже в 8 раз быстрее:
in viewDidLoad:

 while ([localArr count] >0) { NSUInteger maxRange =0; if ([localArr count] >500) { maxRange = 500; }else maxRange = [localArr count]; NSArray *sampleTest = [[NSArray alloc] initWithArray:[localArr subarrayWithRange:NSMakeRange(0,maxRange)]]; NSLog(@"sampleTest cnt: %lu", (unsigned long)[sampleTest count]); if ([self countSampleTest:localArr serverArr:tmpServerArr sampleTest:sampleTest]) { NSPredicate *pre = [ NSPredicate predicateWithFormat:@"NOT (SELF in %@)", sampleTest]; [localArr filterUsingPredicate: pre]; [tmpServerArr filterUsingPredicate:pre]; NSLog(@"localremain: %li", [localArr count]); NSLog(@"tmpserverremain: %li", [tmpServerArr count]); } else { NSLog(@"deleted item in here!: %i, %li", 0, [sampleTest count]); //[localArr count]/10); int found = 0; while (found <10) { maxRange =0; if ([localArr count] >50) { maxRange = 50; }else maxRange = [localArr count]; NSArray *sampleTest1 = [[NSArray alloc] initWithArray:[localArr subarrayWithRange:NSMakeRange(0,maxRange)]]; NSLog(@"sampleTest1 cnt: %lu", (unsigned long)[sampleTest1 count]); if ([self countSampleTest:localArr serverArr:tmpServerArr sampleTest:sampleTest1]) { NSPredicate *pre = [ NSPredicate predicateWithFormat:@"NOT (SELF in %@)", sampleTest1]; [localArr filterUsingPredicate: pre]; [tmpServerArr filterUsingPredicate:pre]; NSLog(@"localremain: %li", [localArr count]); NSLog(@"tmpserverremain: %li", [tmpServerArr count]); } else { NSUInteger k = 0; while (k< [sampleTest1 count]) { NSLog(@"item checked %lu : %@]", (unsigned long)k, sampleTest1[k]); NSCountedSet * localCountedSet = [[ NSCountedSet alloc] initWithArray:localArr]; NSCountedSet * serverCountedSet = [[ NSCountedSet alloc] initWithArray:tmpServerArr]; if ([localCountedSet countForObject:sampleTest1[k]] > [serverCountedSet countForObject:sampleTest1[k]]) { NSLog(@"this item %@ was deleted in server.", sampleTest1[k]); } NSPredicate *pre = [ NSPredicate predicateWithFormat:@"NOT (SELF like %@)", sampleTest1[k]]; [localArr filterUsingPredicate: pre]; [tmpServerArr filterUsingPredicate:pre]; NSLog(@"localremain: %li", [localArr count]); NSLog(@"tmpserverremain: %li", [tmpServerArr count]); if ([localArr count] == [tmpServerArr count]) { k = [sampleTest1 count]; found = 10; }else k +=1; } } found +=1; } } if ([localArr count] == [tmpServerArr count]) { localArr = nil; } // if ([sampleTest count] == 0) { // localArr = nil; // } } NSLog(@"this stuck is done!");//end viewDidLoad. -(BOOL)countSampleTest: (NSMutableArray *)localArr serverArr:(NSMutableArray *)tmpServerArr sampleTest:(NSArray *)sampleTest{ BOOL tf; int cntSampleLoc = 0; int cntSampleServer = 0; for (int i = 0 ; i < [sampleTest count]; i++) { NSCountedSet * localCountedSet = [[ NSCountedSet alloc] initWithArray:localArr]; NSCountedSet * serverCountedSet = [[ NSCountedSet alloc] initWithArray:tmpServerArr]; cntSampleLoc += [localCountedSet countForObject:sampleTest[i]]; //if (localArr[i] in tmpServerArr ) { cntSampleServer +=[serverCountedSet countForObject:sampleTest[i]]; // } } if (cntSampleServer == cntSampleLoc) { tf= true; }else tf = false; return tf;} 

4 Solutions collect form web for “iOS Найти удаленный элемент в большом массиве (например:> 1 миллион элементов)”

Первое решение, которое приходит мне на ум, довольно просто:

 NSArray *serverArray; NSMutableArray *localArray; // This will give you the difference. [localArray removeObjectsInArray:serverArray]; 

Документы говорят:

removeObjectsInArray:

Этот метод похож на removeObject: но он позволяет эффективно удалять большие объекты объектов с помощью одной операции.

Вы также можете использовать NSSet и NSMutableSet которые будут быстрее для больших наборов данных:

 NSMutableSet *serverSet = [NSMutableSet setWithArray: serverArray]; NSSet *localSet = [NSSet setWithArray: localArray]; [serverSet minusSet: localSet]; NSArray *deletedObjects = [serverSet allObjects]; 

См. Также этот вопрос SO для получения дополнительной информации о различиях в производительности между NSArray и NSSet .

Не прибегая к написанию алгоритма:

Хранение ваших отсортированных массивов поможет.

Представьте, что вы ищете слово «мышь» в словаре. Если вы начинаете с «a» и просто проверяете, будет ли каждое слово «мышкой», это займет вас навсегда. Но зная, что слова «m» будут находиться в середине-иш, и что «o» находится в середине «м», означает, что вы можете найти свое слово намного быстрее.

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

  1. Создайте Hashmap (Словарь) как локального, так и серверного массивов.
  2. Прокрутите через локальный массив и посмотрите, существует ли элемент в массиве серверов.

O (N + N + N) = O (3N) = 0 (N)

  • Как получить backBarButtonItem ширину?
  • Xcode 8.1 говорит: «Попробуйте снова войти в систему или обратитесь в службу поддержки Apple, чтобы решить проблему с доступом к учетной записи», что мне делать?
  • Как сбросить номер оповещения iOS Push в Parse?
  • UITapGestureRecognizer initWithTarget: действие: метод для принятия аргументов?
  • Как добавить предопределенные значения в plist?
  • UIButton не выделен на границе
  • UIPopoverController изменяет размер popover и content-viewcontroller (uinavigationcontroller) с разной скоростью
  • Уникальный (глобальный) идентификатор iOS EventKit EKCalendar
  • Настройка UITextField не редактируется или редактируется
  • Как показать предупреждение после установки приложения в устройстве ios
  • Выбор не тип, который можно переименовать Xcode 7
  • Interesting Posts

    _itemFailedToPlayToEnd при воспроизведении локальной mp4 с использованием UIWebView

    IOS: два UIAlert с двумя различными методами делегирования

    Пейджинг в коллекции

    Получить координаты X и Y слова в UITextView

    Поддержка NSOperationQueue и поддержка фона

    Как избежать искажения и растяжения изображения в пользовательском UIButton при использовании набора векторных изображений?

    Как повторно проверить подлинность моего приложения?

    Интеграция с Google Map iOS 1.9.0

    iPhone. Во время запуска приложения приложение переходит в фоновый режим.

    Как я могу отклонить модальный сегмент, а затем выполнить push segue в новый контроллер вида

    Как построить Facebook iOS sdk для armv7s?

    Как быстро получить точную точку объектов?

    Открыть рулон камеры на точной фотографии

    Как скрыть / показать панель вкладок с помощью панели навигации в iOS?

    Отсутствует информация об отладке в файле Dwarf?

    PhoneC: Разработка iOS проста с помощью XCode, Swift3, UITableView, cocatouch, давайте создадим приложения для iPhone, iPad и Macbook.