通过 NSArray 搜索的有效方法是什么

What is the efficient way to search trough NSArray

我的数组中有 NSStrings:

i[0] = axxx
i[1] = axyz
i[2] = axxy
i[3] = abcd

我想传递搜索字符串以查找所有需要的字符串。例如,如果我传递 "ax" 那么它将 return 3 个字符串,如果我传递 "axx" 那么它将 return 2 个字符串。

性能在这里也很关键。该方法应如下所示:

- (NSArray *)searchString:(NSString *)search; 

Noramlly 我使用 NSPredicate,但这次我需要使用前缀树或二叉树,我不确定但它应该更快。任何建议或实施链接。

这是一个相当简单的问题。

正如 Avi 在他的评论中所建议的那样,它分为两部分:用于匹配的方法,以及用于搜索这些匹配项的方法。

如果您的数组已排序并且您正在寻找一个完美的匹配项,则可以使用二进制搜索。我相信这会给你 O(log(n)) 性能。 (时间随着元素个数的对数上升。)

但是,您并不是在寻找一个完美的匹配项。您正在寻找部分匹配项。如果它们总是必须匹配字符串的开头,那么您仍然可以使用二进制搜索找到第一个匹配项,然后在数组中向上和向下线性搜索直到第一个不匹配。这将使您的性能比 O(log(n)) 稍差,但不如 O(n) 差。

如果您在条目内的任何位置匹配您的子字符串,我认为您将不得不测试数组中的每个元素。您只需要测试每个元素,即可获得 O(n) 性能。

请注意,O(n) 性能通常被认为是好的。它适用于大型数据集。 (您想避免 O(n^2) 的性能。这就是要了您的命。)

问题的第二部分是匹配速度。通过编写自己的字符串匹配例程(针对您的精确匹配条件进行硬编码),您可能会获得比谓词稍好的性能,但性能提升可能不大。您必须提供有关什么构成匹配的更多详细信息,以便我们在这部分提供帮助。

缺少基本信息。如果您查找 "axx",您是否希望 "haxx" 出现在您的结果中? "HaXX"? "Axxyyyz"? “äxx”?你有几根弦? 10? 100? 1000?十万?您多久进行一次此搜索?数组多久更改一次?

第一步是确定哪个 NSString 方法将匹配您要匹配的字符串。第二步是使用蛮力和测量来实现(谓词通常比遍历数组慢几倍)。第三步是弄清楚对数据进行排序是否有帮助。

希望这个解决方案能让您满意。

- (NSArray *)searchString:(NSString *)search{

    NSIndexSet *indexes = [dataArray indexesOfObjectsPassingTest:
                           ^BOOL (id obj, NSUInteger i, BOOL *stop) {
                               NSString *myObj = obj;
                               return [myObj containsString:search];
                           }];
    NSArray *results = [dataArray objectsAtIndexes:indexes];

    return results;

}