我在iPhone上进行交互式自动完成时，使用一个大型的NSArray（19k个项目）过滤时遇到了性能问题。
目前，每当用户在搜索框中键入一个字母时，我就会在单独的线程中使用NSPredicate对数组进行过滤，并显示结果。当然，数据集太大，iPhone无法在用户按下第二个键之前完成过滤，因此不会显示预览，直到用户停止输入一两秒钟。
[计算机科学术语，您可以跳过此部分] 我想，框架所做的是将NSPredicate应用于数组中的每个项目，因此需要O(n)，其中n是数组项的数量。但是，可以使用更有效的方法以O(log(n))解决问题。即，在O(n*log(n))中一次对列表进行排序（可以在开发时完成），查找需要在该列表中插入搜索字符串的位置O(log(n))，并从那里开始迭代，直到找到一个不以搜索字符串开头的项O(m)。结果是一个高效的O(log(n)+m)，其中m<我想知道是否有内置的方法让数组知道它是按与过滤器进行测试的同一字段进行排序的，从而可以在该排序后的数组上有效地应用过滤器。
解决方案：
我使用字典创建了一个非常简单的搜索索引，将单个字符映射到以该字符开头的键的项目数组。至少对于我的用例来说，这足以优化以实现瞬时显示自动完成。
目前，每当用户在搜索框中键入一个字母时，我就会在单独的线程中使用NSPredicate对数组进行过滤，并显示结果。当然，数据集太大，iPhone无法在用户按下第二个键之前完成过滤，因此不会显示预览，直到用户停止输入一两秒钟。
[计算机科学术语，您可以跳过此部分] 我想，框架所做的是将NSPredicate应用于数组中的每个项目，因此需要O(n)，其中n是数组项的数量。但是，可以使用更有效的方法以O(log(n))解决问题。即，在O(n*log(n))中一次对列表进行排序（可以在开发时完成），查找需要在该列表中插入搜索字符串的位置O(log(n))，并从那里开始迭代，直到找到一个不以搜索字符串开头的项O(m)。结果是一个高效的O(log(n)+m)，其中m<我想知道是否有内置的方法让数组知道它是按与过滤器进行测试的同一字段进行排序的，从而可以在该排序后的数组上有效地应用过滤器。
解决方案：
我使用字典创建了一个非常简单的搜索索引，将单个字符映射到以该字符开头的键的项目数组。至少对于我的用例来说，这足以优化以实现瞬时显示自动完成。