Python:通过嵌入复杂的算法改进子字符串搜索

Question

我正在扩展我之前的问题 python efficient substring search ,

我有兴趣提高子字符串搜索实现的性能，

我上一个问题的一些答案指出，子字符串搜索是通过使用受 B-M 算法启发的 fastsearch 实现的，这是 source code

更多答案让我找到了 Boyer–Moore 算法、Rabin–Karp 算法的 python 实现。

嵌入 C 代码作为使用这些算法(B-M、Rabin-Karp)的子字符串搜索的良好实现是否有效？

Answer 1

您没有具体说明“高效”的含义。您愿意做出哪些权衡？您准备好在初始化新字符串时付出性能损失的代价吗？什么时候开始搜索？您会用更多的内存换取更快的速度吗？

python 开发者集clear goals当他们开发 python 字符串库时:

• should be faster than the current brute-force algorithm for all test cases (based on real-life code), including Jim Hugunin’s worst-case test
• small setup overhead; no dynamic allocation in the fast path (O(m) for speed, O(1) for storage)
• sublinear search behaviour in good cases (O(n/m))
• no worse than the current algorithm in worst case (O(nm))
• should work well for both 8-bit strings and 16-bit or 32-bit Unicode strings (no O(σ) dependencies)
• many real-life searches should be good, very few should be worst case
• reasonably simple implementation

因此，开发人员对搜索案例和设置案例的性能、存储要求以及维护效率设置了一些限制。这些边界排除了 Boyer-Moore(因为它需要对搜索的字符串进行预处理、启动成本和存储成本)，虽然我没有看到开发人员考虑过 Rabin-Karp 的证据，但它可以在相同的情况下被排除理由(您需要创建哈希并存储它们)。

边界是根据 很多 python 内部结构和使用经验设置的。以上总结并非凭空而来，只是对那次经历的总结。

现在，如果您在特定情况下可以设置不同的权衡取舍，那么可以肯定的是，不同算法的 C 实现很可能胜过标准 Python 实现。但根据一组不同的标准，它会更有效率。

无论如何，Python 搜索算法处理小字符串的情况。如果您尝试将其应用于大型 文本主体，算法将无法像针对大型文本做出不同选择的算法那样执行得很好。如果您必须在 10,000,000 个文档中搜索文本，您会希望使用某种索引解决方案，而不是微不足道的小型 Python 字符串搜索。

将其与使用默认排序实现对包含 100 个项目的列表进行排序，与对 10,000,000,000 个整数进行排序进行比较。在后一种情况下，有一些排序实现可以轻松击败默认的 Python 产品。

还应该指出，Python 有算法创新的历史； Python 中的标准排序算法是 TimSort ，一种由 Tim Peters 发明的新算法，以适应 Python 解释器必须处理的实用现实环境。该算法已成为 Java 和 Android 平台的默认算法。因此，我倾向于相信 Python 核心开发人员的决定。

据我所知，没有人嵌入不同的实现，因为替换默认设置不会在不修补 Python C 代码的情况下工作。当然，您可以轻松创建实现不同搜索算法的专用字符串类型。很可能有一些库将 C 语言用于专门的搜索算法，这些算法使用 Boyer-Moore、Rabin-Karp 或任何其他算法，因为对于他们的特定问题领域来说，这可能是更好的选择。