-1

我的数组中有 NSStrings：

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

我想传递一个搜索字符串来查找所有需要的字符串。例如，如果我传递“ax”，那么它将返回 3 个字符串，如果我传递“axx”，那么它将返回 2 个字符串。

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

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

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

4

3 回答 3

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;

}
于 2016-02-07T14:07:12.813 回答
0

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

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

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

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

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

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

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

于 2016-02-07T12:35:52.527 回答
0

缺少基本信息。如果您寻找“axx”，您是否希望“haxx”出现在您的结果中？“哈XX”？“Axxyyyz”？“xx”？你有几根弦？10？100？1000？100,000？您多久进行一次此搜索？阵列多久更改一次？

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

于 2016-02-07T12:49:52.400 回答