iphone - 在 Objective-C 中搜索字符串的最快方法是什么？

Question

我正在为 iOS 应用程序实现一种自动完成功能。我用于自动完成值的数据是一个以逗号分隔的文本文件，包含大约 100,000 个字符串。这就是我现在正在做的:

1. 读取文本文件，并创建一个包含 100,000 个 NSString 的 NSArray。
2. 当用户输入时，执行[array containsObject:text]

肯定有更好/更快的方法来执行此查找。有什么想法吗？

Answer 1

绝对有!不过，它不是“在 Objective-C 中”:您很可能需要自己编写代码。

想法是将您的字符串列表转换为 suffix tree ，一种数据结构，可让您非常快速地按前缀搜索。在后缀树中搜索可能的补全非常快，但结构本身并不容易构建。在 Internet 上快速搜索发现在 Objective C 中没有现成的实现，但您可以 port an implementation in another language , use a C implementation ，如果您的时间不是特别紧迫，甚至可以自己编写。

也许更简单的方法是按字母顺序对字符串进行排序，并对目前输入的前缀运行二进制搜索。尽管不如后缀树高效，但排序数组方法对于 100K 字符串是可以接受的，因为您在不到 17 次检查中就找到了正确的位置。