iOS 在大数组中查找已删除的项目(即 : > 1 million items)

Question

在 iOS 开发职位的面试中，他们问我在大型数组(> 100 万项)中查找已删除项目的最快解决方案，即:在本地，应用程序已经从服务器获取数组(我们不关心方法来从服务器获取这个数组)。然后，在服务器上，他们删除了这个数组和本地的几个项目，我们不知道。那么，我们如何根据服务器上的新数组和本地数组在本地找到已删除的项目？我想在 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]);

谢谢你的帮助。
** 2015 年 11 月 14 日更新:下面这个循环快了 8 倍:
在 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;}

Answer 1

我想到的第一个解决方案很简单:

NSArray *serverArray;
NSMutableArray *localArray;

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

Docs说:

removeObjectsInArray:

This method is similar to removeObject:, but it allows you to efficiently remove large sets of objects with a single operation.