为什么我的迭代器实现效率很低？

Question

我编写了以下 python 脚本来计算一个字符(a)在无限字符串的前n 个字符中出现的次数。

from itertools import cycle

def count_a(str_, n):

    count = 0

    str_ = cycle(str_)

    for i in range(n):

        if next(str_) == 'a':

            count += 1

    return count

我对迭代器的理解是它们应该是高效的，但是对于非常大的n，这种方法非常慢。为什么会这样？

Answer 1

该cycle迭代器可能不那么有效，因为你想，文件说：使迭代器从可迭代对象返回元素并保存每个元素的副本。当迭代用完时，从保存的副本中返回元素。无限重复...注意，工具包的这个成员可能需要大量的辅助存储（取决于迭代的长度）。为什么不简化并且根本不使用迭代器？它会增加不必要的开销并且不会给您带来任何好处。您可以使用简单的方法轻松计算出现次数str_[:n].count('a')

Answer 2

这里的第一个问题是，尽管使用了 itertools，您仍然在执行显式的 Python 级 for 循环。要在使用 itertools 时获得 C 级速度提升，您希望将所有迭代保留在高速 itertools 中。所以让我们一步一步来，首先我们要得到一个有限字符串中的字符数。为此，您可以使用 itertools.islice 方法获取字符串中的前 n 个字符：str_first_n_chars&nbsp;=&nbsp;islice(cycle(str_),&nbsp;n)接下来您要计算字母 (a) 的出现次数，为此您可以对其中任何一个进行一些变体（您可能想要试验哪些变体更快）：count_a&nbsp;=&nbsp;sum(1&nbsp;for&nbsp;c&nbsp;in&nbsp;str_first_n_chars&nbsp;if&nbsp;c&nbsp;==&nbsp;'a') count_a&nbsp;=&nbsp;len(tuple(filter('a'.__eq__,&nbsp;str_first_n_chars))这一切都很好，但是对于非常大的 ，这仍然很慢，n因为对于非常大的，您需要迭代str_很多很多次n，例如n = 10**10000。换句话说，这个算法是O(n)。我们还可以进行最后一项改进。注意str_在每次迭代中 (a) 的数量从未真正改变。与其str_为 large迭代多次n，我们可以用一点数学来做一些更聪明的事情，这样我们只需要迭代str_两次。首先，我们计算单个片段中 (a) 的数量str_：count_a_single&nbsp;=&nbsp;str_.count('a')然后我们通过使用 divmod 函数找出需要迭代多少次&nbsp;str_才能获得长度n：iter_count,&nbsp;remainder&nbsp;=&nbsp;divmod(n,&nbsp;len(str_))然后我们可以将 iter_count 与 count_a_single 相乘，并在剩余长度中添加 (a) 的数量。我们在这里不需要循环或 islice 等，因为remainder < len(str_)count_a&nbsp;=&nbsp;iter_count&nbsp;*&nbsp;count_a_single&nbsp;+&nbsp;str_[:remainder].count('a')使用这种方法，算法的运行时性能仅在 str_ 的单个循环的长度上增长，而不是n。换句话说，这个算法是O(len(str_))。