从动态规划的角度去看KMP

然而还是被Go内置搜索吊打

背景

最近遇到点挑战,就是需要从一个长文本的text中找到一个匹配的Creative文件名,在考虑了不需要模糊匹配的情况下,首先homebrew了一个brute force的算法,然而在文本巨长的情况下搜索效率不尽人意。

于是就想到以前碰到过kmp算法,然后又恰巧看到朋友圈有位朋友解释了一下kmp。突然就觉得豁然开朗。

这位大神的解法 大神文章

Brute Force

这个方式比较好想, 这里我们为了方便讲述,需要搜索的文本我们称为txt,需要被匹配的文本我们称为pattern。 遍历整个txt,每个字母从pattern第一个字母去重复匹配。每次失败了,搜索都得从pattern开头重新搜索。

于是就能想到如果能从pattern出发,构建一个状态机,根据input (下一个被搜字母)进行状态转换。为了搜索状态的变化更加快速,使用了dynamic programming的思想提前构造好状态机的各个状态。

看完那篇文章真的make my day!

然而还是被Go吊打了

是的毫不犹豫我就用golang写了,并且去和golang内置的strings.Index 方法对比。结果你们猜。。。 被摁在地上摩擦。。。

先上测试结果,builtin strings.Index方法速度奇快无比。。。因为用了rabin karp优化。 当然因为rabin karp有collision风险(在hash 值相同的情况下原文不一样),那个时候可能就会被更stable的kmp反杀。

Run benchmark command go test -bench=. -run=XXX

goos: darwin
goarch: amd64
BenchmarkBuiltinSearch-4   	21104456	        55.7 ns/op
BenchmarkKmpSearch-4       	  101371	     10812 ns/op
PASS
ok  	_/Users/xxxxxx/Downloads/kmp	2.664s

Github Gist 其实写这个记录,就是想测试一下shortcode gist。

Avatar
Marco Huang
Yet Another Engineer
comments powered by Disqus