我在过滤大型NSArray（19k 个项目）以在 iPhone 上进行交互式自动完成时遇到性能问题。
目前，每当用户在搜索框中键入一个字母时，我都会NSPredicate在一个单独的线程中开始使用 an 过滤数组并显示结果。当然，数据集对于 iPhone 来说太大了，要在用户点击第二个键之前完成过滤，所以不会显示预览，直到用户停止输入一两秒。
[Computer Science Babble，你可以放心地跳过这部分] 我猜，框架正在做的是将 NSPredicate 应用于数组中的每一项，因此需要 O(n)，其中 n 是数组项的数量。但是，应该可以使用更有效的方法在 O(log(n)) 中更多地解决问题。即在 O(n*log(n)) 中对列表进行一次排序（这可以在开发时完成），查找需要在该列表中插入搜索字符串的位置 O(log(n)) 并开始迭代直到一个项目不以搜索字符串 O(m) 开头。产生一个有效的 O(log(n) + m)，其中 m << n 算法。DAWG 会更好，但我不记得在工具包中看到过类似的东西。[/计算机科学喋喋不休]
我想知道，如果有一种内置方法可以让数组知道，它是按过滤器正在测试的相同字段排序的，因此过滤器可以有效地应用于该排序数组。
解决方案
我使用字典创建了一个非常简单的搜索索引，该字典将单个字符映射到其键以该字符开头的项目数组。至少对于我的用例而言，这足以实现即时显示自动完成的优化。