itertools – Функции, создающие итераторы для эффективной работы с циклами¶itertools – Functions creating iterators for efficient looping

Функции итераторных инструментов¶Itertool functions

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

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

itertools.chain.from_iterable(iterable)¶

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

@classmethod
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.

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

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

Эквивалентно следующему:

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 1:
        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.count([n])¶

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

def count(n=0):
    # count(10) --> 10 11 12 13 14 ...
    while True:
        yield n
        n += 1

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])¶

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

Работа groupby() похожа на фильтр uniq в Unix. Она создаёт разрыв или новую группу каждый раз, когда значение ключевой функции меняется (именно поэтому данные обычно необходимо отсортировать с помощью той же ключевой функции). Такое поведение отличается от SQL’s 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(object):
    # [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):
        while self.currkey == self.tgtkey:
            self.currvalue = next(self.it) # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)
        self.tgtkey = self.currkey
        return (self.currkey, self._grouper(self.tgtkey))
    def _grouper(self, tgtkey):
        while self.currkey == tgtkey:
            yield self.currvalue
            self.currvalue = next(self.it) # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)

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

Создаёт итератор, который возвращает выбранные элементы из iterable. Если start не равен нулю, то элементы из iterable пропускаются до тех пор, пока не будет достигнут 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)
    it = range(s.start or 0, s.stop or sys.maxsize, s.step or 1)
    nexti = next(it)
    for i, element in enumerate(iterable):
        if i == nexti:
            yield element
            nexti = next(it)

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

itertools.permutations(iterable[, r])¶

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

Если r не указан или равен None, то r по умолчанию принимает длину 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 = 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])¶

Декартово произведение входных итерируемых объектов.

Эквивалентно вложенным циклам for в генераторном выражении. Например, 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 = map(tuple, 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

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 независимых итераторов из одного итерируемого объекта. Случай, когда n==2, эквивалентен:

def tee(iterable):
    def gen(next, data={}):
        for i in count():
            if i in data:
                yield data.pop(i)
            else:
                data[i] = next()
                yield data[i]
    it = iter(iterable)
    return (gen(it.__next__), gen(it.__next__))

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

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

itertools.zip_longest(*iterables[, fillvalue])¶

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

def zip_longest(*args, fillvalue=None):
    # zip_longest('ABCD', 'xy', fillvalue='-') --> Ax By C- D-
    def sentinel(counter = ([fillvalue]*(len(args)-1)).pop):
        yield counter()         # выдаёт fillvalue или вызывает IndexError
    fillers = repeat(fillvalue)
    iters = [chain(it, sentinel(), fillers) for it in args]
    try:
        for tup in zip(*iters):
            yield tup
    except IndexError:
        pass

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

Примеры¶Examples

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

>>> # Показать словарь, отсортированный и сгруппированный по значению
>>> from operator import itemgetter
>>> d = dict(a=1, b=2, c=1, d=2, e=1, f=2, g=3)
>>> di = sorted(d.items(), key=itemgetter(1))
>>> for k, g in groupby(di, key=itemgetter(1)):
...     print(k, map(itemgetter(0), g))
...
1 ['a', 'c', 'e']
2 ['b', 'd', 'f']
3 ['g']

>>> # Найти последовательности подряд идущих чисел с помощью groupby. Ключ к решению
>>> # заключается в вычитании с помощью range, благодаря чему все подряд идущие числа оказываются в одной группе.
>>> # same group.
>>> data = [ 1,  4,5,6, 10, 15,16,17,18, 22, 25,26,27,28]
>>> for k, g in groupby(enumerate(data), lambda t:t[0]-t[1]):
...     print(map(operator.itemgetter(1), g))
...
[1]
[4, 5, 6]
[10]
[15, 16, 17, 18]
[22]
[25, 26, 27, 28]

Рецепты¶Recipes

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

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

def take(n, iterable):
    "Return first n items of the iterable as a list"
    return list(islice(iterable, n))

def enumerate(iterable, start=0):
    return zip(count(start), iterable)

def tabulate(function, start=0):
    "Return function(0), function(1), ..."
    return map(function, count(start))

def nth(iterable, n):
    "Returns the nth item or None"
    return next(islice(iterable, n, None), None)

def quantify(iterable, pred=bool):
    "Count how many times the predicate is true"
    return sum(map(pred, iterable))

def padnone(iterable):
    """Returns the sequence elements and then returns None indefinitely.

    Useful for emulating the behavior of the built-in map() function.
    """
    return chain(iterable, repeat(None))

def ncycles(iterable, n):
    "Returns the sequence elements n times"
    return chain.from_iterable(repeat(iterable, n))

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

def flatten(listOfLists):
    return list(chain.from_iterable(listOfLists))

def repeatfunc(func, times=None, *args):
    """Repeat calls to func with specified arguments.

    Example:  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)
    for elem in b:
        break
    return zip(a, b)

def grouper(n, iterable, fillvalue=None):
    "grouper(3, 'ABCDEFG', '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"
    # Recipe credited to George Sakkis
    pending = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while pending:
        try:
            for next in nexts:
                yield next()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))

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 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)

def combinations_with_replacement(iterable, r):
    "combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC"
    # number items returned:  (n+r-1)! / r! / (n-1)!
    pool = tuple(iterable)
    n = len(pool)
    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)

 def unique_everseen(iterable, key=None):
     "List unique elements, preserving order. Remember all elements ever seen."
     # 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 iterable:
             if element not in seen:
                 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):
     "List unique elements, preserving order. Remember only the element just seen."
     # unique_justseen('AAAABBBCCDAABBB') --> A B C D A B
     # unique_justseen('ABBCcAD', str.lower) --> A B C A D
     return map(next, map(itemgetter(1), groupby(iterable, key)))