itertools.md
1> **Источник:** https://python-all.ru/3.0/library/itertools.html2>3> «Документация Python на русском» – неофициальный перевод официальной документации Python: версии от 2.6 до 3.16, полнотекстовый поиск, английский оригинал рядом с переводом. Эта Markdown-версия страницы предназначена для работы с LLM: вставьте её в ChatGPT, Claude или Cursor.45---67# `itertools` – Функции, создающие итераторы для эффективной работы с циклами89Этот модуль реализует ряд строительных блоков [*итератора*](https://python-all.ru/3.0/glossary.html#term-iterator), вдохновленных конструкциями из языков программирования Haskell и SML. Каждый из них был переработан в форму, подходящую для Python.1011Модуль стандартизирует основной набор быстрых и эффективных по памяти инструментов, которые полезны сами по себе или в комбинации. Стандартизация помогает избежать проблем с читаемостью и надежностью, которые возникают, когда множество людей создают свои собственные слегка отличающиеся реализации, каждая со своими причудами и соглашениями об именах.1213Инструменты спроектированы так, чтобы легко сочетаться друг с другом. Это позволяет просто и эффективно создавать более специализированные инструменты на чистом Python.1415Например, в SML есть инструмент табуляции: `tabulate(f)`, который создает последовательность `f(0), f(1), ...`. Но того же эффекта в Python можно достичь, комбинируя [`map()`](https://python-all.ru/3.0/library/functions.html#map) и [`count()`](https://python-all.ru/3.0/library/itertools.html#itertools.count) для получения `map(f, count())`.1617Аналогично, функциональные инструменты спроектированы для хорошей работы с быстрыми функциями, предоставляемыми модулем [`operator`](https://python-all.ru/3.0/library/operator.html#module-operator).1819Будь то реализованные на чистом Python или в скомпилированном коде, инструменты, использующие итераторы, более эффективны по памяти (и часто быстрее), чем их аналоги на основе списков. Применяя принципы производства «точно вовремя», они создают данные тогда и там, где они нужны, вместо того чтобы расходовать память на компьютерный эквивалент «запасов».2021> **См. также**22>23> The Standard ML Basis Library, [The Standard ML Basis Library](https://python-all.ru/3.0/library/itertools.html).24>25> Haskell, A Purely Functional Language, [Definition of Haskell and the Standard Libraries](https://python-all.ru/3.0/library/itertools.html).2627## Функции итераторных инструментов2829Следующие функции модуля создают и возвращают итераторы. Некоторые из них порождают потоки бесконечной длины, поэтому обращаться к ним следует только с помощью функций или циклов, которые обрывают поток.3031#### `[itertools.chain]itertools.chain(*iterables)`3233Создаёт итератор, возвращающий элементы из первого итерируемого объекта до его исчерпания, затем переходит к следующему и так далее, пока все итерируемые объекты не будут исчерпаны. Используется для обработки последовательных последовательностей как одной последовательности. Эквивалентно:3435```python36def chain(*iterables):37 # chain('ABC', 'DEF') --> A B C D E F38 for it in iterables:39 for element in it:40 yield element41```4243#### `[itertools.itertools.chain.from_iterable]itertools.chain.from_iterable(iterable)`4445Альтернативный конструктор для [`chain()`](https://python-all.ru/3.0/library/itertools.html#itertools.chain). Получает цепочку входных данных из одного итерируемого аргумента, который вычисляется лениво. Эквивалентно:4647```python48@classmethod49def from_iterable(iterables):50 # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F51 for it in iterables:52 for element in it:53 yield element54```5556#### `[itertools.combinations]itertools.combinations(iterable, r)`5758Возвращает подпоследовательности элементов длины *r* из входного *iterable*.5960Комбинации выдаются в лексикографическом порядке. Таким образом, если входной *итерируемый объект* отсортирован, кортежи комбинаций будут созданы в отсортированном порядке.6162Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой комбинации не будет повторяющихся значений.6364Эквивалентно следующему:6566```python67def combinations(iterable, r):68 # combinations('ABCD', 2) --> AB AC AD BC BD CD69 # combinations(range(4), 3) --> 012 013 023 12370 pool = tuple(iterable)71 n = len(pool)72 if r > n:73 return74 indices = list(range(r))75 yield tuple(pool[i] for i in indices)76 while 1:77 for i in reversed(range(r)):78 if indices[i] != i + n - r:79 break80 else:81 return82 indices[i] += 183 for j in range(i+1, r):84 indices[j] = indices[j-1] + 185 yield tuple(pool[i] for i in indices)86```8788Код для [`combinations()`](https://python-all.ru/3.0/library/itertools.html#itertools.combinations) также можно выразить как подпоследовательность [`permutations()`](https://python-all.ru/3.0/library/itertools.html#itertools.permutations) после фильтрации записей, в которых элементы не отсортированы (согласно их позиции во входном пуле):8990```python91def combinations(iterable, r):92 pool = tuple(iterable)93 n = len(pool)94 for indices in permutations(range(n), r):95 if sorted(indices) == list(indices):96 yield tuple(pool[i] for i in indices)97```9899Количество возвращаемых элементов равно `n! / r! / (n-r)!`, когда `0 <= r <= n`, или нулю, когда `r > n`.100101#### `[itertools.count]itertools.count([n])`102103Создает итератор, возвращающий последовательные целые числа, начиная с *n*. Если не указано, *n* по умолчанию равно нулю. Часто используется в качестве аргумента [`map()`](https://python-all.ru/3.0/library/functions.html#map) для генерации последовательных точек данных. Также используется с [`zip()`](https://python-all.ru/3.0/library/functions.html#zip) для добавления порядковых номеров. Эквивалентно:104105```python106def count(n=0):107 # count(10) --> 10 11 12 13 14 ...108 while True:109 yield n110 n += 1111```112113#### `[itertools.cycle]itertools.cycle(iterable)`114115Создаёт итератор, возвращающий элементы из итерируемого объекта и сохраняющий копию каждого. Когда итерируемый объект исчерпан, возвращает элементы из сохранённой копии. Повторяется бесконечно. Эквивалентно:116117```python118def cycle(iterable):119 # cycle('ABCD') --> A B C D A B C D A B C D ...120 saved = []121 for element in iterable:122 yield element123 saved.append(element)124 while saved:125 for element in saved:126 yield element127```128129Примечание: этот элемент набора инструментов может потребовать значительного дополнительного хранилища (в зависимости от длины итерабельного объекта).130131#### `[itertools.dropwhile]itertools.dropwhile(predicate, iterable)`132133Создаёт итератор, который отбрасывает элементы из итерируемого объекта, пока предикат истинен; после этого возвращает каждый элемент. Обратите внимание: итератор не выдаёт *никакого* вывода, пока предикат не станет ложным, поэтому время запуска может быть значительным. Эквивалентно:134135```python136def dropwhile(predicate, iterable):137 # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1138 iterable = iter(iterable)139 for x in iterable:140 if not predicate(x):141 yield x142 break143 for x in iterable:144 yield x145```146147#### `[itertools.filterfalse]itertools.filterfalse(predicate, iterable)`148149Создаёт итератор, который фильтрует элементы из итерируемого объекта, возвращая только те, для которых предикат равен `False`. Если *predicate* равен `None`, возвращает элементы, которые являются ложными. Эквивалентно.150151```python152def filterfalse(predicate, iterable):153 # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8154 if predicate is None:155 predicate = bool156 for x in iterable:157 if not predicate(x):158 yield x159```160161#### `[itertools.groupby]itertools.groupby(iterable[, key])`162163Создаёт итератор, который возвращает последовательные ключи и группы из *iterable*. *key* – это функция, вычисляющая ключевое значение для каждого элемента. Если он не указан или равен `None`, то *key* по умолчанию принимает тождественную функцию и возвращает элемент без изменений. Обычно iterable должен быть отсортирован по той же ключевой функции.164165Работа [`groupby()`](https://python-all.ru/3.0/library/itertools.html#itertools.groupby) похожа на фильтр `uniq` в Unix. Она создаёт разрыв или новую группу каждый раз, когда значение ключевой функции меняется (именно поэтому данные обычно необходимо отсортировать с помощью той же ключевой функции). Такое поведение отличается от SQL’s GROUP BY, которое объединяет общие элементы независимо от их порядка во входных данных.166167Возвращаемая группа сама является итератором, который использует тот же исходный итератор, что и [`groupby()`](https://python-all.ru/3.0/library/itertools.html#itertools.groupby). Поскольку источник общий, когда [`groupby()`](https://python-all.ru/3.0/library/itertools.html#itertools.groupby) объект продвигается, предыдущая группа перестаёт быть видимой. Поэтому, если эти данные потребуются позже, их следует сохранить в виде списка:168169```python170groups = []171uniquekeys = []172data = sorted(data, key=keyfunc)173for k, g in groupby(data, keyfunc):174 groups.append(list(g)) # Сохранить групповой итератор как список175 uniquekeys.append(k)176```177178[`groupby()`](https://python-all.ru/3.0/library/itertools.html#itertools.groupby) эквивалентен следующему:179180```python181class groupby(object):182 # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B183 # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D184 def __init__(self, iterable, key=None):185 if key is None:186 key = lambda x: x187 self.keyfunc = key188 self.it = iter(iterable)189 self.tgtkey = self.currkey = self.currvalue = object()190 def __iter__(self):191 return self192 def __next__(self):193 while self.currkey == self.tgtkey:194 self.currvalue = next(self.it) # Exit on StopIteration195 self.currkey = self.keyfunc(self.currvalue)196 self.tgtkey = self.currkey197 return (self.currkey, self._grouper(self.tgtkey))198 def _grouper(self, tgtkey):199 while self.currkey == tgtkey:200 yield self.currvalue201 self.currvalue = next(self.it) # Exit on StopIteration202 self.currkey = self.keyfunc(self.currvalue)203```204205#### `[itertools.islice]itertools.islice(iterable[, start], stop[, step])`206207Создаёт итератор, который возвращает выбранные элементы из iterable. Если *start* не равен нулю, то элементы из iterable пропускаются до тех пор, пока не будет достигнут start. После этого элементы возвращаются подряд, если только *step* не больше единицы, что приводит к пропуску элементов. Если *stop* равен `None`, то итерация продолжается, пока итератор не исчерпается; в противном случае она останавливается на указанной позиции. В отличие от обычного среза, [`islice()`](https://python-all.ru/3.0/library/itertools.html#itertools.islice) не поддерживает отрицательные значения для *start*, *stop* или *step*. Может использоваться для извлечения связанных полей из данных, у которых внутренняя структура была сплющена (например, в многострочном отчёте поле имени может располагаться на каждой третьей строке). Эквивалентен:208209```python210def islice(iterable, *args):211 # islice('ABCDEFG', 2) --> A B212 # islice('ABCDEFG', 2, 4) --> C D213 # islice('ABCDEFG', 2, None) --> C D E F G214 # islice('ABCDEFG', 0, None, 2) --> A C E G215 s = slice(*args)216 it = range(s.start or 0, s.stop or sys.maxsize, s.step or 1)217 nexti = next(it)218 for i, element in enumerate(iterable):219 if i == nexti:220 yield element221 nexti = next(it)222```223224Если *start* равен `None`, то итерация начинается с нуля. Если *step* равен `None`, то шаг по умолчанию равен единице.225226#### `[itertools.permutations]itertools.permutations(iterable[, r])`227228Возвращает последовательные перестановки длины *r* элементов из *iterable*.229230Если *r* не указан или равен `None`, то *r* по умолчанию принимает длину *iterable* и генерируются все возможные перестановки полной длины.231232Перестановки выдаются в лексикографическом порядке. Таким образом, если входной *итерируемый объект* отсортирован, кортежи перестановок будут созданы в отсортированном порядке.233234Элементы считаются уникальными на основе их позиции, а не значения. Поэтому если входные элементы уникальны, то в каждой перестановке не будет повторяющихся значений.235236Эквивалентно следующему:237238```python239def permutations(iterable, r=None):240 # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC241 # permutations(range(3)) --> 012 021 102 120 201 210242 pool = tuple(iterable)243 n = len(pool)244 r = n if r is None else r245 if r > n:246 return247 indices = list(range(n))248 cycles = range(n, n-r, -1)249 yield tuple(pool[i] for i in indices[:r])250 while n:251 for i in reversed(range(r)):252 cycles[i] -= 1253 if cycles[i] == 0:254 indices[i:] = indices[i+1:] + indices[i:i+1]255 cycles[i] = n - i256 else:257 j = cycles[i]258 indices[i], indices[-j] = indices[-j], indices[i]259 yield tuple(pool[i] for i in indices[:r])260 break261 else:262 return263```264265Код для [`permutations()`](https://python-all.ru/3.0/library/itertools.html#itertools.permutations) можно также выразить как подпоследовательность [`product()`](https://python-all.ru/3.0/library/itertools.html#itertools.product), отфильтрованную для исключения записей с повторяющимися элементами (тех, что находятся на одной и той же позиции во входном пуле):266267```python268def permutations(iterable, r=None):269 pool = tuple(iterable)270 n = len(pool)271 r = n if r is None else r272 for indices in product(range(n), repeat=r):273 if len(set(indices)) == r:274 yield tuple(pool[i] for i in indices)275```276277Количество возвращаемых элементов равно `n! / (n-r)!`, когда `0 <= r <= n` или нулю, когда `r > n`.278279#### `[itertools.product]itertools.product(*iterables[, repeat])`280281Декартово произведение входных итерируемых объектов.282283Эквивалентно вложенным циклам for в генераторном выражении. Например, `product(A, B)` возвращает то же, что и `((x,y) for x in A for y in B)`.284285Вложенные циклы работают как одометр: самый правый элемент увеличивается на каждой итерации. Этот шаблон создает лексикографический порядок, так что если входные итерируемые объекты отсортированы, кортежи произведения выдаются в отсортированном порядке.286287Чтобы вычислить произведение итератора самого на себя, укажите количество повторений с помощью необязательного именованного аргумента *repeat*. Например, `product(A, repeat=4)` означает то же, что и `product(A, A, A, A)`.288289Эта функция эквивалентна следующему коду, за исключением того, что реальная реализация не создаёт промежуточные результаты в памяти:290291```python292def product(*args, repeat=1):293 # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy294 # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111295 pools = map(tuple, args) * repeat296 result = [[]]297 for pool in pools:298 result = [x+[y] for x in result for y in pool]299 for prod in result:300 yield tuple(prod)301```302303#### `[itertools.repeat]itertools.repeat(object[, times])`304305Создаёт итератор, который снова и снова возвращает *object*. Работает бесконечно, если не указан аргумент *times*. Используется как аргумент для [`map()`](https://python-all.ru/3.0/library/functions.html#map) для неизменяемых параметров вызываемой функции. Также используется с [`zip()`](https://python-all.ru/3.0/library/functions.html#zip) для создания неизменяемой части записи кортежа. Эквивалентен:306307```python308def repeat(object, times=None):309 # repeat(10, 3) --> 10 10 10310 if times is None:311 while True:312 yield object313 else:314 for i in range(times):315 yield object316```317318#### `[itertools.starmap]itertools.starmap(function, iterable)`319320Создаёт итератор, который вычисляет функцию, используя аргументы, полученные из итератора. Используется вместо [`map()`](https://python-all.ru/3.0/library/functions.html#map), когда аргументы уже сгруппированы в кортежи из одного итератора (данные были «предварительно сжаты»). Разница между [`map()`](https://python-all.ru/3.0/library/functions.html#map) и [`starmap()`](https://python-all.ru/3.0/library/itertools.html#itertools.starmap) аналогична различию между `function(a,b)` и `function(*c)`. Эквивалентен:321322```python323def starmap(function, iterable):324 # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000325 for args in iterable:326 yield function(*args)327```328329#### `[itertools.takewhile]itertools.takewhile(predicate, iterable)`330331Создаёт итератор, который возвращает элементы из итератора, пока предикат истинен. Эквивалентен:332333```python334def takewhile(predicate, iterable):335 # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4336 for x in iterable:337 if predicate(x):338 yield x339 else:340 break341```342343#### `[itertools.tee]itertools.tee(iterable[, n=2])`344345Возвращает *n* независимых итераторов из одного итерируемого объекта. Случай, когда `n==2`, эквивалентен:346347```python348def tee(iterable):349 def gen(next, data={}):350 for i in count():351 if i in data:352 yield data.pop(i)353 else:354 data[i] = next()355 yield data[i]356 it = iter(iterable)357 return (gen(it.__next__), gen(it.__next__))358```359360Примечание: как только [`tee()`](https://python-all.ru/3.0/library/itertools.html#itertools.tee) произвел разделение, исходный *iterable* не должен использоваться где-либо еще; в противном случае *iterable* может продвинуться без уведомления объектов tee.361362Примечание: этот элемент инструментария может потребовать значительной дополнительной памяти (в зависимости от объема временных данных, которые необходимо хранить). В общем случае, если один итератор будет использовать большую часть или все данные до того, как другой итератор, быстрее использовать [`list()`](https://python-all.ru/3.0/library/functions.html#list) вместо [`tee()`](https://python-all.ru/3.0/library/itertools.html#itertools.tee).363364#### `[itertools.zip_longest]itertools.zip_longest(*iterables[, fillvalue])`365366Создаёт итератор, который объединяет элементы из каждого из итераторов. Если итераторы имеют разную длину, отсутствующие значения заполняются с помощью *fillvalue*. Итерация продолжается, пока самый длинный итератор не будет исчерпан. Эквивалентен:367368```python369def zip_longest(*args, fillvalue=None):370 # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-371 def sentinel(counter = ([fillvalue]*(len(args)-1)).pop):372 yield counter() # выдаёт fillvalue или вызывает IndexError373 fillers = repeat(fillvalue)374 iters = [chain(it, sentinel(), fillers) for it in args]375 try:376 for tup in zip(*iters):377 yield tup378 except IndexError:379 pass380```381382Если один из итераторов потенциально бесконечен, то функция [`zip_longest()`](https://python-all.ru/3.0/library/itertools.html#itertools.zip_longest) должна быть обёрнута чем-то, что ограничивает количество вызовов (например, [`islice()`](https://python-all.ru/3.0/library/itertools.html#itertools.islice) или [`takewhile()`](https://python-all.ru/3.0/library/itertools.html#itertools.takewhile)). Если не указано, *fillvalue* по умолчанию равен `None`.383384## Примеры385386Следующие примеры показывают типичные варианты использования каждого инструмента и демонстрируют способы их комбинирования.387388```python389>>> # Показать словарь, отсортированный и сгруппированный по значению390>>> from operator import itemgetter391>>> d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3)392>>> di = sorted(d.items(), key=itemgetter(1))393>>> for k, g in groupby(di, key=itemgetter(1)):394... print(k, map(itemgetter(0), g))395...3961 ['a', 'c', 'e']3972 ['b', 'd', 'f']3983 ['g']399400>>> # Найти последовательности подряд идущих чисел с помощью groupby. Ключ к решению401>>> # заключается в вычитании с помощью range, благодаря чему все подряд идущие числа оказываются в одной группе.402>>> # same group.403>>> data = [ 1, 4,5,6, 10, 15,16,17,18, 22, 25,26,27,28]404>>> for k, g in groupby(enumerate(data), lambda t:t[0]-t[1]):405... print(map(operator.itemgetter(1), g))406...407[1]408[4, 5, 6]409[10]410[15, 16, 17, 18]411[22]412[25, 26, 27, 28]413```414415## Рецепты416417В этом разделе представлены рецепты для создания расширенного набора инструментов с использованием существующих itertools в качестве строительных блоков.418419Расширенные инструменты обеспечивают такую же высокую производительность, как и базовый набор инструментов. Превосходная производительность по памяти достигается за счёт обработки элементов по одному, а не загрузки всего итерируемого объекта в память сразу. Объём кода остаётся небольшим благодаря связыванию инструментов в функциональном стиле, что помогает избавиться от временных переменных. Высокая скорость сохраняется за счёт предпочтения «векторизованных» строительных блоков вместо использования циклов for и [*генераторов*](https://python-all.ru/3.0/glossary.html#term-generator), которые создают накладные расходы интерпретатора.420421```python422def take(n, iterable):423 "Return first n items of the iterable as a list"424 return list(islice(iterable, n))425426def enumerate(iterable, start=0):427 return zip(count(start), iterable)428429def tabulate(function, start=0):430 "Return function(0), function(1), ..."431 return map(function, count(start))432433def nth(iterable, n):434 "Returns the nth item or None"435 return next(islice(iterable, n, None), None)436437def quantify(iterable, pred=bool):438 "Count how many times the predicate is true"439 return sum(map(pred, iterable))440441def padnone(iterable):442 """Returns the sequence elements and then returns None indefinitely.443444 Useful for emulating the behavior of the built-in map() function.445 """446 return chain(iterable, repeat(None))447448def ncycles(iterable, n):449 "Returns the sequence elements n times"450 return chain.from_iterable(repeat(iterable, n))451452def dotproduct(vec1, vec2):453 return sum(map(operator.mul, vec1, vec2))454455def flatten(listOfLists):456 return list(chain.from_iterable(listOfLists))457458def repeatfunc(func, times=None, *args):459 """Repeat calls to func with specified arguments.460461 Example: repeatfunc(random.random)462 """463 if times is None:464 return starmap(func, repeat(args))465 return starmap(func, repeat(args, times))466467def pairwise(iterable):468 "s -> (s0,s1), (s1,s2), (s2, s3), ..."469 a, b = tee(iterable)470 for elem in b:471 break472 return zip(a, b)473474def grouper(n, iterable, fillvalue=None):475 "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"476 args = [iter(iterable)] * n477 return zip_longest(*args, fillvalue=fillvalue)478479def roundrobin(*iterables):480 "roundrobin('ABC', 'D', 'EF') --> A D E B F C"481 # Recipe credited to George Sakkis482 pending = len(iterables)483 nexts = cycle(iter(it).__next__ for it in iterables)484 while pending:485 try:486 for next in nexts:487 yield next()488 except StopIteration:489 pending -= 1490 nexts = cycle(islice(nexts, pending))491492def powerset(iterable):493 "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"494 s = list(iterable)495 return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))496497def compress(data, selectors):498 "compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F"499 return (d for d, s in zip(data, selectors) if s)500501def combinations_with_replacement(iterable, r):502 "combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC"503 # number items returned: (n+r-1)! / r! / (n-1)!504 pool = tuple(iterable)505 n = len(pool)506 indices = [0] * r507 yield tuple(pool[i] for i in indices)508 while True:509 for i in reversed(range(r)):510 if indices[i] != n - 1:511 break512 else:513 return514 indices[i:] = [indices[i] + 1] * (r - i)515 yield tuple(pool[i] for i in indices)516517 def unique_everseen(iterable, key=None):518 "List unique elements, preserving order. Remember all elements ever seen."519 # unique_everseen('AAAABBBCCDAABBB') --> A B C D520 # unique_everseen('ABBCcAD', str.lower) --> A B C D521 seen = set()522 seen_add = seen.add523 if key is None:524 for element in iterable:525 if element not in seen:526 seen_add(element)527 yield element528 else:529 for element in iterable:530 k = key(element)531 if k not in seen:532 seen_add(k)533 yield element534535 def unique_justseen(iterable, key=None):536 "List unique elements, preserving order. Remember only the element just seen."537 # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B538 # unique_justseen('ABBCcAD', str.lower) --> A B C A D539 return map(next, map(itemgetter(1), groupby(iterable, key)))540```541