python - 对字符串 Python 进行计数操作的计算成本是多少？

Question

例如:

'hello'.count('e')

这是 O(n) 吗？我猜它的工作方式是它扫描 'hello' 并在每次看到字母 'e' 时递增一个计数器。我怎么能不猜就知道呢？我尝试阅读源代码 here , 但在发现这个时卡住了:

def count(s, *args):
    """count(s, sub[, start[,end]]) -> int

    Return the number of occurrences of substring sub in string
    s[start:end].  Optional arguments start and end are
    interpreted as in slice notation.

    """
    return s.count(*args)

我在哪里可以了解 s.count(*args) 中执行的内容？

编辑:我理解 *args 在 Python 函数的上下文中做了什么。

Answer 1

str.count 以 native 代码实现，在 stringobject.c 中文件，委托(delegate)给 stringlib_count , 或 PyUnicode_Count它本身再次委托(delegate)给 stringlib_count。 stringlib_count 最终使用 fastsearch搜索字符串中子字符串的出现次数并计算这些次数。

对于单字符字符串(例如您的'e')，它被短路到以下代码路径:

for (i = 0; i < n; i++)
    if (s[i] == p[0]) {
        count++;
        if (count == maxcount)
            return maxcount;
    }
return count;

所以是的，这正是您假设对字符串序列进行简单迭代并计算子字符串出现的次数。

对于长于单个字符的搜索字符串，由于处理重叠等原因，它变得有点复杂，并且逻辑在 fastsearch 实现中隐藏得更深。但本质上是一样的:对字符串进行线性搜索。

是的，str.count 是线性时间，O(n)。如果你仔细想想，它就很有意义:为了知道一个子串在一个字符串中出现的频率，你需要查看每个可能的相同长度的子串。因此，对于长度为 1 的子字符串，您必须查看字符串中的每个字符，这给您带来了线性复杂度。

顺便说一句。有关底层快速搜索算法的更多信息，请参阅 this article on effbot.org .

---

对于只有单一 Unicode 字符串类型的 Python 3，实现的链接是:unicode_count使用 stringlib_count使用 fastsearch .