在C++中高效存储和检索分类字符串字面量

Question

在C++中高效存储和检索分类字符串字面量

c++stringmemorystorage

4

注意：这是对此问题的跟进。

我有一个“遗留”程序，需要对大块HTML进行数百个字符串匹配。例如，如果HTML与20多个字符串之一匹配，则执行某些操作。如果它与另外4个字符串之一匹配，则执行其他操作。有50-100组这些字符串需要匹配这些HTML块（通常是整个页面）。

我正在努力重构这个代码混乱，并尝试找到一个好的方法来进行所有这些匹配。

这段代码的性能要求非常严格。在进行这些匹配时，它不能等待I/O，因此它们需要在内存中。同时可能会有100多个该进程的副本同时运行，因此启动时的大量I/O可能导致其他副本的I/O缓慢。

考虑到这些要求，最有效的方法是仅将这些字符串的一个副本存储在RAM中（请参见我的上一篇链接问题）。

该程序当前在Windows上使用Microsoft编译器运行，但我希望保持解决方案尽可能跨平台，因此我不认为我想使用PE资源文件或其他内容。

映射外部文件可能有效，但然后我必须解决程序版本和数据版本保持同步的问题。通常情况下，一个不会改变而不影响另一个。此外，这需要一些文件“格式”，这增加了一层我宁愿没有的复杂性。

因此，在所有这些前言之后，似乎最好的解决方案是拥有一堆字符串数组，然后可以对其进行迭代。由于具有上述要求，这似乎有点凌乱，因为代码和数据混合在一起，但是是否有更好的处理这种情况的方法呢？

- thelsdj

我并不完全确定我理解你第二段话的意思（关于你的程序实际上做了什么的部分）。如果你能澄清一下，也许我们可以想出更有帮助的想法。 - nategoose

高效的存储还是检索？标题说的是存储，但文本更像是检索。 - µBio

希望我对第一个大段落的编辑能够澄清事情。 - thelsdj

这些匹配的字符串中是否存在许多共同元素？例如，当您看到HTML的前三个字符时，是否会消除1000个匹配模式中的990个？或者大约一半的字符串以<body>开头？ - jkerian

是的，有解决版本问题的方法，但我还没有遇到过 mmap 文件不会引起更多问题的情况。我应该把查找一组匹配字符串的位置存储在哪里？显然，有一些选项，比如在文件开头建立索引等，但这个问题是否值得创建自定义文件格式等操作呢？ - thelsdj

显示剩余2条评论

3个回答

1

如果需要匹配的字符串可以在编译时锁定，您应该考虑使用像lex这样的标记生成器来扫描输入以进行匹配。如果您不熟悉它，lex会接受一个源文件，其中包含一些正则表达式（包括最简单的正则表达式-字符串字面量）和C操作代码，以在找到匹配项时执行。它经常用于构建编译器和类似程序，并且还有几个类似的程序可供使用（如flex和antlr）。lex构建状态机表，然后生成有效的C代码，用于将输入与这些状态表所代表的正则表达式进行匹配（默认情况下，输入是标准输入，但您可以更改此设置）。使用此方法可能不会导致您担心的程序的不同实例之间在内存中重复字符串（或其他数据）。您可能可以轻松地从现有代码中的字符串字面量生成正则表达式，但是重新设计程序以使用lex生成的代码可能需要花费很多工作。

如果您需要匹配的字符串随时间而变化，则有一些正则表达式库可以在运行时编译正则表达式，但这些库会使用大量RAM，并且根据程序的架构，这些库可能会在程序的不同实例之间重复。

使用正则表达式方法而不是大量的strcmp调用的好处在于，如果您有以下模式：

"string1"
"string2"
"string3"

以及输入：

"string2"

对于DFA（确定有限状态自动机）正则表达式系统（如lex），"string"的部分匹配只需进行一次，这可能会加速您的系统。构建这些东西确实需要lex大量的工作，但所有的艰苦工作都是在前期完成的。

- nategoose

lex是一个有趣的想法，我之前没有考虑过。虽然我认为DFA正则表达式系统对我并没有太多好处，因为字符串通常不足以共享匹配的一部分（大多数可能有90%是唯一的，包括开头）。这可能是第二步，一旦我将匹配重构和组织得更好，到达了“如果（匹配）则执行”的代码路径不再是所有唯一的需要特殊处理的路径的程度。 - thelsdj

即使在第一个字符上进行分离也可以节省大量时间。但是，某些版本的_lex_可能仍然会尝试为每个子字符串中的每个字节添加新的表状态，即使没有可能导致该字符只有两个（或几个）下一个状态。这可能意味着非常大的表。 - nategoose

0

这些字面字符串是存储在文件中的吗？如果是的话，正如您所建议的那样，您最好使用内存映射文件来共享程序的数百个实例之间的文件副本。此外，您可能希望尝试调整工作集大小，以尝试减少页面错误次数，但考虑到您有如此多的实例，这可能会证明是适得其反的（而且除了您的程序需要配额特权来调整工作集大小）。

还有其他技巧可以尝试优化IO性能，例如分配大页面，但这取决于您的文件大小和授予程序的特权。

底线是您需要进行实验，看看哪种方法最有效，并记得在每次更改后进行测量 :)...

- Atul

目前它们都是内联在代码中的，例如：if (htmlPage.find("string to match") != htmlPage.npos).... 这非常糟糕。我不想处理一些外部文件格式，所以我认为字符串数组是清理这个问题的好第一步。 - thelsdj

@nategoose 你说得对，我们使用C++编译器和std::string来处理很多事情，所以我指定C是不真实的，我已经改变了。这是一个丑陋的“遗留”应用程序的坏/好例子。我认为它最初是以C++编写的，以便利用C++库和非常基本的STL用法（字符串），但是应用程序的组织方式只是将许多函数混在一起，没有任何类设计。 - thelsdj

@nategoose 但我应该指出，我正在寻找的问题和答案并没有使用任何特定于C ++的内容，也适用于C。 - thelsdj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jkerian · Accepted Answer

我不确定目前的实现有多慢。因此，在不了解需要何种优化水平的情况下，建议优化措施是很困难的。

然而，鉴于此，我可能会建议采用两阶段方法。将字符串列表编译成基数树，然后将此树保存到某个自定义格式中（对于您的目的来说，XML可能足够好）。

然后，您的进程启动应该包括读取基数树和匹配。如果您想/需要优化树的内存存储，那么可以将其作为一个单独的项目完成，但在我看来，改进匹配算法将更有效地利用时间。从某些方面来说，这是一个“自己打造正则表达式系统”的想法。与建议使用解析器生成器类似。

编辑：我曾经使用过类似于此的东西，其中作为预编译步骤，定制脚本生成了一些相对优化的结构，并将其保存到一个大的char*数组中。(显然不能太大，但这是另一个选项)

这个想法是保留列表（使维护相对容易），但是在运行时通过预编译步骤加速访问。