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

Question

我编写了以下 python 脚本来计算一个字符(a)在无限字符串的前n 个字符中出现的次数。from itertools import cycledef 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 = islice(cycle(str_), n)

接下来您要计算字母 (a) 的出现次数，为此您可以对其中任何一个进行一些变体（您可能想要试验哪些变体更快）：

count_a = sum(1 for c in str_first_n_chars if c == 'a')
count_a = len(tuple(filter('a'.__eq__, str_first_n_chars))

这一切都很好，但是对于非常大的 ，这仍然很慢，n因为对于非常大的，您需要迭代str_很多很多次n，例如n = 10**10000。换句话说，这个算法是O(n)。

---

我们还可以进行最后一项改进。注意str_在每次迭代中 (a) 的数量从未真正改变。与其str_为 large迭代多次n，我们可以用一点数学来做一些更聪明的事情，这样我们只需要迭代str_两次。首先，我们计算单个片段中 (a) 的数量str_：

count_a_single = str_.count('a')

然后我们通过使用 divmod 函数找出需要迭代多少次 str_才能获得长度n：

iter_count, remainder = divmod(n, len(str_))

然后我们可以将 iter_count 与 count_a_single 相乘，并在剩余长度中添加 (a) 的数量。我们在这里不需要循环或 islice 等，因为remainder < len(str_)

count_a = iter_count * count_a_single + str_[:remainder].count('a')

使用这种方法，算法的运行时性能仅在 str_ 的单个循环的长度上增长，而不是n。换句话说，这个算法是O(len(str_))。