如何提升 Go 的 strings.ToLower 的性能

[caizixian]

需要进行大小写不区别的子串检测（含中英文）

同样的代码比 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

[hooluupog]

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)
}

[nixuehan]

..这你都压榨。。 提升硬件把

[caizixian]

@hooluupog 想把一个 string 的大写英文字符转为小写

[shyling]

根据 char 的值判断应该会比 contains/in 之类的快一点吧

[chai2010]

如果真的在乎这点性能，建议重新实现函数，或者换语言

[fcicq]

明摆着应该用自动机

[sumhat]

这个性能真是在 ToLower 而不是 Contains ？

Keyword 数量太多的话建议使用 Trie 树

[abcdabcd987]

“需要进行大小写不区别的子串检测”

瓶颈不在与 ToLower ，而在于子串识别的算法。子串识别有两个很基本的算法：

Multiple text with single pattern: KMP Algorithm
Multiple text with multiple pattern: Aho-Corasick algorithm （ AC 自动机）

[abcdabcd987]

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)

[abcdabcd987]

https://hg.python.org/cpython/file/2.7/Objects/stringlib/fastsearch.h

Python 用了一个跑的比较快的匹配算法，所以表现起来比 golang 好一些

[caizixian]

@abcdabcd987 谢谢回复，我判断出是 ToLower 的原因是我把 ToLower 去掉后，总执行时间从 200 多 ms 下降到十几 ms

函数调用次数 200+k

[abcdabcd987]

@caizixian 原来是这样。不过这也不一定是 ToLower 的问题，也有可能是在原串上做匹配触发了某些条件使得字符串匹配变快了。

刚刚看了下 Strings.ToLower 的代码，发现可能确实 ToLower 会存在性能问题。他是直接用了个 map ，然后 mapper function 还要往下递归两三层。在这种情况下，编译器优化再厉害也是不如手写个 for 来得快的。

[caizixian]

@abcdabcd987 pprof 了一下

[Ouyangan]

@caizixian 你们一提到算法我写野生的就插不上话。

[mengzhuo]

@Ouyangan 学了就可以讨论了

lz 该用自动机啊！楼上的分析得很不错了。
而且直接返回 strings.Contains 不就好了？还 if 一下…
估计你还不知道：
1. string 是会复制的，多用 bytes
2. haystack 小于 cpu 的位长时对比只需要一个 cpu op

[caizixian]

@mengzhuo

用 if 判断是因为多个 substring 都要符合

[]byte 貌似不能解决中文处理问题，而[]rune 没有办法 split 或者像[]byte 一样 ReadBytes