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

Question

我的数组中有 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，但这次我需要使用前缀树或二叉树，我不确定但它应该更快。任何建议或实施链接。

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

- (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;

}

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

What is the efficient way to search trough NSArray

ios

objective-c

binary-tree

binary-search-tree

prefix-tree