C语言中的strstr和正则表达式的区别

Question

假设我有一组用户ID、访问时间、程序名称和版本号的CSV字符串列表，例如：

1,1342995305,Some Program,0.98
1,1342995315,Some Program,1.20
2,1342985305,Another Program,15.8.3
1,1342995443,Bob's favorite game,0.98
3,1238543846,Something else,
...

假设这个列表不是一个文件，而是一个内存中的字符串列表。

现在假设我想找出某些程序被访问的频率，按照它们的版本号列出来。(例如，“Some Program version 1.20”被访问了193次，“Some Program version 0.98”被访问了876次，“Some Program 1.0.1”被访问了1,932次)

是构建正则表达式然后使用regexec()查找匹配并提取版本号更好，还是使用strstr()匹配程序名称加逗号，然后只读取字符串后面的部分作为版本号更好？如果有区别，假设我在Linux上使用GCC。

是否有性能差异？哪种方法更“好”或更“适当”？这是否重要？

- cegfault

Answer 1

使用strstr()函数-使用正则表达式来计算出现次数并不是一个好的选择，因为你仍然需要使用循环来实现这个功能。所以我建议你用一个简单的循环来搜索子字符串的位置，并在每次匹配后增加计数器和开始搜索位置。

- Ωmega

---

我会选择这种方法而不是其他答案中的方法，因为它将减少对 C 字符串函数的调用次数，相比于 strchr、strtok 等。一些字符串函数在第一次操作时调用 strlen，这可能会耗费一些时间。请注意，使用正则表达式并仅编译一次可能与 strstr 的速度相当。 - JimR

这是我一直倾向的方向。似乎strstr能够提高可读性和可维护性，因为它具有低复杂度（不需要准备工作）。然而，这是否意味着正则表达式应该仅用于复杂搜索，还是这取决于个人喜好？ - cegfault

@cegfault - 当你需要从一个输入中捕获一些/多个部分（例如解析等）时，正则表达式是一个正确的工具。但它不适合用于计算子字符串出现次数。 - Ωmega

@cegfault - 不，因为您知道这样的匹配应该是什么样子。正则表达式的一个很好的例子是日志文件，当您正在寻找访问站点某个部分的IP地址列表时，因此您不知道哪个IP地址将匹配，因为匹配基于url的匹配-因此通过正则表达式，您将搜索url，然后使用正则表达式模式捕获IP地址。在您的情况下，如果我正确理解了您的问题，您知道要搜索的所有程序名称及其版本列表，对吗？ - Ωmega

明白了。在这个例子中，我知道所有的程序名称，但不知道所有的版本。 - cegfault

Answer 2

strchr/memcmp是大多数libc版本实现strstr的方式。glibc中基于硬件的strstr实现效果更好。SSE2和SSE4.2（x86）指令集都可以比逐字节扫描更快地完成任务。如果您想了解如何实现，请查看我之前发布的一些博客文章 --- SSE2 and strstr 和 SSE2 and BNDM search --- 您可能会感兴趣。

- Mischa

Answer 3

使用 strtok() 函数将数据拆分成更加结构化的内容（例如结构体列表）。

- user82238

---

从strktok手册页面：此接口已被strsep（3）所取代。 - eyalm

strtok() 是 ANSI/ISO 标准，而 strsep() 不是。 - user82238

这是最慢且最臃肿的方法。此外，通常会有关于“strtok”被认为是有害的一些内容... - R.. GitHub STOP HELPING ICE

我认为在寻找定界符和提取子字符串方面使用hacky方法并不可取。如果只是一次性需求那还可以，但若你希望做更多的事情，具有更大的灵活性，将数据转化为更容易使用的形式会非常实用。 - user82238

Answer 4

我会两个都不用：我打赌使用 strchr() 查找逗号和 strcmp() 检查程序名称会更快。

至于性能，我预计字符串函数（strtok/strstr/strchr/strpos/strcmp...）的运行速度都差不多（即非常非常快），而正则表达式的运行速度会稍微慢一些，但仍然相当快。

真正的性能优势将来自于正确设计搜索：它必须运行多少次，程序数量是否固定等等？

例如，单个扫描获取所有程序的频率数据比单个扫描寻找特定程序要慢得多。但是，如果正确设计，所有后续查询其他程序的操作都会更快。

- LSerni

---

如果strstr实现得好，这不太可能更快。 - R.. GitHub STOP HELPING ICE

我认为所有这些函数或多或少都是相当的；要获得任何可观的收益，必须考虑整体搜索。如果搜索被重复执行，可以进行几个优化（例如，请参见http://blog.phusion.nl/2010/12/06/efficient-substring-searching/）。 - LSerni