1

我正在扩展我之前的问题python 高效子字符串搜索，

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

我上一个问题的一些答案指出，子字符串搜索是通过使用受BM算法启发的fastsearch实现的，这里是源代码

更多答案向我指出了 Boyer-Moore 算法、Rabin-Karp 算法的 python 实现。

使用这些算法（BM， Rabin-Karp ）将c代码嵌入作为子字符串搜索的良好实现是否有效？

4

1 回答 1

10

您没有指定“高效”的含义。你愿意做出哪些取舍？在初始化新字符串时，您是否准备为性能损失付出代价？什么时候开始搜索？你会用更多的内存换取更快的速度吗？

Python 开发者在开发 Python 字符串库时设定了明确的目标：

  • 应该比所有测试用例（基于真实代码）的当前蛮力算法更快，包括 Jim Hugunin 的最坏情况测试
  • 设置开销小；快速路径中没有动态分配（速度为 O(m)，存储为 O(1)）
  • 良好情况下的亚线性搜索行为 (O(n/m))
  • 在最坏情况下不比当前算法差 (O(nm))
  • 应该适用于 8 位字符串和 16 位或 32 位 Unicode 字符串（无 O(σ) 依赖项）
  • 许多现实生活中的搜索应该是好的，极少数应该是最坏的情况
  • 相当简单的实现

因此，开发人员对搜索案例和设置案例的性能、存储要求以及维护效率设置了一些限制。这些边界排除了 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 或任何其他算法的专门搜索算法，因为这很可能是其特定问题域的更好选择。

于 2012-09-04T09:12:54.553 回答