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

我编写了以下 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,这种方法非常慢。为什么会这样?


慕少森
浏览 235回答 2
2回答

茅侃侃

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

白衣染霜花

这里的第一个问题是,尽管使用了 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_))。
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Python