在大阵列中搜索字符串需要很长时间

我正在实现一个根据用户输入的文本过滤UITableView的搜索字段。
该TableView中被从保持NSString的（要显示的数据和搜索），并且可以含有6000+项阵列建立。
当用户开始搜索时，我正在执行-(void)searchBar:(UISearchBar *)searchBar textDidChange:(NSString *)searchText方法。
在大阵列中搜索字符串需要很长时间

但是，我的代码工作，但是，当数据数组很大，它非常缓慢，并创建了一个非常糟糕的用户体验（我的iPhone 4卡住了好几秒钟）。

我执行搜索（在上面提到的方法）的方法是这样的：

NSMutableArray *discardedItems = [[NSMutableArray alloc] init]; // Items to be removed 
searchResultsArray = [[NSMutableArray alloc] initWithArray:containerArray]; // The array that holds all the data 

// Search for matching results 
for (int i=0; i<[searchResultsArray count]; i++) { 
    NSString *data = [[containerArray objectAtIndex:i] lowercaseString]; 
    NSRange r = [data rangeOfString:searchText]; 
    if (r.location == NSNotFound) { 
     // Mark the items to be removed 
     [discardedItems addObject:[searchResultsArray objectAtIndex:i]]; 
    } 
} 
// update the display array 
[searchResultsArray removeObjectsInArray:discardedItems]; 
[myTableView reloadData];

我没想到的是遍历数组有几千个项目将造成任何问题。 ..
任何建议将不胜感激！

UPDATE 我刚刚意识到什么需要的大部分时间是这样的：

[searchResultsArray removeObjectsInArray:discardedItems];

来源

2012-09-01 Code Monkey

仪器说什么？ –

你尝试过排序，然后使用二进制搜索？ – Samir

排序是不可能的，因为：1.我需要按照数组中的原始顺序对结果进行排序。 2.我正在查找数组中每个项目的子字符串，而不是它开头的字符串。所以，排序不会有帮助... –

尝试快速列举的方式，我的片段：

- (void)searchBar:(UISearchBar*)searchBar textDidChange:(NSString*)text 
{ 
    if(text.length == 0) 
    { 
     self.isFiltered = NO; 
    } 
    else 
    { 
     self.isFiltered = YES; 
     self.searchArray = [NSMutableArray arrayWithCapacity:self.places.count]; 

     for (PTGPlace* place in self.places) 
     { 
      NSRange nameRange = [place.name rangeOfString:text options:NSCaseInsensitiveSearch]; 

      if(nameRange.location != NSNotFound) 
      { 
       [self.searchArray addObject:place]; 
      } 
     } 
    } 

    [self.tableView reloadData]; 
} 

- (NSInteger)tableView:(UITableView *)tableView numberOfRowsInSection:(NSInteger)section 
{ 
    if(self.isFiltered) 
     return self.searchArray.count; 
    else 
     return self.places.count; 
}

在的cellForRowAtIndexPath：

PTGPlace *place = nil; 

    if(self.isFiltered) 
     place = [self.searchArray objectAtIndex:indexPath.row]; 
    else 
     place = [self.places objectAtIndex:indexPath.row]; 

    // Configure the cell... 
    cell.textLabel.text = place.name; 
    cell.detailTextLabel.text = [place subtitle];

来源

2012-09-01 20:16:22 mientus

感谢您的回复，但您确实做了我所做的。唯一的区别是你在开始时检查了文本长度 - 我已经在我的代码中做了一些事情（但没有添加到我的示例中）。 –

@CodeMonkey这与你的完全不一样。问题是你*比较*。 mientus的实现对字符串进行不区分大小写的比较，而不是创建数千个临时小写字符串，然后进行搜索。自动恢复增长和临时字符串创建是您实现中最大的时间和内存消费者。 mientus的实现不会创建临时字符串，并且autorelease活动较少。我写了一个与帖子太相似的版本 - 我采用的方法比我的测试速度快了3倍（对于我测试的输入）。 ++改进 – justin

@CodeMonkey iow - 快速枚举不是使用这种方法的巨大收益 - 它是自动释放活动的减少，并避免创建许多临时字符串 - 只需搜索现有字符串而不创建中间（和不必要）表示。 – justin

尝试此：

的前三个位置，创建26个索引集，每一个代表以该字母（只是小写）项的数组索引。也就是说，在idx = 100的条目以“公式”开始。在第一个位置代表“f”的索引集将包含索引“100”。为第二个字符'o'设置的索引将包含索引100，并且为第三个字符'r'设置的索引将包含100.

当用户键入字符'f'时，您立即拥有索引以'f'开头的所有数组项（并且可以快速创建主数组的子集）。当接下来键入'o'时，您可以找到第一个匹配中的索引与第二个匹配的交集。第三位同上。现在做一个前三个索引匹配的主数组的子数组 - 你可以使用索引集。

使用这种急剧减少数组，你现在可以做的蛮力匹配你最初做的事情。

来源

2012-09-01 23:03:05

谢谢你的回答。我不确定我完全关注你... 听起来好像有一些字典来保存数据甚至是三维数组等等。但是，解决方案还不够好，因为我是从数组中的字符串中寻找子串。它不一定以我用来搜索的子字符串开始... –

我刚刚意识到问题是从数组中删除而不是搜索本身... –

在大阵列中搜索字符串需要很长时间

回答

相关问题