Евгений Степанищев

Я — эксперт в области разработки веб-приложений и безопасности в интернете. Каждый месяц мой блог посещают около 90 тысяч человек. Работаю техническим директором в «Системах документооборота», занимаюсь электронным правительством.

Сон разума: снится 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)]
16 сентября 2008 17:16

karguine.ya.ru (karguine.ya.ru)
16 сентября 2008, 18:17

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

bolk (bolknote.ru)
16 сентября 2008, 18:29, ответ предназначен karguine.ya.ru:

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

isagalaev (softwaremaniacs.org/about/)
16 сентября 2008, 20:57

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

    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: "а на Хаскеле это было бы еще проще"

bolk (bolknote.ru)
16 сентября 2008, 21:40, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

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

bolk (bolknote.ru)
16 сентября 2008, 22:11, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

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

bolk (bolknote.ru)
16 сентября 2008, 22:34, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

isagalaev (softwaremaniacs.org/about/)
16 сентября 2008, 23:08

Пока дошел до метро, придумал решение короче. А пока ехал в метро -- реализовал, благо с собой 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)

bolk (bolknote.ru)
16 сентября 2008, 23:23, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

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

isagalaev (softwaremaniacs.org/about/)
16 сентября 2008, 23:33

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

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

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

bolk (bolknote.ru)
16 сентября 2008, 23:35, ответ предназначен isagalaev (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, за что спасибо.

bolk (bolknote.ru)
16 сентября 2008, 23:36, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

bolk (bolknote.ru)
16 сентября 2008, 23:54, ответ предназначен isagalaev (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], iter((i, list(g)) for i, g in groupby(chain(['']*3, letter, ['']*3), lambda x:x))))][1:-1]

bolk (bolknote.ru)
16 сентября 2008, 23:57

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

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

bolk (bolknote.ru)
16 сентября 2008, 23:59

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

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

bolk (bolknote.ru)
17 сентября 2008, 00:13, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

isagalaev (softwaremaniacs.org/about/)
17 сентября 2008, 00:15

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

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

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

isagalaev (softwaremaniacs.org/about/)
17 сентября 2008, 00:19

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

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

bolk (bolknote.ru)
17 сентября 2008, 00:19, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

isagalaev (softwaremaniacs.org/about/)
17 сентября 2008, 00:23

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

bolk (bolknote.ru)
17 сентября 2008, 00:25, ответ предназначен isagalaev (softwaremaniacs.org/about/):

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

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)

Подсказка по написанию комментария

В комментариях можно применять следующую специальную разметку:

  • слово, обрамлённое в «звёздочки» выделяется *жирным*
  • ссылка становится ссылкой: http://bolknote.ru
  • ссылка в скобках также становится ссылкой, закрывающая скобка не захватывается: (http://bolknote.ru)
  • каждую строку цитаты следует начинать со знака «больше»:
    > это цитата
    > из двух строк

  • можно вставить картинку, залитую на один из сервисов: «Яндекс.Фотки», «Фликр» или «Пикплз». Для этого нужно вставить на страницу полный адрес вашей картинки на сервисе, он превратится в картинку:

    http://fotki.yandex.ru/users/bolknote/view/274311?page=3