iphone - NSPredicate 与 NSString : Which is better/faster for finding superstrings?

Question

我有大量的字符串，我正在搜索这些字符串以查看给定的子字符串是否存在。似乎有两种合理的方法可以做到这一点。

选项 1:使用 NSString方法 rangeOfSubstring并测试是否.location存在:

NSRange range = [string rangeOfSubstring:substring];
return (range.location != NSNotFound);

选项 2. 使用 NSPredicate语法 CONTAINS :

NSPredicate *regex = [NSPredicate predicateWithFormat:@"SELF CONTAINS %@", substring];
return ([regex evaluateWithObject:string] == YES)

哪种方法更好，或者是否有我完全缺少的好的选项 3？不，我不确定我所说的“更好”到底是什么意思，但我的意思可能是在迭代很多很多时更快 string s。

Answer 1

您应该对使用 NSPredicate 的任何解决方案进行基准测试和计时。因为根据我的经验 NSPredicate可能会很慢。

为简单起见，我会使用一个简单的 for(NSString *string in stringsArray) { }循环类型。循环体将包含一个简单的 rangeOfSubstring查看。您可以使用 CFStringFind() 将其性能提高几个百分点。 ，但只有在搜索大量字符串时才能看到好处。使用优势 CFStringFind()是您可以避免(非常小的)Objective-C 消息调度开销。同样，当您搜索“很多”字符串时(对于一些总是变化的“很多”值)，切换到它通常只是一个胜利，并且您应该始终进行基准测试以确保。更喜欢更简单的Objective-C rangeOfString:如果可以的话。

一种更复杂的方法是将 ^Blocks 功能与 NSEnumerationConcurrent 一起使用。选项。 NSEnumerationConcurrent只是一个提示，如果可能的话，您希望枚举同时发生，如果实现不能支持并发枚举，则可以自由地忽略此提示。但是，您的标准NSArray最有可能实现并发枚举。实际上，这具有将 NSArray 中的所有对象分开的效果。并将它们拆分到可用的 CPU 上。您需要注意如何改变 ^Block 跨多个线程访问的状态和对象。这是一种潜在的方法:

// Be sure to #include <libkern/OSAtomic.h>

__block volatile OSSpinLock spinLock = OS_SPINLOCK_INIT;
__block NSMutableArray *matchesArray = [NSMutableArray array];

[stringsToSearchArray enumerateObjectsWithOptions:NSEnumerationConcurrent usingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
    NSRange matchedRange = [obj rangeOfString:@"this"];
    if(matchedRange.location != NSNotFound) {
      OSSpinLockLock((volatile OSSpinLock * volatile)&spinLock);
      [matchesArray addObject:obj];
      OSSpinLockUnlock((volatile OSSpinLock * volatile)&spinLock);
    }
  }];

// At this point, matchesArray will contain all the strings that had a match.

这使用轻量级 OSSpinLock确保只有一个线程可以访问和更新 matchesArray一次。您可以使用相同的 CFStringFind()上面的建议也是如此。

另外，您应该知道 rangeOfString:本身不会匹配“单词边界”。在上面的例子中，我使用了词 this ，它将匹配字符串 A paleolithist walked in to the bar...即使它不包含单词 this .

解决这个小问题的最简单的方法是使用 ICU 正则表达式并利用它的“增强的断字”功能。为此，您有几个选择:

NSRegularExpression ，目前仅适用于 >4.2 或 >4.3 iOS(我忘记了哪个)。

RegexKitLite , 通过 RegexKitLite-4.0.tar.bz2

NSPredicate , 通过 SELF MATCHES '(?w)\b...\b' .这样做的好处是它不需要任何额外的东西(即 RegexKitLite)，并且适用于所有(？)版本的 Mac OS X 和 iOS > 3.0。

以下代码显示了如何通过 NSPredicate 在 ICU 正则表达式中使用增强的断字功能。 :

NSString *searchForString = @"this";
NSString *regexString = [NSString stringWithFormat:@".*(?w:\\b\\Q%@\\E\\b).*", searchForString];
NSPredicate *wordBoundaryRegexPredicate = [NSPredicate predicateWithFormat:@"SELF MATCHES %@", regexString];
NSArray *matchesArray = [stringsToSearchArray filteredArrayUsingPredicate:wordBoundaryRegexPredicate];

您可以通过替换 (?w: 使搜索不区分大小写在 regexString与 (?wi: .

正则表达式，如果你有兴趣，基本上说

.*(?w:...).*说“匹配 (?w:...) 部分之前和之后的任何内容”(即，我们只对 (?w:...) 部分感兴趣)。

(?w:...)说“在括号内打开 ICU 增强的分词/查找功能”。

\\b...\\b (这实际上只是一个反斜杠，当它在 @"" 字符串中时，任何反斜杠都必须被反斜杠转义)说“在单词边界处匹配”。

\\Q...\\E说“将紧跟在 \Q 之后直到 \E 的文本视为文字文本(想想“引用”和“结束”)”。换句话说，“引用文字”中的任何字符都没有其特殊的正则表达式含义。

\Q...\E的原因是您可能想要匹配 searchForString 中的文字字符.如果没有这个， searchForString将被视为正则表达式的一部分。例如，如果 searchForString是 this? ，然后没有 \Q...\E它会 不是 匹配文字字符串 this? , 但要么 thi或 this ，这可能不是您想要的。 :)