Пишу, по большей части, про историю, свою жизнь и немного про программирование.

Python iterstrip: itertools для чайников

Я общел рассказать как работает конструкция, которую мы, в итоге, в Ваней породили для тех, кто не знаком с itertools в Python. Для начала формулировка задачи: есть список (list) последовательности строк. В нём все поледовательности пустых строк, длиной более двух надо заменить на одну пустую строку, а пустые строке в начале и конце списка удалить.

Из [’’, 1, 2, 3, ’’, ’’, ’’, ’’, 4, ’’, ’’] мы должны получить аккуратное [1, 2, 3, ’’, 4].

Код, который получился в итоге, с некоторыми упращениями, выглядит вот так:

return list(
            chain(
                *(
                    [[''], grp][item or len(grp)<3]
                        for item, grp in (item, list(grp))
                            for item, grp in groupby(chain(['']*3, letter, ['']*3), lambda x:x))
                )
                )
        )[1:-1]

Заголовок функции я приводить не буду, чтобы не плодить отступы, в функцию входит параметр letter, который содержит обрабатываемый список, возвращается, соответственно, обработанный список. Я постараюсь обойтись без определения генераторов и итераторов, просто представьте, что данные «текут» по функциям, что позволяет их обрабатывать очень экономично, даже если они бесконечные.

Центральное место этой программы, функция groupby группирует входящий список, пользуясь результатом функции, записанной во втором параметре, как признаком группировки. Список не пересортируются, в группы объединяются данные, идущие подряд. На выходе появляется список туплов (tuples), состоящих из результата работы функции, применительно к группе и списка (точнее объекта _grouper) объединённых результатов:

[(x, list(k)) for x, k in groupby([1,2,3,-4,-1,2], lambda x: x>=0)]

Я тут прошёлся по списку [1, 2, 3, -4, -1, 2], объединяя его значения при помощи функции x>=0. Т. е. все подряд идущие числа с одинаковым знаком будут сгруппированы. Получится вот что:

[(True, [1, 2, 3]), (False, [-4, -1]), (True, [2])]

сверху на groupby я навесил генератор — по сути, цикл, который проходит по всем элементам groupby, раскладывая тупл (tuple) в два элемента — x и k. Этот цикл для каждой итерации возвращает результат, форма которого записана перед циклом. Это тупл, состоящий из двух элементов: k (где записан результат группировочной функции) я оставил неизменным, а объект _grouper я преобразовал в список.

Функция chain объединяет итератор, для простоты можно пока представить, что она склеивает списки. Конструкция «[’’]*3» эквивалентна [’’, ’’, ’’] — трём пустым строкам. Таким образом, строка «for item, grp in groupby(chain([’’]*3, letter, [’’]*3), lambda x:x))» делает следующее: по итератору, состоящему из трёх пустых строк, нашего списка letter и ещё трёх пустых строк, проходит функция groupby, которая группирует элементы по самому простому признаку: «lambda x: x», т. е. группируются одинаковые элементы, далее по получившемуся списку туплов проходит цикл, каждый тупл раскладывается на два элемента: item и grp, где из grp делается список (при помощи вызова «list»).

Выше находится конструкция «[ [’’, grp] ][item or len(grp)<n]», выглядит она страшно и кажется «птичим языком», но на деле широко применяется в самых разнообразных языках, включая PHP, сейчас я её объясню. Результатом «item or len(grp)<n» будет True или False. Условие, на мой взгляд, очевидное: если строка не пустая или последовательность меньше 3, то True. True и False используются как индекс списка и выбирают, соответственно, первый или нулевой элемент массива, т. е. список, содержащий пустую строку или группу символов.

Цепочка такая:

Иcходная последовательность: [’’, ’1’, ’1’, ’’, ’’, ’’, ’3’, ’’, ’5’] Добавили с двух сторон пробельные строки: [’’, ’’, ’’, ’’, ’1’, ’1’, ’’, ’’, ’3’, ’’, ’5’, ’’, ’’, ’’] Прошли groupby и генератор: [ (’’, [’’, ’’, ’’, ’’]), (’1’, [’1’, ’1’]), (’’, [’’, ’’]), (’3’, [’3’]), (’’, [’’]), (’5’, [’5’]), (’’, [’’, ’’, ’’]) ] Прошли через условие на птичьем языке: [ [’’], [’1’, ’1’], [’’, ’’], [’3’], [’’], [’5’], [’’] ]

Далее у нас стоит chain, который принимает аргументом всё, что получилось, но с префиксом звёздочка. Chain, как я писал выше, объединяет итераторы, для простоты мы считаем, что это, с натяжкой, эквивалентно объединению списков. У нас есть список, содержащий списки. Хорошо бы эти списки склеить.

В PHP есть функция call_user_func_array, которая принимает на вход два параметра: фукнцию, которую надо вызывать и массив её параметров. В PHP я бы склеил эти списки вот так: call_user_func_array(’array_merge’, $letter). В Python делается всё то же самое, только синтаксис этого вызова другой: func(*args). Это означает, что когда будет вызвана функция func, список args станет списком её аргументов, chain принимает на вход любое количество элементов.

Таким образом мы получим вызов chain(*[ [’’], [’1’, ’1’], [’’, ’’], [’3’], [’’], [’5’], [’’] ]), что эквивалентно chain([’’], [’1’, ’1’], [’’, ’’], [’3’], [’’], [’5’], [’’]). На выходе мы получим следующий итератор, который как список выглядит вот так: [’’, ’1’, ’1’, ’’, ’’, ’3’, ’’, ’5’, ’’].

Легко заметить, что какое бы количество пробельных строк не было по краям, в конце всегда остаётся по одной. От них нам нужно избавиться. Делается это просто, в Python есть срезы, которыми я и пользуюсь: список[1: -1] означает «вернуть список с первого элемента, убрав ещё один с конца». В PHP это будет array_slice($list, 1, -1).

В итоге [’’, ’1’, ’1’, ’’, ’’, ’3’, ’’, ’5’, ’’][1:-1] даст нам искомое: [’1’, ’1’, ’’, ’’, ’3’, ’’, ’5’].

Мда. Что-то как-то не очень всё просто получилось :)

13 комментариев
jimidini (jimidini.ya.ru) 2008

tuple по-русски называется «кортеж»

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

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

Да, я знаю ещё с Рапиры. Но слово мне решительно не нравится.

extremus.livejournal.com 2008

Спасибо за подробный разбор.

Owner (companyowner.myopenid.com) 2008

Мы сейчас в плотную работаем с C# 3.0 в котором добавили lambda и expression trees. Читабельность куда выше будет:

            string[] t = {»», «1», «2», «3», ««, «„, „„, „„, „4“, „„, „„};

            var z = from a in
                        (from a1 in t.Skip(1).Take(4) select a1)
                    select a;

            z = z.Union(
                    from a in
                        (from a1 in t.Skip(8).Take(1) select a1)
                    select a
            );

z = 1,2,3, „„, 4

Кстати, надо пополнение для 99 бутылок на LINQ организовать. :)

Owner (companyowner.myopenid.com) 2008

А во ещё, тот же Distinct делается достаточно элементарно:
            var zz = (from z in new[]{»», «1», «2», «3», ««, «„, „„, „„, „4“, „„, „„} select z)
                .Distinct();

Результат:

zz — 1, 2, 3, 4, „“

Alisey (alisey.myopenid.com) 2008

Не понял всего конвейера. «...длиной более двух надо заменить на одну пустую строку», но потом в примере последовательности из двух тоже заменяются. Если в конце списка нет пустого элемента, это корректно обработается?

И ещё вы не написали почему бы не использовать простой цикл. inject неплохой кандидат:

p [’’, ’’, ’b’, ’o’, ’’, ’l’, ’’, ’’, ’k’, ’’].

push(’’).inject([’’]) {|necklace, pearl|
  necklace << pearl unless pearl == ’’ and necklace.last == ’’
  necklace
}[1..-2]

Alisey (alisey.myopenid.com) 2008

Комментарий для alisey.myopenid.com:

Если в конце списка нет пустого элемента, это корректно обработается?

  • Да, Alisey, корректно.
  • Но я не могу понять где это в коде
astur (astur.net.ru) 2008

Сразу стало интересно твоё отношение к третьему и седьмому пунктам «Дао Пайтона»: «Простое лучше сложного» и «Удобочитаемость важна»....

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

Комментарий для companyowner.myopenid.com:

Интересно, да.

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

Комментарий для alisey.myopenid.com:

Это что был за язык?

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

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

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

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

Alisey (alisey.myopenid.com) 2008

Комментарий для Евгения Степанищева:

Это был язык Руби. Inject — так в Руби называется fold. Это тоже итератор. Вы делаете минимум два прохода: группировку, и после её окончания фильтрацию. Так конечно универсально, для группировки можно использовать сложную функцию. Но как это может быть быстрее одного прохода фильтрации — мне непонятно.

С помощью генераторов правда можно красиво итерировать бесконечные последовательности, и скармливать элементы дальше по одному. Но мне интересно чем конкретно для вашего случая плох цикл или fold.

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

Комментарий для alisey.myopenid.com:

там не делается два прохода. Делается один. В этом смысл итераторов.