почему моя реализация итератора очень неэффективна?
Я не использую const для параметрируемых значений. Вызывающему не важно, изменяете ли вы параметр или нет, это детализация реализации.
Что действительно важно, это отметить методы как const, если они не изменяют свой экземпляр. Сделайте это, когда вы идете, потому что иначе вы могли бы получить либо много const_cast & lt;> или вы могли бы обнаружить, что маркировка метода const требует изменения большого количества кода, потому что он вызывает другие методы, которые должны были быть отмечены как const.
Я также склонен отмечать локальные константы, если мне не нужно их модифицировать. Я считаю, что это облегчает понимание кода, упрощая идентификацию «движущихся частей».
2 ответа
Первая проблема здесь в том, что, несмотря на использование itertools, вы все еще делаете явный уровень python на уровне цикла. Чтобы получить ускорение уровня C при использовании itertools, вы хотите сохранить все итерации в высокоскоростных 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).
Есть одно последнее улучшение, которое мы могли бы сделать. Обратите внимание, что число (a) в str_ никогда не меняется на каждой итерации. Вместо того, чтобы многократно повторять str_ для большого n, мы можем сделать немного умнее с небольшим количеством математики, так что нам нужно только перебрать str_ дважды. Сначала мы посчитаем число (a) в одном отрезке str_:
count_a_single = str_.count('a')
Затем мы выясним, сколько раз нам пришлось бы пройти через str_, чтобы получить длину n по используя функцию divmod:
iter_count, remainder = divmod(n, len(str_))
, тогда мы можем просто умножить iter_count на count_a_single и добавить число (a) в оставшейся длине. Нам не нужен цикл или островок, и это здесь, потому что remainder < len(str_)
count_a = iter_count * count_a_single + str_[:remainder].count('a')
При использовании этого метода производительность алгоритма во время выполнения возрастает только на длину одного цикла str_, а не на n , Другими словами, этот алгоритм O(len(str_)).
Итератор cycle может быть не таким эффективным, как вы думаете, в документации говорится
Создать итератор, возвращающий элементы из итерируемого и сохраняющий копию каждого из них.
Когда итерация исчерпана, вернуть элементы из сохраненной копии. Повторяется бесконечно
... Обратите внимание, что этот элемент инструментария может потребовать значительного вспомогательного хранения (в зависимости от длины итерируемого).
Почему бы не упростить и просто не использовать итератор вообще? Это добавляет ненужные накладные расходы и не дает никакой выгоды. Вы можете легко посчитать события с помощью простого
str_[:n].count('a')