如何提升 Go 的 strings.ToLower 的性能
caizixian · caizixian · 2016-06-10 19:16:18 +08:00 · 2585 次点击这是一个创建于 3088 天前的主题，其中的信息可能已经有所发展或是发生改变。
需要进行大小写不区别的子串检测（含中英文）
同样的代码比 Python 还慢点
func checkAgainstKeywords(s string) bool {
s = strings.ToLower(s)
for _, keyword := range keywords {
if !strings.Contains(s, keyword){
return false
}
}
return true
}
def multi_search(keywords, string):
lowerstring=string.lower()
for keyword in keywords:
if keyword not in lowerstring:
return False
return True
 |
1
hooluupog 2016-06-10 19:35:25 +08:00
Go 的字符串是 utf-8 的，所以要搞清楚你处理的是 unicode 还是 bytes 。如果是后者，可以这样：
func toLower(s string) string { b := make([]byte, len(s)) for i := range b { c := s[i] if c >= 'A' && c <= 'Z' { c += 'a' - 'A' } b[i] = c } return string(b) } |
 |
2
nixuehan 2016-06-10 19:51:44 +08:00
..这你都压榨。。 提升硬件把
|
 |
4
shyling 2016-06-10 20:34:36 +08:00
根据 char 的值判断应该会比 contains/in 之类的快一点吧
|
 |
5
chai2010 2016-06-10 20:35:17 +08:00 via iPhone
如果真的在乎这点性能，建议重新实现函数，或者换语言
|
 |
6
fcicq 2016-06-10 20:37:25 +08:00
明摆着应该用自动机
|
 |
7
sumhat 2016-06-10 21:05:37 +08:00
这个性能真是在 ToLower 而不是 Contains ？
Keyword 数量太多的话建议使用 Trie 树 |
 |
8
abcdabcd987 2016-06-10 21:13:42 +08:00
“需要进行大小写不区别的子串检测”
瓶颈不在与 ToLower ，而在于子串识别的算法。子串识别有两个很基本的算法： Multiple text with single pattern: KMP Algorithm Multiple text with multiple pattern: Aho-Corasick algorithm （ AC 自动机） |
|
9
abcdabcd987 2016-06-10 21:20:54 +08:00
https://golang.org/src/strings/strings_amd64.go?s=521:550#L3
这里可以看到 go 实现的是 Rabin-Karp algorithm 。假设文本长度为 n ，单个关键字长度为 m ，那么 Rabin-Karp 的方法最坏复杂度是 O(nm)，不过一般情况下是 O(n+m)。假设你这里有 w 个关键字，那么总的复杂度是 O(w*(n+m))。 如果关键字多并且文本比较长的话，改用 AC 自动机，复杂度就降到了 O(n + w*m) |
|
10
abcdabcd987 2016-06-10 21:36:45 +08:00
https://hg.python.org/cpython/file/2.7/Objects/stringlib/fastsearch.h
Python 用了一个跑的比较快的匹配算法，所以表现起来比 golang 好一些 |
 |
11
caizixian OP |
|
12
abcdabcd987 2016-06-10 21:47:48 +08:00
@caizixian 原来是这样。不过这也不一定是 ToLower 的问题，也有可能是在原串上做匹配触发了某些条件使得字符串匹配变快了。
刚刚看了下 Strings.ToLower 的代码，发现可能确实 ToLower 会存在性能问题。他是直接用了个 map ，然后 mapper function 还要往下递归两三层。在这种情况下，编译器优化再厉害也是不如手写个 for 来得快的。 |
|
13
caizixian OP |
Select Language