ios - 在Objective-C中搜索大型数组

我有两个非常大的NSMutableArray字符串，每个字符串包含超过40k记录。我必须从一个数组中获取每个元素，然后将该字符串排序到另一个数组中，然后创建一个新数组，该新数组仅包含两个数组中的那些记录。我实现了以下代码，这些代码需要太多时间以及大量内存空间(设备崩溃)。有什么方法可以更有效地解决此问题。

// _perArray and listArray contains   more then 30K records each
for(NSString *gak in _perArray){
    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF LIKE[c] %@",gak];
    NSArray *results = [listArray filteredArrayUsingPredicate:predicate];
    if(results.count>0){
        [_resultArray addObject:results[0]];

    }
}

最佳答案

使用二进制搜索

索引对一个数组排序(一个记录较少的数组)

这将启用二进制搜索

的用法

对较小的数组进行排序只是为了减少索引数组的内存

遍历第二个数组

用于第一个数组

中的每个记录二进制搜索

(如果找到)将记录添加到输出数组

不要忘记预分配输出数组，以避免重新分配速度降低

这是什么意思:

令N,M为其中N<=M

的数组大小

天真的方法是O(N.M)

这种方法(取决于使用的排序)导致O(N.log(N).log(M))

对两个数组进行排序并使用单遍增量搜索

的复杂性将导致类似于O((N.log(N))+(M.log(M))+M)

在复杂性方面变成O(M.log(M)) 的

所以:

索引对展位数组进行排序

通过M循环

具有较少记录的数组的

增量索引

(如果找到匹配项)将其添加到输出数组

更具体地说，项目符号2将会是这样的(如果数组升序排列):

// variables
string m[M],n[N],o[N]; // your arrays any string type with overloaded <,== operators
int M,N,O;               // arrays sizes
int ixm[M],ixn[N];      // indexes for index sort
int i,j;

// bullet 2
for (i=0,j=0,O=0;;)
 {
 if (m[ixm[i]]==n[ixn[j]]) { o[O]=m[ixm[i]]; O++; }
 if (m[ixm[i]]< n[ixn[j]]) { if (i<M) i++; else { if (j<N) j++; else break; }}
  else                     { if (j<N) j++; else { if (i<M) i++; else break; }}
 }

如果正确地对字符串比较进行编码，则可以在条件单一的情况下进行比较

[备注]

如果您不想使用任何这些方法，那么还有另一种方法

您可以将标志添加到一个数组，告诉您是否已使用

(如果在比较期间跳过它的使用)

，它将使您的幼稚方法加快大约两倍

通过M.N字符串比较中的

，您只需要做M.N/2

如果数据块太大而无法容纳在内存中

然后将两个数组分割成适合内存/缓存/大小的某个大小。

和第一个索引对所有段进行排序

然后对所有段组合

执行上述方法之一

唯一需要添加的就是检查O[]是否尚未包含添加的字符串

如果您的数组没有相同字符串的倍数，则

并非如此

否则保持O[]排序或索引排序

并通过二进制搜索进行检查...

通过使用已使用的标志，可以显着加快该细分速度