我編寫了以下 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，這種方法非常慢。為什么會這樣？
2 回答
白衣染霜花
TA貢獻1796條經驗 獲得超10個贊
這里的第一個問題是，盡管使用了 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_))。
添加回答
舉報
0/150
提交
取消