chr(), ord() и re.sub()

Пример из жизни на применение регулярных выражений

Latex не собирает «левый» файл

Исходный текст файла bad_file.tex:

\documentclass{article}
\begin{document}
\U{417}\U{430}\U{434}\U{430}\U{447}\U{430}\U{2116}1.
\U{414}\U{430}\U{43d}\U{43e}:
...

pdflatex не отрисовывает русские буквы

как выглядит годный файл?

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsmath, amsfonts, amssymb, amsthm}

\begin{document}
Тут русский текст пишется в кодировке UTF-8.
\end{document}

как решить с помощью Питона?

Напишем скрипт, который заменяет каждую секцию вида \U{417} на букву с соответствующим кодом

Команда chr() возвращает символ по его номеру в юникоде

Команда ord() получает номер по символу

Команда re.sub(pattern, repl, string) заменяет вхождения регулярного выражения pattern в текст string. При этом repl может быть строкой «на что заменять» или функцией, которая вычисляет «на что заменять».

нужный скрипт

from sys import stdin, stdout
import re

def repl(match_obj):
    return chr(match_obj.groups()[0])

text = stdin.read()
text = re.sub(r'\\U{([0-9a-f]+)}', repl, text)

stdout.write(text)

вывод скрипта

\documentclass{article}
\begin{document}

Задачаȑ61.
Дано:
...

выходной ПДФ

менеджеры контекста

Удобный синтаксис для получения и освобождения ресурсов

пример записи в файл

f = open('hello.txt', 'w')
print('Hello, world!', file=f)
f.close()

более короткая форма

with open('hello.txt', 'w') as f:
    print('Hello, world!', file=f)

.close() вызовется автоматически при выходе из секции

это эквивалент try/finally

как это устроено?

файловый объект в Питоне является менеджером контекста, и его можно использовать с with

чтобы добавить в свой класс функциональность менеджера контекста, надо определить методы .__enter__() и .__exit__()

пример из проекта please

import os

class ChangeDir:
    def __init__(self, path):
        self.old_path = os.getcwd()
        self.where = path

    def __enter__(self):
        if self.where:
            os.chdir(self.where)
        return self

    def __exit__(self, type, value, traceback):
        os.chdir(self.old_path)

тупой пример использования класса ChangeDir

def list_files_flat(startpath):
    with ChangeDir(startpath):
        for root, dirs, files in os.walk('.'):
            for file in files:
                path = os.path.join(root, file)[2:]
                if path[0] != '.':
                    print(norm(path))
                    yield norm(path)

doctest

Простой и удобный способ писать тесты к коду вместе с документацией

документация кода в питоне

Если код класса или функции начинается со строки, то эта строка становится строкой документации и видна по вызову команды help()

пример: класс MultidimensionalFenwickTree.py

class MultidimensionalFenwickSumTree:
    '''Build a multidimensional table of elements (usually numbers), 
    providing item assignment and multidimensional range sum queries.
    '''

    def __init__(self, table):
    	...

указываем в doc-строке пример использования

class MultidimensionalFenwickSumTree:
    '''Build a multidimensional table of elements (usually numbers), 
    providing item assignment and multidimensional range sum queries.

    >>> mfst = MultidimensionalFenwickSumTree([[0, 1, 2, 3], 
    					[4, 5, 6, 7], [8, 9, 0, 1]])
    >>> mfst
    MultidimensionalFenwickSumTree([[0, 1, 2, 3], [4, 5, 6, 7], 
    					[8, 9, 0, 1]])
    >>> mfst[0:2][1:3].sum()
    14
    '''

    def __init__(self, table):
    	...

а теперь вызываем doctest.testmod()

Функция проходится по всем doc-строкам и тестирует код, который в них написан, на работоспособность.

if __name__ == '__main__':
    import doctest
    doctest.testmod()

«поломаем» наш код и посмотрим выдачу скрипта

$ ./MultidimensionalFenwickTree.py
**********************************************************************
File "./MultidimensionalFenwickTree.py", line 23, in __main__.MultidimensionalFenwickSumTree
Failed example:
    mfst[0:2][1:3].sum()
Expected:
    14
Got:
    0
**********************************************************************
1 items had failures:
   1 of   3 in __main__.MultidimensionalFenwickSumTree
***Test Failed*** 1 failure.

Показываются только тесты, которые завершились с ошибкой.

перегрузка индексации и взятия срезов

Синтаксические средства для создания удобных пользовательских контейнеров

возвращаемся к MultidimensionalFenwickTree.py

Хотим, чтобы можно было обращаться к элементам.

>>> mfst
MultidimensionalFenwickSumTree([[0, 1, 2, 3], 
                                [4, 5, 6, 7], 
                                [8, 9, 0, 1]])
>>> mfst[0:2][1:3].sum()
14
>>> mfst[2][1]
9
>>> mfst[2][1] = 8

всё делается перегрузкой операторов

За обращение по индексам отвечает метод .__getitem__()

За присваивание по индексам отвечате метод .__setitem__()

Переопределим их.

def __getitem__(self, index):
    return self.SliceView(self, ())[index]

def __setitem__(self, index, value):
    self.SliceView(self, ())[index] = value

взятие срезов

В параметр index методов .__getitem__() и .__setitem__() приходит либо число типа int, либо срез типа slice.

>>> class Foo:
...     def __getitem__(self, index):
...             print(index)
... 
>>> a = Foo()
>>> a[1]
1
>>> a[1:5]
slice(1, 5, None)
>>> a[1:5:-2]
slice(1, 5, -2)

Во внутреннем классе SliceView прописана разная логика.

class SliceView:
    '''Provide access to elements and subtables of a Fenwick tree.
    self.indices is maintained as a tuple of slice object with step == None
    and 0 <= indices[i].start < self.mfst.length[i],
        indices[i].start < indices[i].stop <= self.mfst.length[i].
    '''

    def __init__(self, mfst, indices, subscript=False):
        self.mfst = mfst
        self.indices = indices
        self.subscript = subscript or all([isinstance(i, int) for i in indices])

    def __fenwick_rec_update(self, indices, difference, level, subtable):
        k = indices[level].start
        while k < self.mfst.length[level]:
            if level + 1 == self.mfst.dim:
                subtable[k] += difference
            else:
                self.__fenwick_rec_update(indices, difference, level + 1, subtable[k])
            k = k | (k + 1)

    def __getitem__(self, index, value=None):
        level = len(self.indices)
        assert level < self.mfst.dim, 'too many levels of indices'

        if isinstance(index, int):
            if index < 0:
                index += self.mfst.length[level]
            index = slice(index, index + 1)
        else:
            self.subscript = False

        if (not 0 <= index.start < self.mfst.length[level] or 
            not index.start < index.stop <= self.mfst.length[level]):
            raise IndexError('index out of range')

        indices = self.indices + (index,)

        if (level + 1 == self.mfst.dim and self.subscript):
            tmp = self.mfst.table
            for i in indices[:-1]:
                tmp = tmp[i.start]
            if value is None:
                return tmp[indices[-1].start]
            else:
                difference = value - tmp[indices[-1].start]
                tmp[indices[-1].start] = value

                self.__fenwick_rec_update(indices, difference, 0, self.mfst.sum)
        else:
            if value is None:
                return type(self)(self.mfst, indices, self.subscript)
            else:
                if level + 1 == self.mfst.dim:
                    raise IndexError('cannot assign to a slice')
                else:
                    raise IndexError('not enough levels of indices')

    def __setitem__(self, index, value):
        self.__getitem__(index, value)

    def __rec_prefix_sum(self, res, indices, level, subtable):
        k = indices[level] - 1
        while k >= 0:
            if level + 1 == self.mfst.dim:
                res[0] += subtable[k]
            else:
                self.__rec_prefix_sum(res, indices, level + 1, subtable[k])
            k = (k & (k + 1)) - 1

    def prefix_sum(self, indices):
        res = [self.mfst.scalar_type()]
        self.__rec_prefix_sum(res, indices, 0, self.mfst.sum)
        return res[0]

    def __rec_sum(self, res, indices, parity, level):
        if level == self.mfst.dim:
            res[0] += parity * self.prefix_sum(indices)
        else:
            indices.append(self.indices[level].start)
            self.__rec_sum(res, indices, -parity, level + 1)
            indices.pop()
            indices.append(self.indices[level].stop)
            self.__rec_sum(res, indices, parity, level + 1)
            indices.pop()

    def sum(self):
        res = [self.mfst.scalar_type()]
        self.__rec_sum(res, [], 1, 0)
        return res[0]						
						

map, filter, zip, reduce, any, all

Средства функционального стиля программирования.

map и filter

Отвечают за преобразование последовательностей.

>>> from math import sqrt
>>> list(map(sqrt, [4, 16, 32, 64]))
[2.0, 4.0, 5.656854249492381, 8.0]
>>> from math import log
>>> list(map(lambda x: log(x, 2), [4, 16, 32, 64]))
[2.0, 4.0, 5.0, 6.0]
>>> list(filter(lambda x: x > 0, [1, -3, 4, -2, 5, 8]))
[1, 4, 5, 8]

map и filter: лучше не использовать

Всё то же самое можно достичь конструкцией list comprehension. При этом читабельность будет выше. И не нужен лишний каст к списку. И можно совместить обе операции.

>>> [sqrt(x) for x in [4, 16, 32, 64]]
[2.0, 4.0, 5.656854249492381, 8.0]
>>> [log(x, 2) for x in [4, 16, 32, 64]]
[2.0, 4.0, 5.0, 6.0]
>>> [x for x in [1, -3, 4, -2, 5, 8] if x > 0]
[1, 4, 5, 8]
>>> [sqrt(x) for x in [1, -3, 4, -2, 5, 8] if x > 0]
[1.0, 2.0, 2.23606797749979, 2.8284271247461903]

map: скалярное произведение

def dot_product(x, y):
    return sum(map(lambda a, b: a * b, x, y))

print(dot_product([1, 2], [3, 4]))

То же самое, но без написания своей функции:

import operator

def dot_product(x, y):
    return sum(map(operator.mul, x, y))

print(dot_product([1, 2], [3, 4]))

zip: перебор нескольких последовательностей

>>> for x, y in zip([2, 3, 5, 7], 'abcd'):
...     print(x, y)
... 
2 a
3 b
5 c
7 d

zip(*matrix): транспонирование

>>> a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
>>> list(zip(*a))
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]
>>> list(zip(*list(zip(*a))))
[(1, 2, 3), (4, 5, 6), (7, 8, 9)]

reduce: цепное вычисление

Пусть необходимо найти побитовый xor всех чисел массива.

import operator
from functools import reduce

reduce(operator.xor, [2, 9, 33])

any и all

any от последовательности равно True, если хотя бы один член последовательности эквивалентен True

all от последовательности равно True, если все члены последовательности эквивалентны True

Дана матрица из нулей и единиц. Проверить, что в каждом столбце есть хотя бы одна единица.

a = [[0, 1, 0],
     [1, 0, 0],
     [0, 1, 1]]
print(all(any(column) for column in zip(*rows)))

yield-генераторы, itertools

Средства для работы с бесконечными последовательностями.

хотим вернуть подотрезок таблицы символов

def str_seq(start, end):
...     return [chr(i) for i in range(ord(start), ord(end) + 1)]
... 
>>> str_seq('а', 'й')
['а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й']
>>> ''.join(str_seq('а', 'й'))
'абвгдежзий'

Проблема: под результат создаётся промежуточный список, хотя новые буквы последовательности можно вычислять «лениво».

однострочные генераторы вместо list comprehension

Конструкция (выражение for переменная in последовательность if условие) создает генератор.

def str_seq(start, end):
...     return (chr(i) for i in range(ord(start), ord(end) + 1))
... 
>>> str_seq('а', 'й')
<generator object <genexpr> at 0x7f5b7c034be0>
>>> ''.join(str_seq('а', 'й'))
'абвгдежзий'

При передаче генератора в функцию внешние круглые скобки можно опускать.

yield-генераторы

Синтаксис для более сложных генераторов: yield вместо return.

def str_seq(start, end):
    i = ord(start)
    while i <= ord(end):
        yield chr(i)
        i += 1

yield возвращает новое значение и приостанавливает работу генератора. Когда будет запрошено следующее значение генератора, работа продолжится со следующего за yield оператора.

что возвращают range, map, filter, zip?

Не списки, а объекты, по которым можно итерироваться.

>>> range(5)
range(0, 5)
>>> import operator
>>> map(operator.methodcaller('lower'), 'AbCDeF')
<map object at 0x7f0eafb4d850>

Плюсы:

• расходуется меньше дополнительной памяти
• map, filter и zip сразу умеют работать с бесконечными последовательностями

itertools.count

itertools.count([start]) — бесконечная последовательность натуральных чисел с некоторого места.

>>> import itertools
>>> names = ['Vasya', 'Petya', 'Kolya']
>>> for i, name in zip(itertools.count(1), names):
...     print(i, name)
... 
1 Vasya
2 Petya
3 Kolya

zip останавливается при достижении конца самой короткой последовательности. Противоположное поведение реализовано в itertools.zip_longest

enumerate

enumerate — сокращение для предыдущей конструкции.

>>> names = ['Vasya', 'Petya', 'Kolya']
>>> for i, name in enumerate(names, 1):
...     print(i, name)
... 
1 Vasya
2 Petya
3 Kolya

itertools.cycle

itertools.cycle — бесконечный циклический обход последовательности

На «первый-второй» рассчитайся!

>>> import itertools
>>> names = ['Guido', 'Larry', 'John', 'Bjarne']
>>> for i, name in zip(itertools.cycle([1, 2]), names):
...     print(i, name)
... 
1 Guido
2 Larry
1 John
2 Bjarne

itertools.islice: первые несколько элементов бесконечной последовательности

>>> def fib():
...     a, b = 1, 1
...     yield a
...     yield b
...     while True:
...             yield a + b
...             a, b = b, a + b
... 
>>> itertools.islice(fib(), 20)
<itertools.islice object at 0x7f0eb1503a48>
>>> list(itertools.islice(fib(), 10))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

map, filter и zip можно применять к бесконечным последовательностям

Это имеет свои последствия. Например, обычные списки или range-объекты могут возвращать несколько независимых итераторов по своему содержимому, а map не может.

>>> a = range(5)
>>> b = iter(a)
>>> c = iter(a)
>>> next(b)
0
>>> next(b)
1
>>> next(c)
0
>>> next(c)
1

map: единственность итератора

>>> a = map(operator.attrgetter('imag'), [1+2j, -1-3j, 2+4j])
>>> a
<map object at 0x7f0eaf452f50>
>>> b = iter(a)
>>> c = iter(a)
>>> next(b)
2.0
>>> next(c)
-3.0
>>> next(b)
4.0
>>> next(c)
Traceback (most recent call last):
  File "<stdin>", line 1, in 
StopIteration