itertools — Функции создания итераторов для эффективных циклов

---

Модуль реализует ряд блочных итераторов, вдохновленных конструкциями из APL, Haskell и SML. Каждая из них была адаптирована в форму подходящую для Python.

Модуль стандартизирует базовый набор быстрых, эффективных с точки зрения памяти инструментов, которые полезны сами по себе или в сочетании. Вместе они образуют «итераторную алгебру», дающую возможность лаконично и эффективно конструировать специализированные инструменты на чистом Python.

Сущность SML предоставляет инструмент табуляции: tabulate(f), который создает последовательность f(0), f(1), .... Такой же эффект может быть достигнут в Python путем объединения map() и count() с образованием map(f, count()).

Эти инструменты и их встроенные аналоги также хорошо работают с высокоскоростными функциями модуля operator. Например, оператор умножения может быть отображен по двум векторам для формирования эффективного скалярного произведения: sum(map(operator.mul, vector1, vector2)).

Бесконечные итераторы:

Итератор	Аргументы	Результаты	Пример
count()	start, [step]	start, start+step, start+2*step, …	count(10) --> 10 11 12 13 14 ...
cycle()	p	p0, p1, … plast, p0, p1, …	cycle('ABCD') --> A B C D A B C D ...
repeat()	elem [,n]	elem, elem, elem, … endlessly or up to n times	repeat(10, 3) --> 10 10 10

Итераторы, оканчивающиеся на самой короткой входной последовательности:

Итератор	Аргументы	Результаты	Пример
accumulate()	p [,func]	p0, p0+p1, p0+p1+p2, …	accumulate([1,2,3,4,5]) --> 1 3 6 10 15
chain()	p, q, …	p0, p1, … plast, q0, q1, …	chain('ABC', 'DEF') --> A B C D E F
chain.from_iterable()	iterable	p0, p1, … plast, q0, q1, …	chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
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
dropwhile()	pred, seq	seq[n], seq[n+1], начинается, когда pred провалился	dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
filterfalse()	pred, seq	элементы seq, где pred(elem) равно false	filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
groupby()	iterable[, key]	субтераторы, сгруппированные по значению key(v)
islice()	seq, [start,] stop [, step]	элементы из seq[start:stop:step]	islice('ABCDEFG', 2, None) --> C D E F G
starmap()	func, seq	func(*seq[0]), func(*seq[1]), …	starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
takewhile()	pred, seq	seq[0], seq[1], пока pred не провалится	takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
tee()	it, n	it1, it2, … itn разбивает один итератор на n
zip_longest()	p, q, …	(p[0], q[0]), (p[1], q[1]), …	zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-

Комбинаторные итераторы:

Итератор	Аргументы	Результаты
product()	p, q, … [repeat=1]	декартово произведение, эквивалентное вложенному циклу for
permutations()	p[, r]	кортежи r-длины, все возможные упорядочения, без повторяющихся элементов
combinations()	p, r	кортежи r-длины, в отсортированном порядке, без повторяющихся элементов
combinations_with_replacement()	p, r	кортежи r-длины, в отсортированном порядке, с повторяющимися элементами

Примеры	Результаты
product('ABCD', repeat=2)	AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)	AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)	AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2)	AA AB AC AD BB BC BD CC CD DD

Функции Itertool

Следующий модуль состоит из функциоальных конструкций и возвращающих итераторы. Некоторые предоставляют потоки бесконечной длины, поэтому к ним должны обращаться только функции или циклы, которые усекают поток.

itertools.accumulate(iterable[, func, *, initial=None])

Создать итератор, который возвращает накопленные суммы или накопленные результаты других двоичных функций (указанных с помощью дополнительного аргумента func).

Если задано значение func, оно должно быть функцией двух аргументов. Элементы входного iterable могут быть любого типа, которые могут быть приняты в качестве аргументов для func. (Например, при операции добавления по умолчанию элементы могут быть любого добавляемого типа, включая Decimal или Fraction.

Обычно количество элементов на выходе соответствует входному итератору. Однако, если представлен ключевой аргумент initial, накопление приводит к initial значение, так что выход имеет на один элемент больше, чем входной итератор.

Примерно эквивалентный:

def accumulate(iterable, func=operator.add, *, initial=None):
    'Возврат промежуточных итогов'
    # accumulate([1,2,3,4,5]) --> 1 3 6 10 15
    # accumulate([1,2,3,4,5], initial=100) --> 100 101 103 106 110 115
    # accumulate([1,2,3,4,5], operator.mul) --> 1 2 6 24 120
    it = iter(iterable)
    total = initial
    if initial is None:
        try:
            total = next(it)
        except StopIteration:
            return
    yield total
    for element in it:
        total = func(total, element)
        yield total

Существует ряд применений аргумента func. Он может быть установлен на min() для запуска минимума, max() для выполнения максимума или operator.mul() для выполения произведения. Таблицы амортизации могут быть построены путем накопления процентов и применения платежей. Повторные отношения первого порядка может быть смоделирован, поставляя начальный значение в повторяемом и используя только общую сумму в аргументе func:

>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
>>> list(accumulate(data, operator.mul))     # выполняемое произведение
[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]
>>> list(accumulate(data, max))              # выполняемый максимум
[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]

# Амортизация 5% займа в 1000 с 4 ежегодными выплатами по 90
>>> cashflows = [1000, -90, -90, -90, -90]
>>> list(accumulate(cashflows, lambda bal, pmt: bal*1.05 + pmt))
[1000, 960.0, 918.0, 873.9000000000001, 827.5950000000001]

# Хаотическое рекуррентное отношение https://en.wikipedia.org/wiki/Logistic_map
>>> logistic_map = lambda x, _:  r * x * (1 - x)
>>> r = 3.8
>>> x0 = 0.4
>>> inputs = repeat(x0, 36)     # используется только начальное значение
>>> [format(x, '.2f') for x in accumulate(inputs, logistic_map)]
['0.40', '0.91', '0.30', '0.81', '0.60', '0.92', '0.29', '0.79', '0.63',
 '0.88', '0.39', '0.90', '0.33', '0.84', '0.52', '0.95', '0.18', '0.57',
 '0.93', '0.25', '0.71', '0.79', '0.63', '0.88', '0.39', '0.91', '0.32',
 '0.83', '0.54', '0.95', '0.20', '0.60', '0.91', '0.30', '0.80', '0.60']

См. functools.reduce() для подобной функции, что возвращает только финал накопившегося значения.

Добавлено в версии 3.2.

Изменено в версии 3.3: Добавлен дополнительный параметр func.

Изменено в версии 3.8: Добавлен дополнительный параметр initial.

itertools.chain(*iterables)

Создать итератор, который возвращает элементы из первого итерабля до тех пор, пока он не будет исчерпан, затем перейти к следующему итератору, пока не будут исчерпаны все итерабли. Используется для обработки последовательных последовательностей в виде одной последовательности. Примерно эквивалентно:

def chain(*iterables):
    # chain('ABC', 'DEF') --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

classmethod chain.from_iterable(iterable)

Альтернативный конструктор для chain(). Получает цепочечные входные данные из одного аргумента итерабля, который вычисляется лениво. Примерно эквивалентно:

def from_iterable(iterables):
    # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

itertools.combinations(iterable, r)

Возвращает r длины подпоследовательности элементов из входного iterable.

Комбинированные кортежи выдаются в лексикографическом порядке в соответствии с порядком ввода iterable. Таким образом, если входной iterable отсортирован, комбинационные кортежи будут созданы в отсортированном порядке.

Элементы рассматриваются как уникальные в зависимости от их положения, а не от их значение. Таким образом, если входные элементы будут уникальны, то в каждой комбинации не будет никакого повторного значения.

Примерно эквивалентный:

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

код для combinations() также может быть выражена как подпоследовательность permutations() после фильтрации записей, где элементы не в порядке сортировки (в соответствии с их положением во входном пуле):

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in permutations(range(n), r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

Число элементов возвращенный равно n! / r! / (n-r)! при 0 <= r <= n или нулю при r > n.

itertools.combinations_with_replacement(iterable, r)

Возвращает r длина подпоследовательности элементов из входного iterable, позволяющая повторять отдельные элементы более одного раза.

Комбинированные кортежи выдаются в лексикографическом порядке в соответствии с порядком ввода iterable. Таким образом, если входной iterable отсортирован, кортежи комбинации будут созданы в отсортированном порядке.

Элементы рассматриваются как уникальные в зависимости от их положения, а не от их значение. Таким образом, если входные элементы уникальны, сгенерированные комбинации также будут уникальны.

Примерно эквивалентный:

def combinations_with_replacement(iterable, r):
    # combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
    pool = tuple(iterable)
    n = len(pool)
    if not n and r:
        return
    indices = [0] * r
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != n - 1:
                break
        else:
            return
        indices[i:] = [indices[i] + 1] * (r - i)
        yield tuple(pool[i] for i in indices)

код для combinations_with_replacement() также может быть выражена как подпоследовательность product() после фильтрации записей, где элементы не в порядке сортировки (в соответствии с их положением во входном пуле):

def combinations_with_replacement(iterable, r):
    pool = tuple(iterable)
    n = len(pool)
    for indices in product(range(n), repeat=r):
        if sorted(indices) == list(indices):
            yield tuple(pool[i] for i in indices)

Количество возвращаемых элементов равно (n+r-1)! / r! / (n-1)! при n > 0.

Добавлено в версии 3.1.

itertools.compress(data, selectors)

Создать итератор, который фильтрует элементы от data, возвращая только те, которые имеют соответствующий элемент в selectors, который вычисляет как True. Останавливается, когда или data или selectors итераторы будут исчерпаны. Примерно эквивалентно:

def compress(data, selectors):
    # compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F
    return (d for d, s in zip(data, selectors) if s)

Добавлено в версии 3.1.

itertools.count(start=0, step=1)

Создать итератор, который возвращает равномерно созданные интервалы между значениями, начинающимся с номера start. Часто используемый как аргумент map(), чтобы произвести последовательные точки данных. Кроме того, используется с zip() для добавления порядковых номеров. Примерно эквивалентно:

def count(start=0, step=1):
    # count(10) --> 10 11 12 13 14 ...
    # count(2.5, 0.5) -> 2.5 3.0 3.5 ...
    n = start
    while True:
        yield n
        n += step

При подсчете с помощью чисел с плавающей запятой иногда можно достичь лучшей точности, подставляя мультипликативные код, такие как: (start + step * i for i in count()).

Изменено в версии 3.1: Добавлены аргументы step и допустимые аргументы, не являющиеся целыми.

itertools.cycle(iterable)

Создать итератор возвращающим элементы из итератора и сохраните копию каждого из них. Когда итератор исчерпан, элементы возвращаются из сохраненной копии. Повторяется бесконечно. Примерно эквивалентно:

def cycle(iterable):
    # cycle('ABCD') --> A B C D A B C D A B C D ...
    saved = []
    for element in iterable:
        yield element
        saved.append(element)
    while saved:
        for element in saved:
              yield element

Обратите внимание, что этот элемент инструментария может потребовать значительного дополнительного хранилища (в зависимости от длины итабля).

itertools.dropwhile(predicate, iterable)

Создать итератор, который удаляет элементы из итерабля до тех пор, пока предикат является истинным; после этого, возвращает каждый элемент. Обратите внимание, итератор не производит любой вывод, пока предикат сначала не становится ложным, таким образом, у этого может быть долгое время запуска. Примерно эквивалентно:

def dropwhile(predicate, iterable):
    # dropwhile(lambda x: x<5, [1,4,6,4,1]) --> 6 4 1
    iterable = iter(iterable)
    for x in iterable:
        if not predicate(x):
            yield x
            break
    for x in iterable:
        yield x

itertools.filterfalse(predicate, iterable)

Создать итератор, который фильтрует элементы из итератора, возвращая только те, для которых предикат является False. Если predicate является None, возвращает элементы, которые являются ложными. Примерно эквивалентно:

def filterfalse(predicate, iterable):
    # filterfalse(lambda x: x%2, range(10)) --> 0 2 4 6 8
    if predicate is None:
        predicate = bool
    for x in iterable:
        if not predicate(x):
            yield x

itertools.groupby(iterable, key=None)

Создать итератор, который возвращает последовательные ключи и группы из iterable. key - функция, вычисляя ключевой значение для каждого элемента. Если не определенный или None, по умолчанию key к функции идентичности и возвращает неизменный элемент. Как правило, итабль должен быть уже отсортирован по той же самой функции ключа.

Работа groupby() аналогична работе фильтра uniq в Unix. Он генерирует разрыв или новую группу каждый раз, когда меняется значение ключевой функции (поэтому обычно необходимо сортировать данные с помощью той же функции ключа). Это поведение отличается от поведения SQL GROUP BY, в котором агрегируются общие элементы независимо от их порядка ввода.

Группа возвращенный сама по себе является итератором, который разделяет лежащую в основе итерабль с groupby(). Поскольку исходный объект является общим, при расширении объекта groupby() предыдущая группа больше не отображается. Таким образом, если эти данные необходимы позже, они должны быть сохранены в виде списка:

groups = []
uniquekeys = []
data = sorted(data, key=keyfunc)
for k, g in groupby(data, keyfunc):
    groups.append(list(g))      # Сохранить групповой итератор в виде списка
    uniquekeys.append(k)

groupby() примерно эквивалентно:

class groupby:
    # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
    # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
    def __init__(self, iterable, key=None):
        if key is None:
            key = lambda x: x
        self.keyfunc = key
        self.it = iter(iterable)
        self.tgtkey = self.currkey = self.currvalue = object()
    def __iter__(self):
        return self
    def __next__(self):
        self.id = object()
        while self.currkey == self.tgtkey:
            self.currvalue = next(self.it)    # Выход на StopIteration
            self.currkey = self.keyfunc(self.currvalue)
        self.tgtkey = self.currkey
        return (self.currkey, self._grouper(self.tgtkey, self.id))
    def _grouper(self, tgtkey, id):
        while self.id is id and self.currkey == tgtkey:
            yield self.currvalue
            try:
                self.currvalue = next(self.it)
            except StopIteration:
                return
            self.currkey = self.keyfunc(self.currvalue)

itertools.islice(iterable, stop)

itertools.islice(iterable, start, stop[, step])

Создать итератор, который возвращает выбранные элементы из итератора. Если значение start не равно нулю, то элементы из итератора пропускаются до тех пор, пока не будет достигнут start. После этого элементы возвращенный последовательно, если не установлено значение step выше, что приводит к пропуску элементов. Если stop является None, то итерация продолжается до исчерпания итератора, если вообще; в противном случае он останавливается в указанном положении. В отличие от обычного нарезки, islice() не поддерживает отрицательные значения для start, stop или step. Может быть используемый для извлечения связанных полей из данных, в которых внутренняя структура была распрямлена (например, многострочный отчет может содержать поле имени в каждой третьей строке). Примерно эквивалентно:

def islice(iterable, *args):
    # islice('ABCDEFG', 2) --> A B
    # islice('ABCDEFG', 2, 4) --> C D
    # islice('ABCDEFG', 2, None) --> C D E F G
    # islice('ABCDEFG', 0, None, 2) --> A C E G
    s = slice(*args)
    start, stop, step = s.start or 0, s.stop or sys.maxsize, s.step or 1
    it = iter(range(start, stop, step))
    try:
        nexti = next(it)
    except StopIteration:
        # Потреблять *iterable* до *start* позиции.
        for i, element in zip(range(start), iterable):
            pass
        return
    try:
        for i, element in enumerate(iterable):
            if i == nexti:
                yield element
                nexti = next(it)
    except StopIteration:
        # Потреблять до *stop*.
        for i, element in zip(range(i + 1, stop), iterable):
            pass

Если start равно None, то итерация начинается с нуля. Если step имеет значение None, то шаг по умолчанию имеет значение 1.

itertools.permutations(iterable, r=None)

Возвращает последовательные перестановки длины r элементов в iterable.

Если r не определен или является None, то дефолты r к длине iterable и всех возможных перестановок во всю длину произведены.

Кортежи перестановок выдаются в лексикографическом порядке в соответствии с порядком ввода iterable. Итак, если вход iterable отсортирован, комбинации кортежей будут создаваться в отсортированном порядке.

Элементы рассматриваются как уникальные в зависимости от их положения, а не от их значение. Таким образом, если входные элементы будут уникальны, то в каждой перестановке не будет никакого повторного значения.

Примерно эквивалентный:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

код для permutations() также может быть выражена в виде подпоследовательности product(), отфильтрованной для исключения записей с повторяющимися элементами (элементами из той же позиции во входном пуле):

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Число элементов возвращенный равно n! / (n-r)! при 0 <= r <= n или нулю при r > n.

itertools.product(*iterables, repeat=1)

Декартовое произведение входных итералей.

Примерно эквивалентный вложенному для циклов в выражении генератор. Например, product(A, B) возвращает то же, что и ((x,y) for x in A for y in B).

Вложенные циклы циклируют как одометр с самым правым элементом, продвигающимся на каждой итерации. Этот шаблон создает лексикографический порядок, так что если итерабли входных данных отсортированы, кортежи продукта выдаются в отсортированном порядке.

Чтобы вычислить произведение итабля с самим собой, укажите число повторов с необязательным аргументом repeat ключевой. Например, product(A, repeat=4) означает то же, что и product(A, A, A, A).

Эта функция примерно эквивалентна следующему код, за исключением того, что фактическая реализация не создает промежуточные результаты в памяти:

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

itertools.repeat(object[, times])

Создать итератор, который возвращает object много раз. Выполняется бесконечно, если не указан аргумент times. Используется в качестве аргумента map() для инвариантных параметров к вызванной функции. Также используется с zip() для создания инвариантной части кортежа.

Примерно эквивалентный:

def repeat(object, times=None):
    # repeat(10, 3) --> 10 10 10
    if times is None:
        while True:
            yield object
    else:
        for i in range(times):
            yield object

Обычно для repeat используется подача потока постоянных значений в map или zip:

>>> list(map(pow, range(10), repeat(2)))
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

itertools.starmap(function, iterable)

Создать итератор, вычисляющий функцию с помощью аргументов, полученных из итератора. Используется вместо map(), когда параметры аргумента уже сгруппированы в кортежи из одного итабля (данные были предварительно заархивированы). Разница между map() и starmap() параллельна различению function(a,b) и function(*c). Примерно эквивалентно:

def starmap(function, iterable):
    # starmap(pow, [(2,5), (3,2), (10,3)]) --> 32 9 1000
    for args in iterable:
        yield function(*args)

itertools.takewhile(predicate, iterable)

Создать итератор, который возвращает элементы из итерабля до тех пор, пока предикат является истинным. Примерно эквивалентно:

def takewhile(predicate, iterable):
    # takewhile(lambda x: x<5, [1,4,6,4,1]) --> 1 4
    for x in iterable:
        if predicate(x):
            yield x
        else:
            break

itertools.tee(iterable, n=2)

Возвращает n независимые итераторы из одного итератора.

Следующий Python код помогает объяснить, что tee делает (хотя фактическая реализация более сложна и использует только единственную основную очередь FIFO).

Примерно эквивалентный:

def tee(iterable, n=2):
    it = iter(iterable)
    deques = [collections.deque() for i in range(n)]
    def gen(mydeque):
        while True:
            if not mydeque:             # когда локальная deque пуста
                try:
                    newval = next(it)   # получить новое значение и
                except StopIteration:
                    return
                for d in deques:        # загрузить все deques
                    d.append(newval)
            yield mydeque.popleft()
    return tuple(gen(d) for d in deques)

Как только tee() сделал разделение, оригинальный iterable не должен быть используемый больше нигде; в противном случае iterable может продвинуться без информирования объектов тройника.

tee итераторы не потокобезопасны. При одновременном использовании итераторов RuntimeError одним и тем же вызовом возвращенный может вызываться tee(), даже если исходный iterable является потокобезопасным.

Эта итертул может потребовать значительного дополнительного хранения (в зависимости от того, сколько временных данных необходимо хранить). Как правило, если один итератор использует большую часть или все данные перед запуском другого итератора, он быстрее использует list() вместо tee().

itertools.zip_longest(*iterables, fillvalue=None)

Создать итератор, объединяющий элементы из каждого итерабля. Если итерабли имеют неравномерную длину, отсутствующие значения заполняются fillvalue. Итерация продолжается до тех пор, пока не будет исчерпана самая длинная итерация. Примерно эквивалентно:

def zip_longest(*args, fillvalue=None):
    # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
    iterators = [iter(it) for it in args]
    num_active = len(iterators)
    if not num_active:
        return
    while True:
        values = []
        for i, it in enumerate(iterators):
            try:
                value = next(it)
            except StopIteration:
                num_active -= 1
                if not num_active:
                    return
                iterators[i] = repeat(fillvalue)
                value = fillvalue
            values.append(value)
        yield tuple(values)

Если один из итераблей потенциально бесконечен, то функция zip_longest() должна быть упакована с чем-то, что ограничивает количество вызовов (например, islice() или takewhile()). Если не определенный, по умолчанию fillvalue равен None.

Рецепты Itertools

В этом разделе представлены рецепты создания расширенного набора инструментов с использованием существующих итертул в качестве стандартных блоков.

По существу, все эти рецепты и многие, многие другие могут быть установлены из проекта more-itertools, найденных на Пакетном Индексе Python (Python Package Index):

pip install more-itertools

Расширенные инструменты обеспечивают такую же высокую производительность, как и основной набор инструментов. Превосходная производительность памяти поддерживается обрабатывающими элементами по одному, а не вводом всего итератора в память одновременно. Объем кода сохраняется за счет объединения инструментов в функциональном стиле, который помогает исключить временные переменные. Высокая скорость сохранена, предпочтя «векторизованные» стандартные блоки по использованию для циклов и генераторов, которые подвергаются интерпретатор наверху.

def take(n, iterable):
    "Вернуть первые n элементов итерируемого в виде списка"
    return list(islice(iterable, n))

def prepend(value, iterator):
    "Добавить одно значение перед итератором"
    # prepend(1, [2, 3, 4]) -> 1 2 3 4
    return chain([value], iterator)

def tabulate(function, start=0):
    "Вернуть function(0), function(1), ..."
    return map(function, count(start))

def tail(n, iterable):
    "Вернуть итератор для последних n элементов"
    # tail(3, 'ABCDEFG') --> E F G
    return iter(collections.deque(iterable, maxlen=n))

def consume(iterator, n=None):
    "Продвинуть итератор на n шагов вперед. Если n - None, потреблять полностью."
    # Использовать функции, которые используют итераторы на скорости C.
    if n is None:
        # подать весь итератор в deque нулевой длины
        collections.deque(iterator, maxlen=0)
    else:
        # перейти к пустому срезу, начиная с позиции n
        next(islice(iterator, n, n), None)

def nth(iterable, n, default=None):
    "Возвращает n-й элемент или значение по умолчанию"
    return next(islice(iterable, n, None), default)

def all_equal(iterable):
    "Возвращает True, если все элементы равны друг другу"
    g = groupby(iterable)
    return next(g, True) and not next(g, False)

def quantify(iterable, pred=bool):
    "Посчитать, сколько раз предикат верен"
    return sum(map(pred, iterable))

def padnone(iterable):
    """Возвращает элементы последовательности, а затем возвращает None бесконечно.

    Полезно для эмуляции поведения встроенной функции map().
    """
    return chain(iterable, repeat(None))

def ncycles(iterable, n):
    "Возвращает элементы последовательности n раз"
    return chain.from_iterable(repeat(tuple(iterable), n))

def dotproduct(vec1, vec2):
    return sum(map(operator.mul, vec1, vec2))

def flatten(list_of_lists):
    "Сгладить один уровень вложенности"
    return chain.from_iterable(list_of_lists)

def repeatfunc(func, times=None, *args):
    """Повторите вызовы func с указанными аргументами.

    Пример:  repeatfunc(random.random)
    """
    if times is None:
        return starmap(func, repeat(args))
    return starmap(func, repeat(args, times))

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

def grouper(iterable, n, fillvalue=None):
    "Собирать данные в блоки или блоки фиксированной длины"
    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return zip_longest(*args, fillvalue=fillvalue)

def roundrobin(*iterables):
    "roundrobin('ABC', 'D', 'EF') --> A D E B F C"
    # Рецепт зачислен George Sakkis
    num_active = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while num_active:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            # Удалить итератор, который мы только что исчерпали из цикла.
            num_active -= 1
            nexts = cycle(islice(nexts, num_active))

def partition(pred, iterable):
    'Использовать предикат для разделения записей на ложные и истинные записи'
    # partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9
    t1, t2 = tee(iterable)
    return filterfalse(pred, t1), filter(pred, t2)

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def unique_everseen(iterable, key=None):
    "Список уникальных элементов, сохраняющих порядок. Помните все элементы, которые когда-либо видели."
    # unique_everseen('AAAABBBCCDAABBB') --> A B C D
    # unique_everseen('ABBCcAD', str.lower) --> A B C D
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element

def unique_justseen(iterable, key=None):
    "Список уникальных элементов, сохраняющих порядок. Запомните только тот элемент, который только что видел."
    # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
    # unique_justseen('ABBCcAD', str.lower) --> A B C A D
    return map(next, map(operator.itemgetter(1), groupby(iterable, key)))

def iter_except(func, exception, first=None):
    """ Повторно вызывать функцию, пока не возникнет исключение.

    Преобразует интерфейс вызова до исключения в интерфейсе итератора. Как
    builtins.iter(func, sentinel), но использует исключение вместо часового для
    завершения цикла.

    Примеры:
        iter_except(functools.partial(heappop, h), IndexError)   # итератор очереди приоритетов
        iter_except(d.popitem, KeyError)                         # неблокирующий итератор dict
        iter_except(d.popleft, IndexError)                       # неблокирующий итератор deque
        iter_except(q.get_nowait, Queue.Empty)                   # зациклить на производителе Queue
        iter_except(s.pop, KeyError)                             # неблокирующий итератор множества

    """
    try:
        if first is not None:
            yield first()            # Для API баз данных, нуждающихся в начальном приведении к db.first()
        while True:
            yield func()
    except exception:
        pass

def first_true(iterable, default=False, pred=None):
    """Возвращает первое истинное значение в итерируемом.

    Если истинное значение не найдено, возвращает *default*

    Если *pred* не является None, возвращает первый элемент, для которого
    значение pred(item) истинно.

    """
    # first_true([a,b,c], x) --> a or b or c or x
    # first_true([a,b], x, f) --> a if f(a) else b if f(b) else x
    return next(filter(pred, iterable), default)

def random_product(*args, repeat=1):
    "Случайный выбор из itertools.product(*args, **kwds)"
    pools = [tuple(pool) for pool in args] * repeat
    return tuple(random.choice(pool) for pool in pools)

def random_permutation(iterable, r=None):
    "Случайный выбор из itertools.permutations(iterable, r)"
    pool = tuple(iterable)
    r = len(pool) if r is None else r
    return tuple(random.sample(pool, r))

def random_combination(iterable, r):
    "Случайный выбор из itertools.combinations(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.sample(range(n), r))
    return tuple(pool[i] for i in indices)

def random_combination_with_replacement(iterable, r):
    "Случайный выбор из itertools.combinations_with_replacement(iterable, r)"
    pool = tuple(iterable)
    n = len(pool)
    indices = sorted(random.randrange(n) for i in range(r))
    return tuple(pool[i] for i in indices)

def nth_combination(iterable, r, index):
    'Эквивалентно list(combinations(iterable, r))[index]'
    pool = tuple(iterable)
    n = len(pool)
    if r < 0 or r > n:
        raise ValueError
    c = 1
    k = min(r, n-r)
    for i in range(1, k+1):
        c = c * (n - k + i) // i
    if index < 0:
        index += c
    if index < 0 or index >= c:
        raise IndexError
    result = []
    while r:
        c, n, r = c*r//n, n-1, r-1
        while index >= c:
            index -= c
            c, n = c*(n-r)//n, n-1
        result.append(pool[-1-n])
    return tuple(result)