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

Question

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

我有兴趣提高子串搜索实现的性能,

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

更多的答案指向了Boyer-Moore算法,Rabin-Karp算法的python实现.

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

Answer 1

你没有用'有效'来表示你的意思.你愿意做出哪些权衡？在初始化新字符串时,您是否准备为性能损失付出代价？开始搜索时？你会以更快的速度交换更多内存吗？

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或任何其他算法的专用搜索算法,因为这可能是他们特定问题域的更好选择.