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

Question

我有问题的特例，但很高兴知道是否可以实现任何功能。

所以我想找到一个子串在字符串中的位置。好的，在 python 中有一个 find method这正是需要的。

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

Return the lowest index in s where the substring sub is found such that sub is wholly contained in s[start:end]. Return -1 on failure. Defaults for start and end and interpretation of negative values is the same as for slices.

太神奇了，但问题是在一个大字符串中找到一个大子字符串可以从 O(n*m) 运行到 O(n)(这是一个大笔交易)depending on the algorithm .文档没有提供有关时间复杂度的信息，也没有提供有关底层算法的信息。

我看到很少有方法可以解决这个问题:

• 基准
• 查看源代码并尝试理解它

两者听起来都不太容易(我希望有更简单的方法)。那么我怎样才能找到内置函数的复杂性呢？

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 referenced there对算法及其复杂性进行了很好的讨论。