itertools.md
1> **Источник:** https://python-all.ru/3/library/itertools.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# `itertools` – Функции, создающие итераторы для эффективного перебора89---1011Этот модуль реализует ряд строительных блоков [итераторов](https://python-all.ru/3/glossary.html#term-iterator), вдохновлённых конструкциями из APL, Haskell и SML. Каждый из них переработан в форму, подходящую для Python.1213Модуль стандартизирует основной набор быстрых и эффективных по памяти инструментов, которые полезны сами по себе или в комбинации. Вместе они образуют «алгебру итераторов», позволяющую создавать специализированные инструменты кратко и эффективно на чистом Python.1415Например, SML предоставляет инструмент табуляции: `tabulate(f)`, который порождает последовательность `f(0), f(1), ...`. Того же эффекта можно достичь в Python скомбинировав [`map()`](https://python-all.ru/3/library/functions.html#map) и [`count()`](https://python-all.ru/3/library/itertools.html#itertools.count) для получения `map(f, count())`.1617**Основные итераторы:**1819| Итератор | Аргументы | Результаты | Пример |20| --- | --- | --- | --- |21| [`accumulate()`](https://python-all.ru/3/library/itertools.html#itertools.accumulate) | p \[,func\] | p0, p0+p1, p0+p1+p2, … | `accumulate([1,2,3,4,5]) → 1 3 6 10 15` |22| [`batched()`](https://python-all.ru/3/library/itertools.html#itertools.batched) | p, n | (p0, p1, …, p\_n-1), … | `batched('ABCDEFG', n=3) → ABC DEF G` |23| [`chain()`](https://python-all.ru/3/library/itertools.html#itertools.chain) | p, q, … | p0, p1, … plast, q0, q1, … | `chain('ABC', 'DEF') → A B C D E F` |24| [`chain.from_iterable()`](https://python-all.ru/3/library/itertools.html#itertools.chain.from_iterable) | iterable | p0, p1, … plast, q0, q1, … | `chain.from_iterable(['ABC', 'DEF']) → A B C D E F` |25| [`compress()`](https://python-all.ru/3/library/itertools.html#itertools.compress) | data, selectors | (d\[0\] if s\[0\]), (d\[1\] if s\[1\]), … | `compress('ABCDEF', [1,0,1,0,1,1]) → A C E F` |26| [`count()`](https://python-all.ru/3/library/itertools.html#itertools.count) | \[start\[, step\]\] | start, start+step, start+2\*step, … | `count(10) → 10 11 12 13 14 ...` |27| [`cycle()`](https://python-all.ru/3/library/itertools.html#itertools.cycle) | p | p0, p1, … plast, p0, p1, … | `cycle('ABCD') → A B C D A B C D ...` |28| [`dropwhile()`](https://python-all.ru/3/library/itertools.html#itertools.dropwhile) | predicate, seq | seq\[n\], seq\[n+1\], начиная с момента, когда предикат не выполняется | `dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8` |29| [`filterfalse()`](https://python-all.ru/3/library/itertools.html#itertools.filterfalse) | predicate, seq | элементы seq, для которых predicate(elem) не выполняется | `filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8` |30| [`groupby()`](https://python-all.ru/3/library/itertools.html#itertools.groupby) | iterable\[, key\] | подитераторы, сгруппированные по значению key(v) | `groupby(['A','B','DEF'], len) → (1, A B) (3, DEF)` |31| [`islice()`](https://python-all.ru/3/library/itertools.html#itertools.islice) | seq, \[start,\] stop \[, step\] | elements from seq\[start:stop:step\] | `islice('ABCDEFG', 2, None) → C D E F G` |32| [`pairwise()`](https://python-all.ru/3/library/itertools.html#itertools.pairwise) | iterable | (p\[0\], p\[1\]), (p\[1\], p\[2\]) | `pairwise('ABCDEFG') → AB BC CD DE EF FG` |33| [`repeat()`](https://python-all.ru/3/library/itertools.html#itertools.repeat) | elem \[,n\] | elem, elem, elem, … бесконечно или до n раз | `repeat(10, 3) → 10 10 10` |34| [`starmap()`](https://python-all.ru/3/library/itertools.html#itertools.starmap) | func, seq | func(\*seq\[0\]), func(\*seq\[1\]), … | `starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000` |35| [`takewhile()`](https://python-all.ru/3/library/itertools.html#itertools.takewhile) | predicate, seq | seq\[0\], seq\[1\], пока predicate не вернёт ложь | `takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4` |36| [`tee()`](https://python-all.ru/3/library/itertools.html#itertools.tee) | it, n | it1, it2, … itn разделяет один итератор на n | `tee('ABC', 2) → A B C, A B C` |37| [`zip_longest()`](https://python-all.ru/3/library/itertools.html#itertools.zip_longest) | p, q, … | (p\[0\], q\[0\]), (p\[1\], q\[1\]), … | `zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-` |3839**Комбинаторные итераторы:**4041| Итератор | Аргументы | Результаты |42| --- | --- | --- |43| [`product()`](https://python-all.ru/3/library/itertools.html#itertools.product) | p, q, … \[repeat=1\] | декартово произведение, эквивалентно вложенному циклу for |44| [`permutations()`](https://python-all.ru/3/library/itertools.html#itertools.permutations) | p\[, r\] | кортежи длиной r, все возможные перестановки, без повторяющихся элементов |45| [`combinations()`](https://python-all.ru/3/library/itertools.html#itertools.combinations) | p, r | кортежи длиной r, в отсортированном порядке, без повторяющихся элементов |46| [`combinations_with_replacement()`](https://python-all.ru/3/library/itertools.html#itertools.combinations_with_replacement) | p, r | кортежи длиной r, в отсортированном порядке, с повторяющимися элементами |4748| Примеры | Результаты |49| --- | --- |50| `product('ABCD', repeat=2)` | `AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD` |51| `permutations('ABCD', 2)` | `AB AC AD BA BC BD CA CB CD DA DB DC` |52| `combinations('ABCD', 2)` | `AB AC AD BC BD CD` |53| `combinations_with_replacement('ABCD', 2)` | `AA AB AC AD BB BC BD CC CD DD` |5455## Функции itertools5657Следующие функции создают и возвращают итераторы. Некоторые из них дают потоки бесконечной длины, поэтому их следует использовать только в функциях или циклах, которые обрезают поток.5859#### `itertools.accumulate(iterable[, function, *, initial=None])`6061Создаёт итератор, возвращающий накопленные суммы или накопленные результаты других бинарных функций.6263Если *function* не указана, по умолчанию используется сложение. *Function* должна принимать два аргумента: накопленное значение и очередной элемент из *iterable*.6465Если указано начальное значение *initial*, накопление начнётся с него, и в результате будет на один элемент больше, чем во входном итерируемом объекте.6667Примерно эквивалентно:6869```python70def accumulate(iterable, function=operator.add, *, initial=None):71 'Return running totals'72 # accumulate([1,2,3,4,5]) → 1 3 6 10 1573 # accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 11574 # accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 1207576 iterator = iter(iterable)77 total = initial78 if initial is None:79 try:80 total = next(iterator)81 except StopIteration:82 return8384 yield total85 for element in iterator:86 total = function(total, element)87 yield total88```8990Чтобы вычислить текущий минимум, задайте *function* равной [`min()`](https://python-all.ru/3/library/functions.html#min). Для текущего максимума – *function* [`max()`](https://python-all.ru/3/library/functions.html#max). Для текущего произведения – *function* [`operator.mul()`](https://python-all.ru/3/library/operator.html#operator.mul). Для построения [таблицы амортизации](https://python-all.ru/3/library/itertools.html) накопите проценты и примените платежи:9192```pycon93>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]94>>> list(accumulate(data, max)) # текущий максимум95[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]96>>> list(accumulate(data, operator.mul)) # текущее произведение97[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]9899# Amortize a 5% loan of 1000 with 10 annual payments of 90100>>> update = lambda balance, payment: round(balance * 1.05) - payment101>>> list(accumulate(repeat(90, 10), update, initial=1_000))102[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]103```104105См. [`functools.reduce()`](https://python-all.ru/3/library/functools.html#functools.reduce) – похожая функция, возвращающая только итоговое накопленное значение.106107Добавлено в версии 3.2.108109Изменено в версии 3.3: Добавлен необязательный параметр *function*.110111Изменено в версии 3.8: Добавлен необязательный параметр *initial*.112113#### `itertools.batched(iterable, n, *, strict=False)`114115Группирует данные из *iterable* в кортежи длины *n*. Последняя группа может быть короче *n*.116117Если *strict* равен True, будет вызвано исключение [`ValueError`](https://python-all.ru/3/library/exceptions.html#ValueError), если последняя группа короче *n*.118119Перебирает входной iterable и накапливает данные в кортежи размером до *n*. Входные данные обрабатываются лениво – ровно столько, чтобы заполнить одну группу. Результат возвращается сразу, как только группа заполнена или входной iterable исчерпан:120121```pycon122>>> flattened_data = ['roses', 'red', 'violets', 'blue', 'sugar', 'sweet']123>>> unflattened = list(batched(flattened_data, 2))124>>> unflattened125[('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]126```127128Примерно эквивалентно:129130```python131def batched(iterable, n, *, strict=False):132 # batched('ABCDEFG', 3) → ABC DEF G133 if n < 1:134 raise ValueError('n must be at least one')135 iterator = iter(iterable)136 while batch := tuple(islice(iterator, n)):137 if strict and len(batch) != n:138 raise ValueError('batched(): incomplete batch')139 yield batch140```141142Добавлено в версии 3.12.143144Изменено в версии 3.13: Добавлен параметр *strict*.145146#### `itertools.chain(*iterables)`147148Создаёт итератор, который возвращает элементы из первого iterable, пока он не исчерпан, затем переходит к следующему, и так до исчерпания всех. Это объединяет несколько источников данных в один итератор. Примерная реализация:149150```python151def chain(*iterables):152 # chain('ABC', 'DEF') → A B C D E F153 for iterable in iterables:154 yield from iterable155```156157#### `classmethod chain.from_iterable(iterable)`158159Альтернативный конструктор для [`chain()`](https://python-all.ru/3/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного аргумента iterable, который вычисляется лениво. Примерная реализация:160161```python162def from_iterable(iterables):163 # chain.from_iterable(['ABC', 'DEF']) → A B C D E F164 for iterable in iterables:165 yield from iterable166```167168#### `itertools.combinations(iterable, r)`169170Возвращает подпоследовательности элементов длины *r* из входного *iterable*.171172Результат является подмножеством [`product()`](https://python-all.ru/3/library/itertools.html#itertools.product), в котором оставлены только те элементы, которые являются подпоследовательностями *iterable*. Длина результата задаётся выражением [`math.comb()`](https://python-all.ru/3/library/math.html#math.comb), которое равно `n! / r! / (n - r)!`, если `0 ≤ r ≤ n`, или нулю, если `r > n`.173174Кортежи-комбинации порождаются в лексикографическом порядке по порядку входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи также будут отсортированы.175176Элементы считаются уникальными по позиции, а не по значению. Если входные элементы уникальны, то в каждой комбинации не будет повторяющихся значений.177178Примерно эквивалентно:179180```python181def combinations(iterable, r):182 # combinations('ABCD', 2) → AB AC AD BC BD CD183 # combinations(range(4), 3) → 012 013 023 123184185 pool = tuple(iterable)186 n = len(pool)187 if r > n:188 return189 indices = list(range(r))190191 yield tuple(pool[i] for i in indices)192 while True:193 for i in reversed(range(r)):194 if indices[i] != i + n - r:195 break196 else:197 return198 indices[i] += 1199 for j in range(i+1, r):200 indices[j] = indices[j-1] + 1201 yield tuple(pool[i] for i in indices)202```203204#### `itertools.combinations_with_replacement(iterable, r)`205206Возвращает подпоследовательности элементов длины *r* из входного *iterable*, допуская повторение отдельных элементов.207208Результат является подмножеством [`product()`](https://python-all.ru/3/library/itertools.html#itertools.product), в котором оставлены только те элементы, которые являются подпоследовательностями (с возможными повторениями) *iterable*. Количество возвращаемых подпоследовательностей равно `(n + r - 1)! / r! / (n - 1)!`, если `n > 0`.209210Кортежи-комбинации порождаются в лексикографическом порядке по порядку входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи будут отсортированы.211212Элементы считаются уникальными по позиции, а не по значению. Если входные элементы уникальны, то порождённые комбинации тоже будут уникальны.213214Примерно эквивалентно:215216```python217def combinations_with_replacement(iterable, r):218 # combinations_with_replacement('ABC', 2) → AA AB AC BB BC CC219220 pool = tuple(iterable)221 n = len(pool)222 if not n and r:223 return224 indices = [0] * r225226 yield tuple(pool[i] for i in indices)227 while True:228 for i in reversed(range(r)):229 if indices[i] != n - 1:230 break231 else:232 return233 indices[i:] = [indices[i] + 1] * (r - i)234 yield tuple(pool[i] for i in indices)235```236237Добавлено в версии 3.1.238239#### `itertools.compress(data, selectors)`240241Создаёт итератор, который возвращает элементы из *data*, для которых соответствующий элемент из *selectors* истинен. Останавливается, когда исчерпан либо *data*, либо *selectors*. Примерная реализация:242243```python244def compress(data, selectors):245 # compress('ABCDEF', [1,0,1,0,1,1]) → A C E F246 return (datum for datum, selector in zip(data, selectors) if selector)247```248249Добавлено в версии 3.1.250251#### `itertools.count(start=0, step=1)`252253Создаёт итератор, возвращающий равномерно расположенные значения, начиная с *start*. Может использоваться с [`map()`](https://python-all.ru/3/library/functions.html#map) для генерации последовательных точек данных или с [`zip()`](https://python-all.ru/3/library/functions.html#zip) для добавления номеров по порядку. Примерная реализация:254255```python256def count(start=0, step=1):257 # count(10) → 10 11 12 13 14 ...258 # count(2.5, 0.5) → 2.5 3.0 3.5 ...259 n = start260 while True:261 yield n262 n += step263```264265При подсчёте с числами с плавающей точкой иногда лучшей точности можно добиться, используя мультипликативный код, например: `(start + step * i for i in count())`.266267Изменено в версии 3.1: Добавлен аргумент *step* и разрешены нецелые аргументы.268269#### `itertools.cycle(iterable)`270271Создаёт итератор, который возвращает элементы из *iterable* и сохраняет копию каждого. Когда iterable исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Примерная реализация:272273```python274def cycle(iterable):275 # cycle('ABCD') → A B C D A B C D A B C D ...276277 saved = []278 for element in iterable:279 yield element280 saved.append(element)281282 while saved:283 for element in saved:284 yield element285```286287Этот инструмент может потребовать значительного объёма дополнительной памяти (в зависимости от длины iterable).288289#### `itertools.dropwhile(predicate, iterable)`290291Создаёт итератор, который пропускает элементы из *iterable*, пока *predicate* истинен, а затем возвращает все оставшиеся элементы. Примерная реализация:292293```python294def dropwhile(predicate, iterable):295 # dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8296297 iterator = iter(iterable)298 for x in iterator:299 if not predicate(x):300 yield x301 break302303 for x in iterator:304 yield x305```306307Обратите внимание: этот итератор не выдаёт *ни одного* элемента, пока предикат впервые не станет ложным, поэтому время запуска может быть большим.308309#### `itertools.filterfalse(predicate, iterable)`310311Создаёт итератор, который фильтрует элементы из *iterable*, возвращая только те, для которых *predicate* возвращает ложное значение. Если *predicate* равен `None`, возвращает элементы, которые являются ложными. Примерная реализация:312313```python314def filterfalse(predicate, iterable):315 # filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8316317 if predicate is None:318 predicate = bool319320 for x in iterable:321 if not predicate(x):322 yield x323```324325#### `itertools.groupby(iterable, key=None)`326327Make an iterator that returns consecutive keys and groups from the *iterable*. The *key* is a function computing a key value for each element. If not specified or is `None`, *key* defaults to an identity function and returns the element unchanged. Generally, the iterable needs to already be sorted on the same key function.328329Работа `groupby()` аналогична фильтру `uniq` в Unix. Она создает разрыв или новую группу каждый раз, когда изменяется значение ключевой функции (поэтому обычно необходимо отсортировать данные с помощью той же ключевой функции). Такое поведение отличается от SQL GROUP BY, которая объединяет общие элементы независимо от порядка их ввода.330331Возвращаемая группа сама является итератором, который использует общий исходный итерируемый объект с `groupby()`. Поскольку источник общий, при продвижении объекта `groupby()` предыдущая группа перестает быть видимой. Поэтому, если эти данные понадобятся позже, их следует сохранить в виде списка:332333```python334groups = []335uniquekeys = []336data = sorted(data, key=keyfunc)337for k, g in groupby(data, keyfunc):338 groups.append(list(g)) # Сохранить групповой итератор как список339 uniquekeys.append(k)340```341342`groupby()` примерно эквивалентно:343344```python345def groupby(iterable, key=None):346 # [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B347 # [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC D348349 keyfunc = (lambda x: x) if key is None else key350 iterator = iter(iterable)351 exhausted = False352353 def _grouper(target_key):354 nonlocal curr_value, curr_key, exhausted355 yield curr_value356 for curr_value in iterator:357 curr_key = keyfunc(curr_value)358 if curr_key != target_key:359 return360 yield curr_value361 exhausted = True362363 try:364 curr_value = next(iterator)365 except StopIteration:366 return367 curr_key = keyfunc(curr_value)368369 while not exhausted:370 target_key = curr_key371 curr_group = _grouper(target_key)372 yield curr_key, curr_group373 if curr_key == target_key:374 for _ in curr_group:375 pass376```377378#### `itertools.islice(iterable, stop)`379380#### `itertools.islice(iterable, start, stop[, step])`381382Создает итератор, который возвращает выбранные элементы из итерируемого объекта. Работает как срез последовательности, но не поддерживает отрицательные значения для *start*, *stop* или *step*.383384Если *start* равен нулю или `None`, итерация начинается с нуля. В противном случае элементы из итерируемого объекта пропускаются до достижения *start*.385386Если *stop* равен `None`, итерация продолжается до тех пор, пока входной объект не будет исчерпан. В противном случае она останавливается на указанной позиции.387388Если *step* равен `None`, шаг по умолчанию равен единице. Элементы возвращаются последовательно, если только *step* не больше единицы, что приводит к пропуску элементов.389390Примерно эквивалентно:391392```python393def islice(iterable, *args):394 # islice('ABCDEFG', 2) → A B395 # islice('ABCDEFG', 2, 4) → C D396 # islice('ABCDEFG', 2, None) → C D E F G397 # islice('ABCDEFG', 0, None, 2) → A C E G398399 s = slice(*args)400 start = 0 if s.start is None else s.start401 stop = s.stop402 step = 1 if s.step is None else s.step403 if start < 0 or (stop is not None and stop < 0) or step <= 0:404 raise ValueError405406 indices = count() if stop is None else range(max(start, stop))407 next_i = start408 for i, element in zip(indices, iterable):409 if i == next_i:410 yield element411 next_i += step412```413414Если входной объект является итератором, то полное потребление *islice* продвигает входной итератор на `max(start, stop)` шагов независимо от значения *step*.415416#### `itertools.pairwise(iterable)`417418Возвращает последовательные перекрывающиеся пары, взятые из входного *iterable*.419420Количество кортежей из двух элементов в выходном итераторе будет на один меньше, чем количество входных элементов. Он будет пустым, если входной итерируемый объект содержит менее двух значений.421422Примерно эквивалентно:423424```python425def pairwise(iterable):426 # pairwise('ABCDEFG') → AB BC CD DE EF FG427428 iterator = iter(iterable)429 a = next(iterator, None)430431 for b in iterator:432 yield a, b433 a = b434```435436Добавлено в версии 3.10.437438#### `itertools.permutations(iterable, r=None)`439440Возвращает последовательные *r*-элементные [перестановки элементов](https://python-all.ru/3/library/itertools.html) из *iterable*.441442Если *r* не указан или равен `None`, то *r* по умолчанию равен длине *iterable* и генерируются все возможные перестановки полной длины.443444Результат является подпоследовательностью [`product()`](https://python-all.ru/3/library/itertools.html#itertools.product), из которой отфильтрованы записи с повторяющимися элементами. Длина результата определяется [`math.perm()`](https://python-all.ru/3/library/math.html#math.perm), который вычисляет `n! / (n - r)!`, когда `0 ≤ r ≤ n`, или ноль, когда `r > n`.445446Кортежи перестановок выдаются в лексикографическом порядке в соответствии с порядком входного *iterable*. Если входной *iterable* отсортирован, выходные кортежи будут созданы в отсортированном порядке.447448Элементы считаются уникальными на основе их позиции, а не значения. Если входные элементы уникальны, то в перестановке не будет повторяющихся значений.449450Примерно эквивалентно:451452```python453def permutations(iterable, r=None):454 # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC455 # permutations(range(3)) → 012 021 102 120 201 210456457 pool = tuple(iterable)458 n = len(pool)459 r = n if r is None else r460 if r > n:461 return462463 indices = list(range(n))464 cycles = list(range(n, n-r, -1))465 yield tuple(pool[i] for i in indices[:r])466467 while n:468 for i in reversed(range(r)):469 cycles[i] -= 1470 if cycles[i] == 0:471 indices[i:] = indices[i+1:] + indices[i:i+1]472 cycles[i] = n - i473 else:474 j = cycles[i]475 indices[i], indices[-j] = indices[-j], indices[i]476 yield tuple(pool[i] for i in indices[:r])477 break478 else:479 return480```481482#### `itertools.product(*iterables, repeat=1)`483484[Декартово произведение](https://python-all.ru/3/library/itertools.html) входных итерируемых объектов.485486Примерно эквивалентно вложенным циклам for в генераторном выражении. Например, `product(A, B)` возвращает то же, что и `((x,y) for x in A for y in B)`.487488Вложенные циклы работают как одометр: самый правый элемент увеличивается на каждой итерации. Этот шаблон создает лексикографический порядок, так что если входные итерируемые объекты отсортированы, кортежи произведения выдаются в отсортированном порядке.489490Чтобы вычислить произведение итерируемого объекта на самого себя, укажите количество повторений с помощью необязательного именованного аргумента *repeat*. Например, `product(A, repeat=4)` эквивалентно `product(A, A, A, A)`.491492Эта функция примерно эквивалентна следующему коду, за исключением того, что реальная реализация не накапливает промежуточные результаты в памяти:493494```python495def product(*iterables, repeat=1):496 # product('ABCD', 'xy') → Ax Ay Bx By Cx Cy Dx Dy497 # product(range(2), repeat=3) → 000 001 010 011 100 101 110 111498499 if repeat < 0:500 raise ValueError('repeat argument cannot be negative')501 pools = [tuple(pool) for pool in iterables] * repeat502503 result = [[]]504 for pool in pools:505 result = [x+[y] for x in result for y in pool]506507 for prod in result:508 yield tuple(prod)509```510511Перед запуском `product()` полностью потребляет входные итерируемые объекты, сохраняя пулы значений в памяти для генерации произведений. Соответственно, она полезна только для конечных входных данных.512513#### `itertools.repeat(object[, times])`514515Создает итератор, который снова и снова возвращает *object*. Работает бесконечно, если не указан аргумент *times*.516517Примерно эквивалентно:518519```python520def repeat(object, times=None):521 # repeat(10, 3) → 10 10 10522 if times is None:523 while True:524 yield object525 else:526 for i in range(times):527 yield object528```529530Обычное применение *repeat* – передача потока постоянных значений в *map* или *zip*:531532```pycon533>>> list(map(pow, range(10), repeat(2)))534[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]535```536537#### `itertools.starmap(function, iterable)`538539Создаёт итератор, который вычисляет *функцию*, используя аргументы, полученные из *итерируемого объекта*. Используется вместо [`map()`](https://python-all.ru/3/library/functions.html#map), когда параметры аргументов уже «предварительно упакованы» в кортежи.540541Различие между [`map()`](https://python-all.ru/3/library/functions.html#map) и `starmap()` аналогично различию между `function(a,b)` и `function(*c)`. Примерно эквивалентно:542543```python544def starmap(function, iterable):545 # starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000546 for args in iterable:547 yield function(*args)548```549550#### `itertools.takewhile(predicate, iterable)`551552Создаёт итератор, который возвращает элементы из *итерируемого объекта* до тех пор, пока *предикат* истинен. Примерно эквивалентно:553554```python555def takewhile(predicate, iterable):556 # takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4557 for x in iterable:558 if not predicate(x):559 break560 yield x561```562563Обратите внимание: элемент, который первым не удовлетворяет условию предиката, потребляется из входного итератора, и доступа к нему нет. Это может быть проблемой, если приложение хочет продолжить потребление входного итератора после того, как *takewhile* отработал до полного исчерпания. Чтобы обойти эту проблему, рассмотрите возможность использования [more-itertools.before\_and\_after()](https://python-all.ru/3/library/itertools.html) вместо этого.564565#### `itertools.tee(iterable, n=2)`566567Возвращает *n* независимых итераторов из одного итерируемого объекта.568569Примерно эквивалентно:570571```python572def tee(iterable, n=2):573 if n < 0:574 raise ValueError575 if n == 0:576 return ()577 iterator = _tee(iterable)578 result = [iterator]579 for _ in range(n - 1):580 result.append(_tee(iterator))581 return tuple(result)582583class _tee:584585 def __init__(self, iterable):586 it = iter(iterable)587 if isinstance(it, _tee):588 self.iterator = it.iterator589 self.link = it.link590 else:591 self.iterator = it592 self.link = [None, None]593594 def __iter__(self):595 return self596597 def __next__(self):598 link = self.link599 if link[1] is None:600 link[0] = next(self.iterator)601 link[1] = [None, None]602 value, self.link = link603 return value604```605606Если входной *итерируемый объект* уже является объектом-итератором tee, все элементы возвращаемого кортежа создаются так, как если бы они были произведены upstream-вызовом `tee()`. Этот «шаг уплощения» позволяет вложенным вызовам `tee()` использовать одну и ту же базовую цепочку данных и выполнять один шаг обновления вместо цепочки вызовов.607608Свойство уплощения делает итераторы tee эффективно просматриваемыми:609610```python611def lookahead(tee_iterator):612 "Return the next value without moving the input forward"613 [forked_iterator] = tee(tee_iterator, 1)614 return next(forked_iterator)615```616617```pycon618>>> iterator = iter('abcdef')619>>> [iterator] = tee(iterator, 1) # Сделать входные данные просматриваемыми (peekable)620>>> next(iterator) # Продвинуть итератор вперед621'a'622>>> lookahead(iterator) # Проверить следующее значение623'b'624>>> next(iterator) # Продолжить движение вперед625'b'626```627628Итераторы `tee` не являются потокобезопасными. Исключение [`RuntimeError`](https://python-all.ru/3/library/exceptions.html#RuntimeError) может быть возбуждено при одновременном использовании итераторов, возвращённых одним вызовом `tee()`, даже если исходный *итерируемый объект* потокобезопасен.629630Этот инструмент итерации может потребовать значительного вспомогательного хранилища (в зависимости от объёма временных данных, которые необходимо сохранить). В общем случае, если один итератор использует большую часть или все данные до того, как запустится другой итератор, быстрее использовать [`list()`](https://python-all.ru/3/library/stdtypes.html#list) вместо `tee()`.631632#### `itertools.zip_longest(*iterables, fillvalue=None)`633634Создаёт итератор, который объединяет элементы из каждого *итерируемого объекта*.635636Если итерируемые объекты имеют разную длину, недостающие значения заполняются с помощью *fillvalue*. Если не указан, *fillvalue* по умолчанию равен `None`.637638Итерация продолжается, пока самый длинный итерируемый объект не будет исчерпан.639640Примерно эквивалентно:641642```python643def zip_longest(*iterables, fillvalue=None):644 # zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D-645646 iterators = list(map(iter, iterables))647 num_active = len(iterators)648 if not num_active:649 return650651 while True:652 values = []653 for i, iterator in enumerate(iterators):654 try:655 value = next(iterator)656 except StopIteration:657 num_active -= 1658 if not num_active:659 return660 iterators[i] = repeat(fillvalue)661 value = fillvalue662 values.append(value)663 yield tuple(values)664```665666Если один из итерируемых объектов потенциально бесконечен, то функция `zip_longest()` должна быть обёрнута чем-то, что ограничивает количество вызовов (например, [`islice()`](https://python-all.ru/3/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/3/library/itertools.html#itertools.takewhile)).667668## Рецепты itertools669670В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.671672Основная цель рецептов itertools – образовательная. Рецепты демонстрируют различные способы мышления об отдельных инструментах – например, что `chain.from_iterable` связано с концепцией уплощения. Рецепты также дают идеи о том, как инструменты можно комбинировать – например, как `starmap()` и `repeat()` могут работать вместе. Рецепты также показывают шаблоны использования itertools с модулями [`operator`](https://python-all.ru/3/library/operator.html#module-operator) и [`collections`](https://python-all.ru/3/library/collections.html#module-collections), а также со встроенными itertools, такими как `map()`, `filter()`, `reversed()` и `enumerate()`.673674Второстепенная цель рецептов – служить инкубатором. `accumulate()`, `compress()` и `pairwise()` изначально были рецептами. В настоящее время рецепты `sliding_window()`, `derangements()` и `sieve()` тестируются, чтобы проверить, оправдают ли они себя.675676Практически все эти и многие другие рецепты можно установить из проекта [more-itertools](https://python-all.ru/3/library/itertools.html), доступного на Python Package Index:677678```python679python -m pip install more-itertools680```681682Многие рецепты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода сохраняется небольшим за счёт связывания инструментов в [функциональном стиле](https://python-all.ru/3/library/itertools.html). Высокая скорость сохраняется благодаря предпочтению «векторизованных» строительных блоков перед использованием циклов for и [генераторов](https://python-all.ru/3/glossary.html#term-generator), которые влекут накладные расходы интерпретатора.683684```python685from itertools import (accumulate, batched, chain, combinations, compress,686 count, cycle, filterfalse, groupby, islice, permutations, product,687 repeat, starmap, tee, zip_longest)688from collections import Counter, deque689from contextlib import suppress690from functools import reduce691from heapq import heappush, heappushpop, heappush_max, heappushpop_max692from math import comb, isqrt, prod, sumprod693from operator import getitem, is_not, itemgetter, mul, neg, truediv694695# ==== Базовые однострочники ====696697def take(n, iterable):698 "Return first n items of the iterable as a list."699 return list(islice(iterable, n))700701def prepend(value, iterable):702 "Prepend a single value in front of an iterable."703 # prepend(1, [2, 3, 4]) → 1 2 3 4704 return chain([value], iterable)705706def repeatfunc(function, times=None, *args):707 "Repeat calls to a function with specified arguments."708 if times is None:709 return starmap(function, repeat(args))710 return starmap(function, repeat(args, times))711712def flatten(list_of_lists):713 "Flatten one level of nesting."714 return chain.from_iterable(list_of_lists)715716def ncycles(iterable, n):717 "Returns the sequence elements n times."718 return chain.from_iterable(repeat(tuple(iterable), n))719720def loops(n):721 "Loop n times. Like range(n) but without creating integers."722 # for _ in loops(100): ...723 return repeat(None, n)724725def tail(n, iterable):726 "Return an iterator over the last n items."727 # tail(3, 'ABCDEFG') → E F G728 return iter(deque(iterable, maxlen=n))729730def consume(iterator, n=None):731 "Advance the iterator n-steps ahead. If n is None, consume entirely."732 # Используйте функции, потребляющие итераторы на скорости C.733 if n is None:734 deque(iterator, maxlen=0)735 else:736 next(islice(iterator, n, n), None)737738def nth(iterable, n, default=None):739 "Returns the nth item or a default value."740 return next(islice(iterable, n, None), default)741742def quantify(iterable, predicate=bool):743 "Given a predicate that returns True or False, count the True results."744 return sum(map(predicate, iterable))745746def first_true(iterable, default=False, predicate=None):747 "Returns the first true value or the *default* if there is no true value."748 # first_true([a, b, c], x) → a or b or c or x749 # first_true([a, b], x, f) → a if f(a) else b if f(b) else x750 return next(filter(predicate, iterable), default)751752def all_equal(iterable, key=None):753 "Returns True if all the elements are equal to each other."754 # all_equal('4٤௪౪໔', key=int) → True755 return len(take(2, groupby(iterable, key))) <= 1756757# ==== Конвейеры данных ====758759def unique_justseen(iterable, key=None):760 "Yield unique elements, preserving order. Remember only the element just seen."761 # unique_justseen('AAAABBBCCDAABBB') → A B C D A B762 # unique_justseen('ABBcCAD', str.casefold) → A B c A D763 if key is None:764 return map(itemgetter(0), groupby(iterable))765 return map(next, map(itemgetter(1), groupby(iterable, key)))766767def unique_everseen(iterable, key=None):768 "Yield unique elements, preserving order. Remember all elements ever seen."769 # unique_everseen('AAAABBBCCDAABBB') → A B C D770 # unique_everseen('ABBcCAD', str.casefold) → A B c D771 seen = set()772 if key is None:773 for element in filterfalse(seen.__contains__, iterable):774 seen.add(element)775 yield element776 else:777 for element in iterable:778 k = key(element)779 if k not in seen:780 seen.add(k)781 yield element782783def unique(iterable, key=None, reverse=False):784 "Yield unique elements in sorted order. Supports unhashable inputs."785 # unique([[1, 2], [3, 4], [1, 2]]) → [1, 2] [3, 4]786 sequenced = sorted(iterable, key=key, reverse=reverse)787 return unique_justseen(sequenced, key=key)788789def sliding_window(iterable, n):790 "Collect data into overlapping fixed-length chunks or blocks."791 # sliding_window('ABCDEFG', 3) → ABC BCD CDE DEF EFG792 iterator = iter(iterable)793 window = deque(islice(iterator, n - 1), maxlen=n)794 for x in iterator:795 window.append(x)796 yield tuple(window)797798def grouper(iterable, n, *, incomplete='fill', fillvalue=None):799 "Collect data into non-overlapping fixed-length chunks or blocks."800 # grouper('ABCDEFG', 3, fillvalue='x') → ABC DEF Gxx801 # grouper('ABCDEFG', 3, incomplete='strict') → ABC DEF ValueError802 # grouper('ABCDEFG', 3, incomplete='ignore') → ABC DEF803 iterators = [iter(iterable)] * n804 match incomplete:805 case 'fill':806 return zip_longest(*iterators, fillvalue=fillvalue)807 case 'strict':808 return zip(*iterators, strict=True)809 case 'ignore':810 return zip(*iterators)811 case _:812 raise ValueError('Expected fill, strict, or ignore')813814def roundrobin(*iterables):815 "Visit input iterables in a cycle until each is exhausted."816 # roundrobin('ABC', 'D', 'EF') → A D E B F C817 # Алгоритм Джорджа Саккиса818 iterators = map(iter, iterables)819 for num_active in range(len(iterables), 0, -1):820 iterators = cycle(islice(iterators, num_active))821 yield from map(next, iterators)822823def subslices(seq):824 "Return all contiguous non-empty subslices of a sequence."825 # subslices('ABCD') → A AB ABC ABCD B BC BCD C CD D826 slices = starmap(slice, combinations(range(len(seq) + 1), 2))827 return map(getitem, repeat(seq), slices)828829def derangements(iterable, r=None):830 "Produce r length permutations without fixed points."831 # derangements('ABCD') → BADC BCDA BDAC CADB CDAB CDBA DABC DCAB DCBA832 # Алгоритм Стефана Похманна833 seq = tuple(iterable)834 pos = tuple(range(len(seq)))835 have_moved = map(map, repeat(is_not), repeat(pos), permutations(pos, r=r))836 valid_derangements = map(all, have_moved)837 return compress(permutations(seq, r=r), valid_derangements)838839def iter_index(iterable, value, start=0, stop=None):840 "Return indices where a value occurs in a sequence or iterable."841 # iter_index('AABCADEAF', 'A') → 0 1 4 7842 seq_index = getattr(iterable, 'index', None)843 if seq_index is None:844 iterator = islice(iterable, start, stop)845 for i, element in enumerate(iterator, start):846 if element is value or element == value:847 yield i848 else:849 stop = len(iterable) if stop is None else stop850 i = start851 with suppress(ValueError):852 while True:853 yield (i := seq_index(value, i, stop))854 i += 1855856def iter_except(function, exception, first=None):857 "Convert a call-until-exception interface to an iterator interface."858 # iter_except(d.popitem, KeyError) → неблокирующий итератор словаря859 with suppress(exception):860 if first is not None:861 yield first()862 while True:863 yield function()864865# ==== Математические операции ====866867def multinomial(*counts):868 "Number of distinct arrangements of a multiset."869 # Counter('abracadabra').values() → 5 2 2 1 1870 # multinomial(5, 2, 2, 1, 1) → 83160871 return prod(map(comb, accumulate(counts), counts))872873def powerset(iterable):874 "Subsequences of the iterable from shortest to longest."875 # powerset([1,2,3]) → () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)876 s = list(iterable)877 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))878879def sum_of_squares(iterable):880 "Add up the squares of the input values."881 # sum_of_squares([10, 20, 30]) → 1400882 return sumprod(*tee(iterable))883884# ==== Операции с матрицами ====885886def reshape(matrix, columns):887 "Reshape a 2-D matrix to have a given number of columns."888 # reshape([(0, 1), (2, 3), (4, 5)], 3) → (0, 1, 2) (3, 4, 5)889 return batched(chain.from_iterable(matrix), columns, strict=True)890891def transpose(matrix):892 "Swap the rows and columns of a 2-D matrix."893 # transpose([(1, 2, 3), (11, 22, 33)]) → (1, 11) (2, 22) (3, 33)894 return zip(*matrix, strict=True)895896def matmul(m1, m2):897 "Multiply two matrices."898 # matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]) → (49, 80) (41, 60)899 n = len(m2[0])900 return batched(starmap(sumprod, product(m1, transpose(m2))), n)901902# ==== Арифметика многочленов ====903904def convolve(signal, kernel):905 """Дискретная линейная свёртка двух итерируемых объектов.906 Эквивалентно умножению многочленов.907908 Свёртки математически коммутативны; однако входные данные909 вычисляются по-разному. Сигнал потребляется лениво и может быть910 бесконечным. Ядро полностью потребляется до начала вычислений.911912 Статья: https://betterexplained.com/articles/intuitive-convolution/913 Видео: https://www.youtube.com/watch?v=KuXjwB4LzSA914 """915 # convolve([1, -1, -20], [1, -3]) → 1 -4 -17 60916 # convolve(data, [0.25, 0.25, 0.25, 0.25]) → Скользящее среднее (размытие)917 # convolve(data, [1/2, 0, -1/2]) → Оценка первой производной918 # convolve(data, [1, -2, 1]) → Оценка второй производной919 kernel = tuple(kernel)[::-1]920 n = len(kernel)921 padded_signal = chain(repeat(0, n-1), signal, repeat(0, n-1))922 windowed_signal = sliding_window(padded_signal, n)923 return map(sumprod, repeat(kernel), windowed_signal)924925def polynomial_from_roots(roots):926 """Вычисляет коэффициенты многочлена по его корням.927928 (x - 5) (x + 4) (x - 3) раскрывается в: x³ -4x² -17x + 60929 """930 # polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]931 factors = zip(repeat(1), map(neg, roots))932 return list(reduce(convolve, factors, [1]))933934def polynomial_eval(coefficients, x):935 """Вычисляет значение многочлена в заданной точке.936937 Вычисляет с лучшей численной устойчивостью, чем метод Горнера.938 """939 # Вычислить x³ -4x² -17x + 60 при x = 5940 # polynomial_eval([1, -4, -17, 60], x=5) → 0941 n = len(coefficients)942 if not n:943 return type(x)(0)944 powers = map(pow, repeat(x), reversed(range(n)))945 return sumprod(coefficients, powers)946947def polynomial_derivative(coefficients):948 """Вычисляет первую производную многочлена.949950 f(x) = x³ -4x² -17x + 60951 f'(x) = 3x² -8x -17952 """953 # polynomial_derivative([1, -4, -17, 60]) → [3, -8, -17]954 n = len(coefficients)955 powers = reversed(range(1, n))956 return list(map(mul, coefficients, powers))957958# ==== Теория чисел ====959960def sieve(n):961 "Primes less than n."962 # sieve(30) → 2 3 5 7 11 13 17 19 23 29963 if n > 2:964 yield 2965 data = bytearray((0, 1)) * (n // 2)966 for p in iter_index(data, 1, start=3, stop=isqrt(n) + 1):967 data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))968 yield from iter_index(data, 1, start=3)969970def factor(n):971 "Prime factors of n."972 # factor(99) → 3 3 11973 # factor(1_000_000_000_000_007) → 47 59 360620266859974 # factor(1_000_000_000_000_403) → 1000000000000403975 for prime in sieve(isqrt(n) + 1):976 while not n % prime:977 yield prime978 n //= prime979 if n == 1:980 return981 if n > 1:982 yield n983984def is_prime(n):985 "Return True if n is prime."986 # is_prime(1_000_000_000_000_403) → True987 return n > 1 and next(factor(n)) == n988989def totient(n):990 "Count of natural numbers up to n that are coprime to n."991 # https://mathworld.wolfram.com/TotientFunction.html992 # totient(12) → 4 потому что len([1, 5, 7, 11]) == 4993 for prime in set(factor(n)):994 n -= n // prime995 return n996997# ==== Скользящие статистики ====998999def running_mean(iterable):1000 "Average of values seen so far."1001 # running_mean([37, 33, 38, 28]) → 37 35 36 341002 return map(truediv, accumulate(iterable), count(1))10031004def running_min(iterable):1005 "Smallest of values seen so far."1006 # running_min([37, 33, 38, 28]) → 37 33 33 281007 return accumulate(iterable, func=min)10081009def running_max(iterable):1010 "Largest of values seen so far."1011 # running_max([37, 33, 38, 28]) → 37 37 38 381012 return accumulate(iterable, func=max)10131014def running_median(iterable):1015 "Median of values seen so far."1016 # running_median([37, 33, 38, 28]) → 37 35 37 351017 read = iter(iterable).__next__1018 lo = [] # максимальная куча1019 hi = [] # мин-куча того же размера, что и lo, или на единицу меньше1020 with suppress(StopIteration):1021 while True:1022 heappush_max(lo, heappushpop(hi, read()))1023 yield lo[0]1024 heappush(hi, heappushpop_max(lo, read()))1025 yield (lo[0] + hi[0]) / 210261027def running_statistics(iterable):1028 "Aggregate statistics for values seen so far."1029 # Создать кортежи: (size, minimum, median, maximum, mean)1030 t0, t1, t2, t3 = tee(iterable, 4)1031 return zip(1032 count(1),1033 running_min(t0),1034 running_median(t1),1035 running_max(t2),1036 running_mean(t3),1037 )1038```1039