Это сайт — моя персональная записная книжка. Интересна мне, по большей части, история, своя жизнь и немного программирование.

Сон разума: снится Python

Вот что родил мой мозг в текущем проекте:

def trim(letter):
    SKIPLEAD = object()
    SKIPINNE = object()

    todelete, stage, skipped = [], SKIPLEAD, 0

    for idx, blank in enumerate([x == '' for x in letter]):
        if stage == SKIPLEAD:
            if blank:
                todelete.append(idx)
            else:
                stage = SKIPINNE
        else:
            if blank:
                skipped += 1
                todelete.append(idx)
            else:
                if 0 < skipped < 3:
                     todelete = todelete[0:-skipped]
    return [letter[idx] for idx in set(range(0, len(letter))) - set(todelete)]
20 комментариев
karguine.ya.ru 2008

Понять бы ещё, для чего это. =)

Евгений Степанищев (bolknote.ru) 2008

Комментарий для karguine.ya.ru:

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

isagalaev (softwaremaniacs.org/about/) 2008

Нам тут показалось, что условие «от трех пробелов -​-​ выкидывать» нелогичное... Кажется, что вместо него должно быть что-то типа «от трех пробелов -​-​ сокращать до двух». Но да ладно. Если взять ровно такое описание задачки, то у меня получилось вот так:

    from itertools import dropwhile, groupby, chain
    def trim(letter):
        letter = dropwhile(lambda l: not l, letter)
        empty = []
        for l in letter:
            if not l:
                empty.append(l)
            else:
                if 0 < len(empty) < 3:
                    for e in empty:
                        yield e
                empty = []
                yield l

А потом я позвал elephantum’а, который помнит функцию groupby, которую я не помню. Вышел отрыв башки :-)

    def trim(ll):
        for k, grp in groupby(
                          dropwhile(
                              lambda l: not l,
                              chain(ll, [’’, ’’, ’’])),
                          lambda x:x):
            grp = list(grp)
            if k or len(grp) < 3:
                for i in grp: yield i

Так что выкидывай свои императивные привычки :-). Особенно эти «SKIPLEAD = object()»

P.S. elephantum: «а на Хаскеле это было бы еще проще»

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Спасибо, отформатирую и попробую понять что вы тут понаписали :)

P.S. hCard так и не пашет. Вот они сторонние сервисы! Буду глубоко отлаживать.

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Спасибо ещё раз!

Зря я не уделял внимание itertools, очень и очень полезная штука.

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Ага, разобрался. Могу уже внятно объяснить, почему нули пропадут в начале списка и любая последовательность из трёх и больше нулей — в любом месте.

isagalaev (softwaremaniacs.org/about/) 2008

Пока дошел до метро, придумал решение короче. А пока ехал в метро -​-​ реализовал, благо с собой Nokia с Питоном :-) ( http://fotki.yandex.ru/users/isagalaev/view/101414/ )

    from itertools import chain, groupby, imap
    def trim(letters):
        return chain(*imap(lambda (k, g): g if k or len(g) < 3 else [], imap(lambda (k, g): (k, list(g)), groupby(chain([’’] * 3, letters, [’’] * 3), lambda x:x))))

Да, это в одну строку :-). Более понятно будет так:

def trim(letters):
    letters = chain([’’] * 3, letters, [’’] * 3)
    letters = groupby(letters, lambda x:x)
    letters = imap(lambda (k, g): (k, list(g)), letters)
    letters = imap(lambda (k, g): g if k or len(g) < 3 else [], letters)
    return chain(*letters)

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

кстати, надо chain вынести за dropwhile в варианте №2. [’’]*3 я тоже догадался использовать :)

Щас ещё свой вариант выложу ;)

isagalaev (softwaremaniacs.org/about/) 2008

Секундочку, я еще не закончил!

Оказывается, на генераторных выражениях покороче получается из-за меньшего числа lambda:

from itertools import chain, groupby
def trim(letters):
    return chain(*(g for k, g in list(g for k, g in groupby(chain([’’] * 3, letters, [’’] * 3), lambda x:x)) if k or len(g) < 3))

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Кстати, расшифровка лишняя, голову я уже проапгрейдил. Вот мой вариант (вызов *func подсмотрел у тебя, до этого сам не додумался, хотя синтаксис знаю, с ним отвалился и ifilterfalse, которым я отфильтровывал пустой список):

print [x for x in chain(*starmap(lambda item, grp: grp if item != ’’ or len(grp)<3 else [],imap(lambda (item, grp): (item, list(grp)), groupby(chain([’’]*3, letter, [’’]*3), lambda x:x))))]

level up, за что спасибо.

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Ага, я генератором условие пытался сделать, но упёрся в необходимость преобразовования grp в list, показалось неэстетичным. Так лучше, да.

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

В общем, я всё-таки выбрал вариант на итераторах, как (потенциально) жрущий меньше памяти, хотя и вариант на генераторах очень интересен (я даже попробовал гибридный, с переходом через iter). И конструкцию Python 2.5 тоже убрал, у нас на проде 2.4.

В итоге, вот что вышло (задачу я модифицировал, так как аргумент замену 3+ пустых строк на одну — разумен):

print [x for x in chain(*starmap(lambda item, grp: [grp, [’’]][item == ’’ and len(grp)>2], iterlist(g for i, g in groupby(chain([’’]*3, letter, [’’]*3), lambda x:x))))][1:-1]

Евгений Степанищев (bolknote.ru) 2008

Отлично повеселились. Если я полюблю Python, то за итераторы и генераторы :)

Это то, что мне не хватало при переходе с Perl на PHP. Спасибо за itertool :)

Евгений Степанищев (bolknote.ru) 2008

Заметка для себя:

не забыть завтра при замене этого куска выкинуть «print [x for x in» и вставить туда просто list.

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Чёрт. Не тот вариант оставил. Щас напишу отдельным постом.

isagalaev (softwaremaniacs.org/about/) 2008

Кажется тут есть какое-то недопонимание...

Во-первых, «итератор» и «генератор» не взаимоисключающие слова. Генератор -​-​ это один из способов сделать итератор.

Во-вторых, конструкция (x for x in iterable) принципиально отличается от [x for x in iterable] тем, что как раз не создает в памяти собственно списка, поэтому если ты хочешь экономить память, то надо использовать именно генераторные выражения (в круглых скобках), а не list comprehension (в квадратных).

isagalaev (softwaremaniacs.org/about/) 2008

Кстати, помимо экономии памяти генераторные выражения еще и быстрее в таки вот цепочных операциях. Потому что вещи типа [x for x in [i for i in iterable]] реально бегают по списку столько раз, сколько вложены. То же самое скруглыми скобками пробегают по изначальному итератору ровно один раз, применяя все преобразования к каждому элементу.

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

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Ага, я поковырял что вышло и понял где у моя ошибка. Я просто не поставил скобки вокруг генератора и решил, что генераторы и итераторы — вещи разные.

isagalaev (softwaremaniacs.org/about/) 2008

Скобки там и правда местами опциональны. Например если ты указываешь генераторное выражения прямо в параметрах функции: f(x for x in iterable) эквивалентно ffor x in iterable

Евгений Степанищев (bolknote.ru) 2008

Комментарий для softwaremaniacs.org/about/:

Вынес результат отдельным постом, видоизменив задачу. Кстати, если ещё не спишь, подскажи: a if b else c есть в __future__, если есть, то как подключается, если сходу вспомнишь. Если нет, завтра сам прочитаю.