Группировать итерируемый предикатом в Python

Я не совсем прочитал весь ваш код, но я думаю, что это может помочь:

 from itertools import izip, tee, chain def pairwise(iterable): a, b = tee(iterable) return izip(a, chain(b, [next(b, None)])) def group(iterable, isstart): pairs = pairwise(iterable) def extract(current, lookahead, pairs=pairs, isstart=isstart): yield current if isstart(lookahead): return for current, lookahead in pairs: yield current if isstart(lookahead): return for start, lookahead in pairs: gen = extract(start, lookahead) yield gen for _ in gen: pass for gen in group(xrange(4, 16), lambda x: x % 5 == 0): print '------------------' for n in gen: print n print [list(g) for g in group([], lambda x: x % 5 == 0)] 

Результат:

 $ python gen.py ------------------ 4 ------------------ 5 6 7 8 9 ------------------ 10 11 12 13 14 ------------------ 15 [] 

Редактировать:

И вот еще одно решение, подобное вышеизложенному, но без pairwise() и часового вместо этого. Я не знаю, какой из них быстрее:

 def group(iterable, isstart): sentinel = object() def interleave(iterable=iterable, isstart=isstart, sentinel=sentinel): for item in iterable: if isstart(item): yield sentinel yield item items = interleave() def extract(item, items=items, isstart=isstart, sentinel=sentinel): if item is not sentinel: yield item for item in items: if item is sentinel: return yield item for lookahead in items: gen = extract(lookahead) yield gen for _ in gen: pass 

Оба теперь проходят тест, благодаря идее JFSebastians об истощении пропущенных генераторов подгрупп.

как я могу изящно и эффективно подбирать итеративный предикат в Python?

Вот краткая, эффективная с точки зрения памяти реализация, которая очень похожа на ту, что была из вашего вопроса:

 from itertools import groupby, imap from operator import itemgetter def igroup(iterable, isstart): def key(item, count=[False]): if isstart(item): count[0] = not count[0] # start new group return count[0] return imap(itemgetter(1), groupby(iterable, key)) 

Он поддерживает бесконечные группы.

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

 from itertools import islice, tee def group(iterable, isstart): it, it2 = tee(iterable) count = 0 for item in it: if isstart(item) and count: gr = islice(it2, count) yield gr for _ in gr: # skip to the next group pass count = 0 count += 1 if count: gr = islice(it2, count) yield gr for _ in gr: # skip to the next group pass 

groupby может быть реализован в чистом Python:

 def igroup_inline_key(iterable, isstart): it = iter(iterable) def grouper(): """Yield items from a single group.""" while not p[START]: yield p[VALUE] # each group has at least one element (a header) p[VALUE] = next(it) p[START] = isstart(p[VALUE]) p = [None]*2 # workaround the absence of `nonlocal` keyword in Python 2.x START, VALUE = 0, 1 p[VALUE] = next(it) while True: p[START] = False # to distinguish EOF and a start of new group yield grouper() while not p[START]: # skip to the next group p[VALUE] = next(it) p[START] = isstart(p[VALUE]) 

Чтобы избежать повторения кода, while True цикл while True может быть записан как:

 while True: p[START] = False # to distinguish EOF and a start of new group g = grouper() yield g if not p[START]: # skip to the next group for _ in g: pass if not p[START]: # EOF break 

Хотя предыдущий вариант может быть более явным и читаемым.

Я думаю, что общее эффективное решение для памяти в чистом Python не будет значительно быстрее, чем на основе groupby .

Если process(item) выполняется быстро по сравнению с igroup() и заголовок может быть эффективно найден в строке (например, для фиксированного статического заголовка), вы можете повысить производительность, прочитав файл в больших кусках и разделив его на значение заголовка . Это должно сделать вашу задачу связанной с IO.

Главное, что вам нужно написать генератор, который дает подгенераторы. Мое решение похоже на концепцию по методу @pillmuncher, но более самодостаточно, потому что оно позволяет избежать использования механизмов itertools для создания вспомогательных генераторов. Недостатком является то, что я должен использовать несколько неэлегантный список темпов. В Python 3 это может быть сделано более красиво с nonlocal .

 def grouper(iterable, isstart): it = iter(iterable) last = [next(it)] def subgroup(): while True: toYield = last[0] try: last.append(next(it)) except StopIteration, e: last.pop(0) yield toYield raise StopIteration else: yield toYield last.pop(0) if isstart(last[0]): raise StopIteration while True: sg = subgroup() yield sg if len(last) == 2: # subgenerator was aborted before completion, let's finish it for a in sg: pass if last: # sub-generator left next element waiting, next sub-generator will yield it pass else: # sub-generator left "last" empty because source iterable was exhausted raise StopIteration >>> for g in grouper([0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0], lambda x: x==0): ... print "Group", ... for i in g: ... print i, ... print Group 0 1 1 Group 0 1 Group 0 1 1 1 1 Group 0 

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

Редактирование: я проверил ваш юнит-тест на ваших оригинальных двух и моих. Похоже, что мой немного быстрее, чем ваша igroup но все же медленнее, чем версия на основе списка. Естественно, что вам нужно будет сделать компромисс между скоростью и памятью здесь; если вы знаете, что группы не будут слишком ужасными, используйте версию на основе списка для скорости. Если группы могут быть огромными, используйте версию на основе генератора, чтобы сохранить использование памяти.

Редактирование: отредактированная версия выше обрабатывает по-разному. Если вы выйдете из подгенератора, но возобновите внешний генератор, он пропустит оставшуюся часть прерванной группы и начнет следующую группу:

 >>> for g in grouper([0, 1, 2, 88, 3, 0, 1, 88, 2, 3, 4, 0, 1, 2, 3, 88, 4], lambda x: x==0): ... print "Group", ... for i in g: ... print i, ... if i==88: ... break ... print Group 0 1 2 88 Group 0 1 88 Group 0 1 2 3 88 

Итак, вот еще одна версия, которая пытается сшить пары подстроек из groupby с chain . Это заметно быстрее для теста производительности, но гораздо медленнее, когда есть много небольших групп (например, isstart = lambda x: x % 2 == 0 ). Он обманывает и перезаписывает повторяющиеся заголовки (вы можете обойти это с помощью трюков с итератором «все-таки-все-таки»). Это также шаг назад в отделе элегантности, поэтому я думаю, что по-прежнему предпочитаю оригинал.

 def group2(iterable, isstart=lambda x: x): groups = itertools.groupby(iterable, isstart) start, group = next(groups) if not start: # Deal with initial non-start group yield group _, group = next(groups) groups = (grp for _, grp in groups) while True: # group will always be start item(s) now group = list(group) for item in group[0:-1]: # Back-to-back start items... and hope this doesn't get very big. :) yield iter([item]) yield itertools.chain([group[-1]], next(groups, [])) # Start item plus subsequent non-start items group = next(groups) 

 % time deque (group2 (xrange (10 ** 7), lambda x: x% 1000 == 0), maxlen = 0)
 CPU times: пользователь 3.13 s, sys: 0.00 s, всего: 3.13 s