Группировать итерируемый предикатом в Python
Я разбираю файл следующим образом:
--header-- data1 data2 --header-- data3 Data4 данные 5 --header-- --header-- ...
И мне нужны такие группы:
- Могу ли я ускорить этот базовый код линейной алгебры?
- Подсчитайте, сколько матриц имеет полный ранг для всех подматриц
- Словарь Python vs list, который быстрее?
- Загрузка большого файла (25 тыс. Записей) в dict медленнее в Python?
- Длительность непрерывной работы без ненужных значений
[ [header, data1, data2], [header, data3, data4, data5], [header], [header], ... ] поэтому я могу перебирать их так:
for grp in group(open('file.txt'), lambda line: 'header' in line): for item in grp: process(item)
и сохранить логику обнаружения-группы отдельно от логики процесса-группы.
Но мне нужно повторить итерации, поскольку группы могут быть произвольно большими, и я не хочу их хранить. То есть, я хочу разбивать итерабельность на подгруппы каждый раз, когда я сталкиваюсь с элементом «дозорного» или «заголовка», как указано предикатом. Похоже, это было бы общей задачей, но я не могу найти эффективную реализацию Pythonic.
Вот глупая реализация append-to-a-list:
def group(iterable, isstart=lambda x: x): """Group `iterable` into groups starting with items where `isstart(item)` is true. Start items are included in the group. The first group may or may not have a start item. An empty `iterable` results in an empty result (zero groups).""" items = [] for item in iterable: if isstart(item) and items: yield iter(items) items = [] items.append(item) if items: yield iter(items)
Похоже, что есть хорошая версия itertools , но она ускользает от меня. «Очевидное» (?!) groupby решение, похоже, не работает, потому что могут быть соседние заголовки, и им нужно идти в отдельных группах. Лучшее, что я могу придумать: (ab) использовать groupby с ключевой функцией, которая хранит счетчик:
def igroup(iterable, isstart=lambda x: x): def keyfunc(item): if isstart(item): keyfunc.groupnum += 1 # Python 2's closures leave something to be desired return keyfunc.groupnum keyfunc.groupnum = 0 return (group for _, group in itertools.groupby(iterable, keyfunc))
Но я чувствую, что Python может сделать лучше – и, к сожалению, это еще медленнее, чем версия с немым списком:
# ipython % time deque (группа (xrange (10 ** 7), lambda x: x% 1000 == 0), maxlen = 0) CPU times: пользователь 4.20 s, sys: 0,03 с, всего: 4,23 с % time deque (igroup (xrange (10 ** 7), lambda x: x% 1000 == 0), maxlen = 0) CPU times: пользователь 5.45 s, sys: 0.01 с, всего: 5.46 с
Чтобы вам было легко, вот несколько модульных тестовых кодов:
class Test(unittest.TestCase): def test_group(self): MAXINT, MAXLEN, NUMTRIALS = 100, 100000, 21 isstart = lambda x: x == 0 self.assertEqual(next(igroup([], isstart), None), None) self.assertEqual([list(grp) for grp in igroup([0] * 3, isstart)], [[0]] * 3) self.assertEqual([list(grp) for grp in igroup([1] * 3, isstart)], [[1] * 3]) self.assertEqual(len(list(igroup([0,1,2] * 3, isstart))), 3) # Catch hangs when groups are not consumed for _ in xrange(NUMTRIALS): expected, items = itertools.tee(itertools.starmap(random.randint, itertools.repeat((0, MAXINT), random.randint(0, MAXLEN)))) for grpnum, grp in enumerate(igroup(items, isstart)): start = next(grp) self.assertTrue(isstart(start) or grpnum == 0) self.assertEqual(start, next(expected)) for item in grp: self.assertFalse(isstart(item)) self.assertEqual(item, next(expected))
Итак: как я могу сгруппировать итерабельную по предикату элегантно и эффективно в Python?
- Питонический способ вычисления среднего значения и дисперсии значений в счетчиках
- Разве divmod () быстрее, чем с помощью операторов% и //?
- Эффективное вычисление согласованного по границе среднего значения окрестности
- Что это за результат cProfile, говорящий мне, что мне нужно исправить?
- Векторизовать этот цикл цикла свертки более эффективно в numpy
4 Solutions collect form web for “Группировать итерируемый предикатом в 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