在字符串中 快速查找

很多时候,我们需要在字符串中执行查找,以判断过滤指定的内容出来。比如过在落格输入法当中,就需要用辅码过滤出需要的候选词。

一般来说,查找和对比肯定是数字来的最快,不过在词库上总不能把所有的词汇都转换为数字(虽然理论上可行……)在字符串的搜索上,我们有很多种办法来实现,这里我就说一下我自己的思路:

Set<String>

由于我的词库辅码筛选只对两字或者三字词汇生效,那么我考虑把它们作为集合(Set)来检测,把词汇拆成单字。很遗憾,不说拆分的单独开销,本以为哈希表的set集合会很快,但速度并不行,可能它的优势是在于大量的时候吧,不过很可惜,它的速度是最慢的。

我用一个简短的集合来多次遍历然后统计时间,得到结果如下:

结果 8.90186786651611 值得一提的是,无论是命中还是丢失,速度是一样的。当然,速度慢也得考虑字符串比较自身的开销问题。

a.contains(“a”)

字符串自带了包含方法,它可以检测字符串 a 中是否包含了 "a" ,如果包含了,就返回 true 。这是很直接的办法:

用这样简单的遍历得到结果 7.06464505195618 秒。

那么能不能更快一些呢?我们换一种思路,如果说我们仅仅是查找,那其实还有一种方法可以考虑,那就是

a.range(of: “a”)

Swift 中 String  还有一个自带的方案,那就是获取指定字符串在另一字符串的范围,用来提取活着修改字符串用,如果找不到,那么就返回 nil 。

这里我们用返回值是否为空来判断字符串是否包含,速度会是多少呢?

执行的结果是 6.38309478759766 秒。显然,这种方法的查找速度是比上边两种专门的查找要快的。

总结

  • 用什么方法是手段不是目的,总之我们能得到想要的结果就好了,哪个好?最快的那个;
  • 多个功能类似可以互相替代的方法要做测试,不能靠猜来判断性能;
  • Set是唯一命中和丢失速度都一致的方法,但 range 丢失时也比 Set 要快;
  • 以上结果是建立在字符串查找上的,不是所有情况 :)

发表评论

电子邮件地址不会被公开。 必填项已用*标注