如何在python中找到内置函数的复杂性

Question

我有问题的特殊情况,但是知道是否可以使用任何函数会很好.

所以我想在字符串中找到子字符串的位置.好的,在python中有一个find方法可以完全满足需要.

string.find(s,sub [,start [,end]])

返回s中找到substring sub的最低索引,使sub完全包含在s [start:end]中.失败时返回-1.开始和结束的默认值以及负值的解释与切片的默认值相同.

惊人的,但问题是,在一个大的字符串找到一个大子可以从运行O(n*m)到O(n)(这是一个巨大的交易)取决于算法.文档不提供有关时间复杂度的信息,也不提供有关基础算法的信息.

我看到如何解决这个问题的方法很少:

• 基准
• 转到源代码并尝试理解它

两者听起来都不容易(我希望有一种更简单的方法).那么如何才能找到内置函数的复杂性？

Answer 1

您说，“转到源代码并尝试理解它”，但这可能比您想象的要容易。一旦你看到实际的实现代码，在Objects/stringlib/fastsearch.h 中，你会发现：

/* fast search/count implementation, based on a mix between boyer-
   moore and horspool, with a few more bells and whistles on the top.
   for some more background, see: http://effbot.org/zone/stringlib.htm */

那里引用的URL 对算法及其复杂性进行了很好的讨论。