cocoa-touch - 如何有效地过滤大型 NSArray？

Question

我在为 iPhone 上的交互式自动完成过滤大型 NSArray(19k 项)时遇到性能问题。

目前，每当用户在搜索框中输入字母时，我都会在单独的线程中使用 NSPredicate 开始过滤数组并显示结果。当然，数据集太大，iPhone 无法在用户按下第二个键之前完成过滤，因此不会显示预览，直到用户停止输入一两秒。

[计算机科学白痴，你可以安全地跳过这部分]我猜，框架正在做的是将 NSPredicate 应用于数组中的每个项目，因此需要 O(n)，其中 n 是数量数组项。但是，应该可以使用更有效的方法在 O(log(n)) 中更多地解决问题。 IE。在 O(n*log(n)) 中对列表进行一次排序(这可以在开发时完成)，查找需要在该列表中插入搜索字符串的位置 O(log(n)) 并从那里开始迭代直到一个项目不以搜索字符串 O(m) 开头。产生一个高效的 O(log(n) + m)，其中 m << n 算法。 DAWG 会更好，但我不记得在工具包中看到过类似的东西。 [/计算机科学牙牙学语]

我在想，是否有一种内置的方式让数组知道，它是按过滤器测试的同一个字段排序的，因此过滤器可以有效地应用于那个排序的数组。

解决方案

我使用字典创建了一个非常简单的搜索索引，该字典将单个字符映射到键以该字符开头的项目数组。至少对于我的用例来说，这是足以实现即时显示自动完成的优化。

Answer 1

如果数据以某种方式排序，那么我建议将数组分成多个较小的数组。所以你可能有 A-G、H-M、N-Z 数组。

或者将所有内容都放入核心数据或 SQLite 数据库中，并使用查询来帮助加快速度。当您处理如此大的数据集时，索引数据库选择将比尝试在内存中过滤数据更有效。

另一个建议是创建一个 trie，这将使一切变得更好。尽管创建它们需要一些工作:

http://en.wikipedia.org/wiki/Trie