在大陣列中搜索字符串需要很長時間

我正在實現一個根據用戶輸入的文本過濾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

謝謝你的回答。我不確定我完全關注你... 聽起來好像有一些字典來保存數據甚至是三維數組等等。但是，解決方案還不夠好，因爲我是從數組中的字符串中尋找子串。它不一定以我用來搜索的子字符串開始... –

我剛剛意識到問題是從數組中刪除而不是搜索本身... –

在大陣列中搜索字符串需要很長時間

回答

相關問題