Улучшить функцию itertools.pairwise()
Я пытаюсь создать пользовательскую функцию, которая улучшает функцию itertools попарно.
В отличие от парной функции, которая возвращает пары элементов (n=2), я хотел бы иметь возможность указать длину группировки (n=x). Чтобы я мог возвращать группы элементов заданной длины. Это возможно?
Поэтому, когда n=2, групповая функция должна быть эквивалентна парной функции itertools. Но когда n=3, я ожидаю, что он вернет группы из 3.
Это то, что у меня есть до сих пор, что по сути то же самое, что и парная функция. т.е. работает для n=2.
Код:
from itertools import tee
my_string = 'abcdef'
def groupwise(iterable, n):
a = tee(iterable, n)
next(a[n-1], None)
return zip(a[0], a[1])
for item in groupwise(my_string, 2):
print("".join(item))
Выход:
ab
bc
cd
de
ef
Я пытаюсь изменить приведенный выше код, чтобы принять n=3, n=4, n=5, ... n=x, но я не могу придумать способ предоставить неопределенное количество компонентов функции zip, учитывая, что я хотел бы указать любое значение n <= len(my_string)
При n=3 вывод должен быть:
abc
bcd
cde
def
zip(*a[:n]) возвращает: aab, bbc, ccd, dde, eef. Если я не должен изменить что-то еще?
До того, как он был добавлен в itertools, pairwise был частью more-itertools. Вы все еще можете найти его там вместе с triplewise и другими оконными функциями. Функции windowed или sliding_window могут быть теми, которые вам нужны. more-itertools.readthedocs.io/en/stable/api.html#windowing
Вы можете обнаружить, что этот grouper от more_itertools работает лучше, чем доморощенный.
grouper не совсем делает то, что мне нужно.
Конечно, это возможно. Почему бы и нет? И разве это не просто sliding_window из собственных рецептов itertools Python?
Спасибо, Келли, да - похоже, что sliding_window и windowed из more_itertools - это функции, которые я ищу. Я не знал, что эти функции существуют. Отсюда мои усилия. Спасибо.
Ответы 2
tee, к сожалению, не будет масштабироваться таким образом. Написание pairwise занимает один вызов tee, и если вы хотите сделать это для N элементов в каждой группе, вам понадобится N-1 вызовов tee.
К счастью, мы можем добиться большего успеха, просто свернув петлю самостоятельно. Что мы собираемся сделать, так это отслеживать последние N элементов, которые мы видели сами, и yield их всякий раз, когда у нас есть достаточно большая группа. Для этого нам нужна структура данных, которая может эффективно добавлять элементы справа и вычитать их слева. collections.deque отлично подойдет. На самом деле, у него даже есть параметр maxlen, который автоматически вычитает слева именно тогда, когда нам это нужно.
from collections import deque
def groupwise(iterable, n):
accum = deque((), n)
for element in iterable:
accum.append(element)
if len(accum) == n:
yield tuple(accum)
Создайте пустую двухстороннюю очередь (первым аргументом конструктора являются начальные элементы: пустой кортеж), емкость которой равна n. Когда мы добавим более n элементов с правой стороны, он автоматически удалит самый левый. Мы могли бы сделать это вручную, но deque сделает это за нас, поэтому мы могли бы также использовать функциональность, которую они нам предоставили.
Затем повторите итерацию. Добавьте каждый элемент в конец двухсторонней очереди (удаляя слева по мере необходимости, чтобы удовлетворить требование максимальной длины). Затем, если в деке есть n элементов, мы yield его. Это делает нашу функцию функцией-генератором, поэтому она создаст новый итератор, состоящий из всех значений yielded.
Мы делаем неглубокую копию нашей двухсторонней очереди, поэтому мы не просто каждый раз получаем один и тот же (изменяемый) объект двухсторонней очереди. Мы также делаем эту неглубокую копию tuple, а не двухсторонней очередью, чтобы она больше соответствовала другим itertools функциям.
Для вызова используйте
print(list(groupwise(range(10), 3)))
# Output: [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6), (5, 6, 7), (6, 7, 8), (7, 8, 9)]
Вам не нужно if len(accum) == n:, если вы начинаете с полной очереди вместо пустой: iterator = iter(iterable); accum = deque(islice(iterator, n), maxlen=n); yield tuple(accum); for x in iterator: accum.append(x); yield tuple(accum). (где islice импортируется из itertools). Я не замерял время, но подозреваю, что если len(iterator) намного больше, чем n, отказ от этого теста может ускорить его.
Что вы имеете в виду под «не будет масштабироваться таким образом»?
И действительно ли нам «нужна структура данных, которая может эффективно добавлять элементы справа и вычитать их слева»? Что хорошего в O(1) обновлении дека, если вы все равно тратите O(n) на создание из него кортежа?
@Stef Это ошибка, вы получаете что-то, даже если итерация короче n.
@KellyBundy Действительно, я должен был сказать if len(accum) == n: yield tuple(accum) перед циклом. Что касается вашего комментария к deque: в любом случае нет способа избежать генерации O (n) кортежа. «Эффективно добавлять справа и удалять слева», возможно, преувеличение, но вам нужно как-то хранить элементы, так почему бы не очередь. Код для more_itertools.sliding_window тоже использует дек, хотя я не знаю, какие другие решения они сравнивали, прежде чем выбрать
@Stef Или просто инициализируйте с n-1 вместо n и удалите лишний доход. Я действительно удивлен, что ни рецепт itertools, ни more-itertools этого не делают. Конечно, deque работает, я просто не согласен с «необходимостью» его эффективной модификации здесь, когда это все равно затмевается. Использование кортежа вместо двухсторонней очереди может быть даже быстрее.
@Stef кортеж быстрее, чем deque с 10000 элементов и n=1000.
@KellyBundy Вы можете создать задачу или пул реквест на github.com/more-itertools/more-itertools
Согласно комментариям Стефа , есть и другие альтернативные ответы. Ни один из них существенно не отличается от ответа Сильвио, но я решил включить их сюда для полноты картины:
Код Стефа:
from itertools import islice
from collections import deque
def groupwise(iterable, n):
iterator = iter(iterable);
accum = deque(islice(iterator, n-1), maxlen=n);
for x in iterator:
accum.append(x);
yield tuple(accum)
Код Келли Банди:
from itertools import islice
def groupwise(iterable, n):
it = iter(iterable)
accum = None, *islice(it, n-1)
for x in zip(it):
accum = accum[1:] + x
yield accum
Код Ричи:
from itertools import islice
from collections import deque
def groupwise(iterable, n):
it = iter(iterable)
if n > 0 and len(accum := deque(islice(it, n-1), maxlen=n)) == n - 1:
return (accum.append(v) or tuple(accum) for v in it)
else:
return ()
Ричи v2 Код:
from itertools import islice
from collections import deque
def groupwise(iterable, n):
it = iter(iterable)
if n < 1:
return ()
accum = deque(islice(it, n-1), maxlen = n)
return (accum.append(v) or tuple(accum) for v in it)
Использование оконного режима:
Согласно комментарию Стефа, внутри more-itertools есть функция windowed, которая обеспечивает требуемую функциональность:
from more_itertools import windowed
my_string = 'abcdef'
for item in windowed(my_string, 3):
print("".join(item))
Версия ScottC, адаптированная из Windowed:
Заимствуем часть оконного кода и прислушиваемся к советам Келли Банди , Стефа и Ричи
from itertools import islice
from collections import deque
def groupwise(iterable, n):
if n < 1:
return None
it = iter(iterable)
accum = deque(islice(it, n-1), maxlen=n)
for _ in map(accum.append, it):
yield tuple(accum)
print(list(groupwise('abcde',3)))
Выход:
[('a', 'b', 'c'), ('b', 'c', 'd'), ('c', 'd', 'e')]
Поскольку вы работаете с итерируемыми объектами, нет гарантии, что они индексируются. То есть iterable[0:n-1] может рухнуть. Вместо этого я рекомендую использовать itertools.islice.
Обновлено - кажется, я все это уже рассмотрел?
@Stef Скорее всего, вызов len вылетит вместо этого.
@Kelly: Вы можете использовать None в качестве параметра остановки для itertools.islice, что даст именно желаемый эффект. Чего вы не можете сделать, так это остановить k элементов до конца итерации для значений k, отличных от нуля.
@rici Почему ты так говоришь?
@kelly: Потому что я рассматривал вызов len как аргумент islice, в котором нет необходимости. Очевидно, вы можете избавиться от использования len в начале, а затем проверить len(accum) после того, как вы его создадите.
Спасибо, rici - обновили, и звонки len были успешно удалены благодаря вашему вкладу. Когда n > len(iterable), функция groupwise возвращает None.
@rici Да, я имел в виду len(iterable) в коде ответа. Отвечая на комментарий Стефа о неиндексируемых итерируемых объектах, которые обычно также не поддерживают len, и этот вызов len появился до ныне удаленного среза, о котором говорил Стеф, поэтому вместо этого вызов len будет причиной сбоя. Да, длину можно проверить потом, хотя я не понимаю, как будет работать использование None as stop. И проверка длины в любом случае бессмысленна, если вы инициализируете n-1 вместо n элементов (использование n-1 и удаление дополнительного выхода было моим советом, который упоминается в ответе).
@ScottC Теперь последний сломан, например, list(groupwise(iter('abcde'), 3)) дает [('a', 'b', 'e')].
Попробуйте: print(list(groupwise('abcde',3)))
@Kelly: приношу извинения за публикацию кода в комментарии, но, поскольку этот вопрос закрыт, я больше ничего не могу сделать. Вот мое предложение: def groupwise(iterable, n): it = iter(iterable) if n > 0 and len(accum := deque(islice(it, n-1), maxlen=n)) == n - 1: return (accum.append(v) or tuple(accum) for v in it) else: return ()
@ScottC Почему я должен это попробовать?
Это позволяет полностью избежать второго вызова islice. Но моей первоначальной мыслью было заменить второй вызов на islice(iterable, n-1, None). Не первый звонок.
@rici А, я даже не заметил эту секунду islice раньше. Отчасти потому, что экран моего телефона слишком узок, чтобы показать все решение, отчасти потому, что я никогда полностью не просматривал это решение, а отчасти потому, что я не ожидал этого второго islice, потому что это просто неправильно (теряет элементы, если итерируемый объект является итератором) . На мой взгляд, «код Стефа» лучше всего подходит для использования deque (теперь, когда он инициализируется с n-1). Кстати, он закрыт как дубликат, поэтому, если у вас есть хорошая альтернатива, вы можете опубликовать его под другим вопросом :-)
@rici Да, и теперь, если вы измените genexp на обычный цикл, сделав функцию функцией генератора, вам не понадобится or хак. И я думаю, что это было бы более читабельно.
СкоттК:; Чтобы решить проблему, на которую указывает @kelly, вам нужен it = iter(iterable), как в моем коде, и тогда вам не нужен второй islice. Так что это также позволяет избежать повторения первых n-1 элементов дважды.
@rici Как это может быть быстрее? Он делает то же самое, за исключением того, что вы выполняете дополнительную проверку правды и (не-) прыжок. (О, и у вас, вероятно, есть load_deref вместо load_fast, но я думаю, что сейчас это почти такая же скорость.)
@kelly: я думаю, ты прав. Там нет большой разницы, и она зависит от длины итерации, но в большинстве случаев ваш путь немного быстрее, согласно быстрому ненаучному тесту.
@rici разница выражения генератора и функции генератора взята из этого. Как и ожидалось, они идентичны, за исключением того, что вы выполняете дополнительные/медленные действия, о которых я упоминал. (Конечно, это Python 3.8, не уверен в более новых версиях).
@kelly: хорошо, я попытаюсь выяснить, почему я вижу разницу в скорости (хотя и незначительную) при тестировании на v3.11. Вы, безусловно, правы насчет хакерства return (q.append(v) or tuple(q) for v in it). К сожалению, нет appended(q, v), который возвращает q после добавления v; по-видимому, желание сделать это не является питоническим. Виновен по обвинению, что и привело меня к этой неудачной идиоме. Но вы также можете вернуть генератор, используя, возможно, менее хакерский return (tuple(q) for _ in map(q.append, it)), который может быть моим последним решением этой отвлекающей проблемы.
это для версии 1 или версии 2 - я могу обновить ее, если хотите?
@rici Вы пробовали сравнивать результаты dis в 3.11? Может сейчас есть другие отличия. Хотя я скорее в этом сомневаюсь. appended нет, но есть __iadd__ и iconcat.
Попробуйте
zip(*a[:n])?