正则表达式和缓存：效率比较长期来看哪个更高？

本篇文章给大家分享《正则表达式和缓存：效率比较长期来看哪个更高？》，覆盖了Golang的常见基础知识，其实一个语言的全部知识点一篇文章是不可能说完的，但希望通过这些问题，让读者对自己的掌握程度有一定的认识(B 数)，从而弥补自己的不足，更好的掌握它。

我有一个服务，它在其内部的某个地方对某些内容是“允许”还是“不允许”（为了简单起见）进行验证，这是基于正则表达式匹配的。在伪代码中：

func isallowed(s string) {
  return regex.match(pattern, s)
}

现在，我知道正则表达式很慢，尽管 golang 有稍微简单化的正则表达式来满足其性能 sla，但它仍然不会与精确的字符串比较相同。而且我还知道我的函数将经常使用重复的值被调用。于是，我想到了做一个缓存：

var cache = make(map[string]bool)

func isAllowed(s string) {
  if result, found := cache[s]; found {
    return result
  }
  allowed := regex.match(pattern, s) // ignore syntax here; I'm simplifying this as pseudo-code
  cache[s] = allowed
  return allowed
}

所以现在如果字符串已经在我的缓存中，我可以避免正则表达式操作。但是...此缓存中可能会有很多值，例如数千或数万个值。因此，为了查找缓存中的值，我可能需要进行 10,000 次字符串比较，而不是单个正则表达式操作。

所以，我想我的问题是，字符串比较比 go 正则表达式匹配快多少？缓存对我的效率有帮助还是有损？

正确答案

这种技术称为记忆化。

[hash]map 查找的时间复杂度为 O(1) [constant]。 Go 的 regexp 包中的正则表达式保证在 O(N)（线性）时间内运行，其中 N 是输入的长度（请参阅 https://pkg.go.dev/regexp#pkg-overview 和 https://swtch.com/~rsc/regexp/regexp1.html 了解详细信息）。

这意味着您正在用时间换取空间：TANSTAAFL

至于 map 查找可能比正则表达式快多少，找出答案的唯一方法是使用代表实际输入的内容运行一些基准测试。

您可能需要考虑的一些问题：

• 从性能角度来看，此授权功能所花费的时间实际上很重要吗？
• 缓存命中和缓存未命中的频率是多少？
• 如果这是一个长时间运行的服务/守护进程，缓存是否会无限制地增长并最终导致您的服务/守护进程崩溃？
• 您是否想要使用更复杂的缓存，其中缓存条目会过期或被逐出，以将增长保持在限制范围内？

最后，

• 如果您出于授权目的而必须解析字符串中的位，也许更好的性能改进可能是重新考虑您的方法并将授权规则/标志维护为某种数据类型（结构或位图）用于执行授权测试的相关函数。

今天关于《正则表达式和缓存：效率比较长期来看哪个更高？》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！