快速搜索和排序

Question

我整个下午都在研究搜索算法，希望得到一些意见。其中一些是特定于iOS的，但一般概念并不是这样。

我试图显示一组数据，即目录。在目录中，我有部门和人员。我知道这听起来像是教科书上的例子，但请听我解释。这不是作业，我保证。（我可以提供我正在工作的屏幕截图。）

我有一个条目数组，其中有这两种目录条目。我需要按名称对条目进行排序，然后将数组分成较小的数组，其中每个子数组包含以相同字母开头的条目。

此外，我需要考虑用户可能输入的搜索字符串。

我的一般过程如下：

1. Filter all the entries that match the type and search string if there is one. For this step I use an NSPredicate:

   NSPredicate *predicate = [NSPredicate predicateWithFormat:@"type == %i AND searchableContents B[cd] %@", type, searchString];
   
   if (!searchString || searchString.length == 0)
   {
       predicate = [NSPredicate predicateWithFormat:@"type == %i", type];
   }
   
   NSArray *array = [_directoryContents filteredArrayUsingPredicate:predicate];
   

2. Sort the results alphabetically.

   array  = [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
       return [((BRKDirectoryEntry *)obj1).comperableTitle compare:((BRKDirectoryEntry *)obj2).comperableTitle];
   }];
   

3. Break up the results into smaller arrays. For performance, I skip this step if we're searching, but it doesn't seem to help.

   if(alphabetized)
   {
       array = [self _alphabetizedArrayFromPresortedArray:array];
   }
   

在总共950个条目中，它的性能很差。

现在，对于我的默认显示，我可以简单地将排序后的数据缓存到内存中，然后显示和滚动表现良好，但是对于实时搜索，根本无法达到用户期望的流畅性能。

有什么指针或提示吗？

- Moshe

---

我仍然惊讶于有多少人会问“我正在做XYZ，但速度太慢了。我该如何使它更快？”好像别人的猜测有很大的机会一样。没有瑞士军刀般万无一失的方法。让程序自己告诉你答案。这里有一个简短的例子（用Python编写，但你会明白的）。 - Mike Dunlavey

只是一个小提示：使用谓词比快速枚举要慢得多，如此所示：https://www.objc.io/issues/7-foundation/collections/（**枚举和高阶消息**部分）。我认为你可以简化这行代码if (!searchString || searchString.length == 0)为if(!searchString.length) - Duc

Answer 1

是的。忘记文件，把它保存在数据库中。创建索引，一切都变成了简单的SQL语句。

- Dan