С. В. Вабищевич инженерпрограммист компании ооо ск хайникс мемори солюшнс Восточная Европа
 Скачать 1.28 Mb.
|
|
getitem__ передан список или ndarray, то исполь- зуется «продвинутая» индексация: она создает копию массива с ука- занными элементами. >>> x = numpy.arange(4) >>> x[[1, 3]] == x[[False, True, False, True]] Список, переданный в качестве индекса, может содержать как индексы, так и массив bool, означающий, какие элементы нужно взять. Замечание. Массив bool может иметь длину меньше, чем дли- на исходного массива. Если длина больше и есть True за пределами массива, будет исключение. УНИВЕРСАЛЬНЫЕ ФУНКЦИИ В numpy реализовано множество функций по работе с дан- ными – сложение, умножение, вычисление синуса и т. п. Все опера- ции над массивами выполняются поэлементно. >>> x, y = numpy.arange(3), numpy.linspace(2, 3, num=3, endpoint=True) >>> x + y == numpy.array([2, 3.5, 5]) >>> numpy.max(x) == x.max() # 2 Универсальные функции (ufunc) выполняются с учетом распо- ложения данных. Во время прохода также используется буфериза- ция. Поэтому они работают быстрее Python built- in. На небольших данных ufunc работают медленнее ввиду необходимости настройки. ТИПЫ И ЗАПИСИ В numpy используется своя система типов, в частности, numpy.bool отличается от Python built- in bool. В массивах помимо скалярных типов можно хранить произволь- ные типы dtype, по сути, C-структуры, содержащие некоторые ска- лярные типы. >>> dt = np.dtype([(‘name’, np.str_, 16), (‘grades’, np.float64, (2,))]) >>> dt = np.dtype({‘names’: [‘r’,’g’,’b’,’a’], ‘formats’: [uint8, uint8, uint8, uint8]}) 102 В dtypes указаны имена – массивы с такими типами будут яв- ляться записями (numpy.recarray), так что к столбцам можно будет обращаться по имени. ВОЗМОЖНОСТИ NUMPY В Numpy есть поддержка массивов с пропусками – MaskedArray. Значения в таких массивах могут быть numpy. ma.masked. >>> x = numpy.array([1, 2, 3, –1, 5]) >>> mx = numpy.ma.masked_array(x, mask=[0, 0, 0, 1, 0]) >>> mx.mean() # 2.75 Такие значения обрабатываются функциями и не влияют на ре- зультат. Работа с произвольными Python- функциями может быть органи- зована с помощью следующих вспомогательных методов: – apply_along_axis (apply_over_axes) – применяет функцию вдоль оси (осей); – vectorize – обобщенный класс функций (можно использовать как декоратор, реализован как for); – frompyfunc – позволяет создать ufunc из обычной функции. Также в numpy реализована работа – с матрицами (Matrix); – со случайными величинами (random); – со статистическими функциями; – допустима стыковка массивов. 4.2. ПРОЧИЕ МАТЕМАТИЧЕСКИЕ БИБЛИОТЕКИ SCIPY В то время как Numpy реализует определенные типы дан- ных и базовые операции, SciPy 1 реализует множество вспомогатель- ных функций: – Clustering – реализация kmeans и пр.; – Constants – множество констант, математических и физических; 1 https ://docs.scipy.org/doc/scipy/reference/ 103 – FFTPack – функции, выполняющие дискретное преобразова- ние Фурье; – Integrate – интегрирование (квадратурные формулы, с фикси- рованной сеткой) и дифференцирование (Рунге- Кутта и пр.); – IO – работа с форматами данных, в том числе MatLab; – Linalg – линейная алгебра (решение СЛАУ, разложение матриц, нахождение собственных значений, матричные функции, специаль- ные виды матриц и пр.); – NDImage – функции по работе с изображениями (свертки, аф- финные преобразования и т. п.); – ODR – orthogonal distance regression; – Optimize – оптимизация (методы первого и второго порядка, метод Ньютона, BGFS, Conjugate Gradient и пр., поиск корней, МНК); – Signal – методы обработки сигналов (звука – свертки, сплай- ны, фильтры); – Sparse и Sparse.Linalg – разреженные матрицы и методы по ра- боте с ними; – CSGraph – методы по работе со сжатыми разреженными графа- ми (в том числе алгоритмы Дейкстры, BFS, DFS и т. п.); – Spatial – работа с точками на плоскости (KDTree и пр.); – Stats и Stats.Mstats – работа с распределениями и статистиками. MATPLOTLIB, SEABORN, SYMPY, PANDAS Для отображения данных используются библиотеки MatplotLib и Seaborn. Поскольку библиотеки довольно обширные, при работе с данными библиотеками рекомендуется активно поль- зоваться пособием для разработчиков: MPL tutorials 1 (или reference) 2 или SBS tutorials 3 (или API) 4 . Далее следует найти нужный пример и модифицировать его для своих целей. Библиотека Sympy 5 позволяет производить символьные вычис- ления, а Pandas 6 – работать с данными (более удобная обертка над NumPy, ориентированная на группировку/преобразование данных и статистики). 1 https ://matplotlib.org/tutorials/index.html 2 https ://matplotlib.org/contents.html 3 https ://seaborn.pydata.org/tutorial.html 4 https ://seaborn.pydata.org/api.html 5 http ://docs.sympy.org/latest/index.html 6 http ://pandas.pydata.org/pandas‑ docs/stable/ 104 Также полезным будет ознакомиться с дополнительными при- мерами использования данных библиотек (https://github.com/ jrjohansson/scientific- python- lectures). 4.3. РАБОТА С WEB. GUI В стандартной библиотеке есть модули для работы с web: – socket 1 – работа с сокетами; – html.parsers; xml.etree 2 , xml.dom и xml.sax – html и xml парсеры; – urllib 3 – http- запросы. Кроме того есть множество библиотек (часто надстроек либо над стандартными модулями, либо над другими библиотеками), которые использовать гораздо удобнее. Для парсинга html и xml популярны библиотеки lxml 4 и BeautifulSoup 5 WEB- ЗАПРОСЫ И ПАРСИНГ Для выполнения запросов (например, get и post) исполь- зуют библиотеку requests 6 – реализованные в ней классы и менед- жеры контекста упрощают работу. Важно! При работе с запросами не забывайте про timeout, а так- же возможность повторить свой запрос несколько раз (retry). Для работы с базами данных используют SQLAlchemy 7 . В стан- дартной библиотеке также есть sqlite3 8 для работы с SQLite databases. Также существует множество web- фреймворков (для написания сайтов). Одни из самых популярных – Django 9 и Flask 10 . (Полный спи- сок здесь: https://wiki.python.org/moin/WebFrameworks/). Для генерации страниц (шаблонов) используют Jinja2 11 и genshi 12 1 https ://docs.python.org/3/library/socket.html 2 https ://docs.python.org/3/library/xml.etree.elementtree.html 3 https ://docs.python.org/3/library/urllib.html 4 https ://pypi.org/project/lxml/ 5 https ://pypi.org/project/beautifulsoup4/ 6 https ://pypi.org/project/requests/ 7 https ://pypi.org/project/SQLAlchemy/ 8 https ://docs.python.org/3/library/sqlite3.html 9 https ://www.djangoproject.com/ 10 https ://pypi.org/project/Flask/ 11 https ://pypi.org/project/Jinja2/ 12 https ://genshi.edgewall.org/ 105 GUI Для построения GUI на Python часто используют следую- щие библиотеки: – Tkinter (стандартная); – PyQt/PySide; – wxPython; – PyGTK; – pygame (в том числе для игр); – Kivy (в том числе для мобильных платформ; в качестве вве- дения можно ознакомиться со статьей: https://habr.com/company/ yandex/blog/354030/). Достаточно полный список библиотек для построения GUI: https:// wiki.python.org/moin/GUI Programming in Python и https://wiki.python. org/moin/GuiProgramming. ПРИМЕР ПРИЛОЖЕНИЯ НА KIVY Общее описание приложения на Kivy Рассмотрим пример написания простого приложения на Kivy, интерфейс которого представлен на рис. 9. Рис. 9. Интерфейс приложения Kivy Основное приложение разделено на две части: интерфейс, ко- торый описывается схемой, и основного кода приложения, содер- жащего обработчики. Пример описания интерфейса приложения # main.kv BoxLayout: 106 size: root.size pos: root.pos orientation: ’vertical’ Label: text: str(root.counter) font_size: 40 Button: text: “Увеличить счетчикˮ on_press: root.increase() font_size: 40 Пример кода приложения >>> # main.py >>> from kivy.app import App >>> from kivy.uix.widget import Widget >>> from kivy.properties import NumericProperty >>> class MainWindow(Widget): >>> counter = NumericProperty(0) >>> def increase(self): >>> self.counter += 1 >>> class MyApp(App): # (!) MyApp -> my.kv >>> def build(self): >>> return MainWindow() >>> MyApp().run() 4.4. ПОДРОБНОСТИ РЕАЛИЗАЦИИ И ПРОЧИЕ ВОЗМОЖНОСТИ ЯЗЫКА БАЙТ-КОД При загрузке модуля интерпретатор компилирует исход- ный код в байт-код – набор инструкций, за каждой из которых сто- ит обработчик – функция в интерпретаторе, которая ее выполняет. Для построения байткода интерпретатор строит абстрактное синтаксическое дерево. В стандартной библиотеке есть как модуль, позволяющий построить AST-дерево (ast-модуль) 1 , так и позволяю- 1 https ://docs.python.org/3/library/ast.html 107 щий просмотреть байт-код, который далее будет интерпретирован (dis-модуль) 1 Рассмотрим пример кода и соответствующий ему байт-код: 0 >>> import dis 1 >>> 2 >>> global_a = 0 3 >>> 4 >>> def f(closure_b): 5 >>> enclosing_c = 1 6 >>> 7 >>> def g(param_d): 8 >>> local_e = 2 9 >>> return (global_a + closure_b + enclosing_c + param_d + local_e) 10 >>> 11 >>> dis.dis(g) 12 >>> 13 >>> f(–1) Байт-код функции g, полученный с помощью модуля dis, выгля- дит следующим образом: 8 0 LOAD_CONST 1 (2) 3 STORE_FAST 1 (local_e) 9 6 LOAD_GLOBAL 0 (global_a) 9 LOAD_DEREF 0 (closure_b) 12 BINARY_ADD 13 LOAD_DEREF 1 (enclosing_c) 16 BINARY_ADD 17 LOAD_FAST 0 (param_d) 20 BINARY_ADD 21 LOAD_FAST 1 (local_e) 24 BINARY_ADD 25 RETURN_VALUE На примере этого кода видно, как различаются обращения к глобальным, локальным переменным и переменным из внеш- них функций (LOAD-команды). За присваивание значения отвечает STORE-команда, за сложение – BINARY_ADD, а за возврат значения из функции – команда RETURN. 1 https ://docs.python.org/3/library/dis.html 108 Подробнее о байт-коде можно почитать в этих двух статьях: https://pythoninternal.wordpress.com/2014/07/14/python- bytecode/ и https://habr.com/post/140356/ ИНТРОСПЕКЦИЯ Интерпретируемый язык позволяет легко создавать код «на лету», а также контролировать выполнение программы: прове- рить тип объекта, узнать сигнатуру функции, последний фрейм и все переменные в нем, стек вызовов. Для работы со стеком и фреймами в Python используется модуль sys 1 , для работы с объектами – модуль inspect 2 Замечание. В Python стек рекурсии ограничен (по умолчанию 1000, рекурсия может быть изменена). Оптимизация хвостовой ре- курсии отсутствует. В Python есть собственный интерактивный отладчик – pdb 3 (ча- сто используется многими IDE). GIL И GC В Python есть Global Interpreter Lock – механизм, кото- рый гарантирует одновременное выполнение только одного потока. Переключение GIL в последней версии Python происходит по тайме- ру. Подробности можно найти здесь (http://www.dabeaz.com/python/ UnderstandingGIL.pdf). Для всех объектов в Python ведется счетчик ссылок, а все объ- екты классифицируются в три поколения. После того как разница между количеством выделений памяти и количеством очисток па- мяти превысит некоторый порог threshold0, GC пытается объекты из нулевого поколения, для которых счетчик ссылок нулевой, пере- нести в первое. После некоторого количества threshold1 таких ите- раций происходит попытка переместить объекты из первого поко- ления во второе. GC также умеет разрешать циклические зависимости, если у объектов не переопределен метод __del__. Если же переопределен, то Python не разрешает такие зависимости автоматически, посколь- 1 https ://docs.python.org/3/library/sys.html 2 https ://docs.python.org/3.7/library/inspect.html 3 https ://docs.python.org/3/library/pdb.html 109 ку, вообще говоря, невозможно угадать безопасный порядок, в кото‑ ром следует вызывать методы __del__. Удалить такие объекты можно вручную, а посмотреть, какие объ‑ екты на какие ссылаются, можно с помощью методов gc.get_referrers и gc.get_referents. Избежать циклических зависимостей позволяют «слабые ссыл‑ ки» – weakref 1 (PEP‑205) 2 . Подробнее о GC: https://docs.python.org/3.7/ library/gc.html и https://pythoninternal.wordpress.com/2014/08/04/the‑ garbage‑ collector/ ПОТОКИ И ПРОЦЕССЫ В PYTHON Потоки в Python являются системными потоками, однако исполнение Python‑ кода невозможно одновременно несколькими потоками (это гарантируется GIL’ом). Потоки в Python полезны при выполнении операций ввода‑ вывода, а также при вызовах внешних библиотек. Для параллельно‑ го выполнения Python‑кода следует предусмотреть его выполнение в нескольких процессах. Для передачи данных между процессами они должны быть се‑ риализуемы. Подробнее про доступные примитивы и функции работы с про‑ цессами и потоками можно почитать в документации на эти модули: multiprocessing 3 , threading 4 , concurrent 5 , subprocess 6 , signal 7 СЕРИАЛИЗАЦИЯ ДАННЫХ Текст и простые объекты сериализуют в удобном для чте‑ ния формате, например json или yaml. Для передачи данных между процессами можно использовать модуль struct. Он позволяет упаковать C‑совместимые типы в один буфер. Стандартный механизм Python использует для сериализации 1 https://docs.python.org/3.7/library/weakref.html 2 https://www.python.org/dev/peps/pep‑0205 3 https://docs.python.org/3.7/library/multiprocessing.html 4 https://docs.python.org/3.7/library/threading.html 5 https://docs.python.org/3.7/library/concurrent.html 6 https://docs.python.org/3.7/library/subprocess.html 7 https://docs.python.org/3.7/library/signal.html 110 внутренний формат, процесс преобразования к которому поддержи- вается в модуле pickle 1 (для почти всех Python- объектов, кроме по- токов, lambda- функций, frame’ов и некоторых др.). Есть возможность использовать также сторонние библиоте- ки, которые сериализуют в том числе lambda- функции: bson 2 , dill 3 , protobuf 4 РАСШИРЕНИЕ ЯЗЫКА Поскольку официальный интерпретатор CPython напи- сан на C, то можно из Python напрямую взаимодействовать с C-ко- дом – реализовывать C/C++ extensions. Стандартный механизм взаимодействия описан в документации 5 , другие возможности – реализация расширений с помощью boost Python 6 и библиотеки Pybind11 7 РАЗВОРАЧИВАНИЕ ПРИЛОЖЕНИЙ Для создания переносимых приложений можно восполь- зоваться встроенными модулями, которые позволяют создать описа- ние приложения и указать все необходимые зависимости: setuptools 8 и distutils 9 НОВЫЕ ИНТЕРЕСНЫЕ ВОЗМОЖНОСТИ Новые изменения в Python 3.6: – улучшения в форматировании строк (PEP-498) 10 ; – поддержка подчеркиваний в числовых литералах (PEP-515) 11 1 https://docs.python.org/3.7/library/pickle.html 2 https://pypi.python.org/pypi/bson 3 https://pypi.python.org/pypi/dill 4 https://developers.google.com/protocol‑ buffers/docs/pythontutorial 5 https://docs.python.org/3.7/c‑ api/index.html 6 https://www.boost.org/doc/libs/1_55_0/libs/python/doc/ 7 https://github.com/pybind/pybind11 8 https://setuptools.readthedocs.io/en/latest/ 9 https://packaging.python.org/ 10 https://www.python.org/dev/peps/pep‑0498 11 https ://www.python.org/dev/peps/pep‑0515 Новые изменения в Python 3.7: – функции __ getattr__ и __dir__ у модуля (PEP-562) 1 ; – переменные контекста (PEP-567) 2 Недавно одобренные: – поддержка дженерик- типов (PEP-560) 3 ; – отложенное вычисление аннотаций (PEP-563) 4 1 https ://www.python.org/dev/peps/pep‑0562 2 https ://www.python.org/dev/peps/pep‑0567 3 https ://www.python.org/dev/peps/pep‑0560 4 https://www.python.org/dev/peps/pep‑0563 112 Глава 5 ЛАБОРАТОРНЫЕ РАБОТЫ Ниже приведены задания для закрепления знаний. На примере решения небольших задач отрабатывается пройденный на лекциях материал, а на примерах домашних заданий – написа- ние программ. 1. ОСНОВЫ ЯЗЫКА И БАЗОВЫЕ КОЛЛЕКЦИИ 1. Напишите программу, которая будет выводить через пробел все четные числа от 1 до 50, попутно заменяя числа, которые делятся на 3, на Fizz, делящиеся на 5 – на Buzz, а делящиеся и на 3, и на 5 – на FizzBuzz. 2. Напишите функцию, возвращающую число, битовое пред- ставление которого является k-тым членом последовательности Морса- Туэ 1 (последовательность OEIS № A010060). Значение пере- менной полагайте допустимым целым числом, большим либо рав- ным нулю. О быстрой скорости роста числа не беспокойтесь. Постарайтесь в решении обойтись без использования строк. Пример >>> assert get_sequence_item(0) == 0b0 >>> assert get_sequence_item(1) == 0b1 >>> assert get_sequence_item(2) == 0b110 >>> assert get_sequence_item(3) == 0b1101001 3. Билетик называется счастливым, если сумма первых трех цифр его номера равна сумме последних цифр. Напишите функцию, принимающую номер билета и возвраща- ющую номер ближайшего счастливого билета (если их два – то лю- бой из них). Номер переданного билета полагайте допустимым це- лым шестизначным числом (без нулей в начале). 1 https ://en.wikipedia.org/wiki/Thue‑ Morse_sequence Пример >>> assert get_nearest_lucky_ticket(111111) == 111111 >>> assert get_nearest_lucky_ticket(123322) == 123321 >>> assert get_nearest_lucky_ticket(123320) == 123321 4. Напишите функцию, подсчитывающую количество различных способов выдать со счета сумму от 0 до 50 копеек монетами по 1, 2, 5 и 10 копеек. 5. Напишите функцию, которая первым аргументом на вход при- нимает строку с цифрами некоторого целого числа. Второй аргумент функции – числа, вхождения которых нужно найти в переданной строке цифр, – является либо целым числом, либо кортежем целых чисел (если их несколько). Функция должна возвращать количество всех позиций, на кото- рых обнаружены вхождения, а также отсортированный список об- наруженных позиций. Если передан кортеж, то возвращать нужно суммарное количество вхождений, а также объединенный отсор- тированный список позиций найденных чисел. Если длина списка больше чем k, то возвращайте только первые k элементов. Пара- метр k – натуральное число, по умолчанию пять, –передается тре- тьим аргументом. Также реализуйте еще одну функцию, которая будет иметь ту же сигнатуру, что и предыдущая, но первый ее аргумент будет именем файла, из которого нужно считать число. Предполагается, что упо- мянутая выше функция будет переиспользована. Пример >>> assert index(‘123’, 1) == (1, [1]) >>> assert index(‘1212122222’, (1, 2, 12), 3) == (13, [1, 1, 2]) 114 2. COMPREHENSION- ВЫРАЖЕНИЯ И ДОПОЛНИТЕЛЬНЫЕ КОЛЛЕКЦИИ 1. Напишите функцию, которая принимает один аргу- мент n – натуральное число – и считает (возвращает) сумму 1 * 2 + + 2 * 3 + … +(n – 1) * n. Используйте comprehensions для решения за- дачи, желательно только одно. Пример >>> assert calculate_special_sum(3) == 8 2. Напишите функцию, которая принимает один аргумент – нату- ральное число – и возвращает все Пифагоровские тройки, т. е. трой- ки натуральных чисел (x, y, z), что x 2 + y 2 = z 2 и 1 ≤ x ≤ n, 1 ≤ y ≤ n, 1 ≤ z ≤ n. Тройкой называется кортеж из трех элементов. Используйте comprehensions для решения задачи, желательно только одно. Пример >>> expected_sorted = [(3, 4, 5), (4, 3, 5)] >>> actual_sorted = sorted(get_pythagoras_triples(5)) >>> assert expected_sorted == actual_sorted 3. Напишите функцию, которая принимает на вход последова- тельность (кортеж или список) и возвращает список пар из уни- кальных элементов и количества раз, сколько они встретились в пе- реданной последовательности. Парой называется кортеж из двух элементов. Порядок пар в списке не важен. Пример >>> expected_sorted = [(1, 2), (2, 1)] >>> actual_sorted = sorted(compress([1, 2, 1])) >>> assert expected_sorted == actual_sorted 4. Напишите функцию, которая для выборки, заданной списком, и заданного натурального числа k посчитает и выведет гистограм- му распределения шириной k. Другими словами, найдет максимум и минимум, поделит интервал на k частей (1 ≤ k ≤ d, d – количество различных элементов в списке) и посчитает, сколько элементов вы- борки попало в каждый интервал. Верните список длины k, содержащий количество элементов в каж дой ячейке. Левую границу интервалов считайте включая, пра- 115 вую – исключая (кроме последнего интервала). Желательно реали- зовать алгоритм со сложностью 0(n), где n – длина входного списка. Пример >>> assert distribute([1.3, 1, 2, 1.7], 2) == [2, 2] 5. Рассмотрим список, который содержит числа и другие списки, которые, в свою очередь, могут содержать другие числа и вложен- ные в них списки. Реализуйте функцию, которая будет разворачи- вать списки такого вида в один. Пример со списками >>> list_to_test = [1, 3, [1, [[], 2]], 3, []] >>> expected = [1, 3, 1, 2, 3] >>> actual = flatten_list(list_to_test) >>> assert expected == actual 6. Напишите функцию, которая принимает один аргумент n – на- туральное число – и возвращает все простые числа, не превосходя- щие n. Используйте comprehensions для решения задачи. Функция должна содержать лишь одно comprehension-выражение. 7. Реализуйте сортировку слиянием (merge sort, асимптотическая сложность алгоритма – 0(n log n). Программа должна корректно ра- ботать для списков (возвращать новый отсортированный список) и кортежей (возвращать кортеж). Использовать встроенные функ- ции сортировки и/или слияния запрещается. При решении предполагается также отсутствие итерирования по сортируемой коллекции с помощью индексов. Иначе говоря, ре- комендуется произвольной индексации избегать. 8. Существует исследование, говорящее о том, что в словах текста можно произвольно переставить буквы (не затрагивая первую и по- следнюю), и от этого читабельность текста практически не ухудшит- ся. Напишите программу для проверки этого факта. Ваша программа должна получать на вход какой-нибудь текст и переставлять буквы в его словах случайным образом (см. модуль random, постарайтесь выбрать самый подходящий метод). Также у программы должен быть режим, в котором буквы (кроме первой и последней) переставляются не случайным образом, а сор- тируются по алфавиту. Сравните результаты (для себя). Функция должна принимать на вход текст (одна строка, возмож- но с переносами строк внутри) и параметр, обозначающий, нужно ли использовать случайную перестановку или нет. Используйте ArgParser для передачи строки и указания режима. Предусмотрите возможность передачи пути к файлу. Название пара- метров и их вид выберите произвольно (будет проверяться вручную). Утилиту постарайтесь реализовать одновременно как скрипт и как модуль, т. е. чтобы была возможность запускать ее как скрипт с удобным интерфейсом командной строки, а также возможность подключать (импортировать) ее как внешний модуль. Также постарайтесь организовать корректно работу с кирилли- цей. Словами считайте последовательность букв, цифр и дефис '-'. Ис- пользование регулярных выражений поощряется (модуль re 1 , изучи- те самостоятельно). Если не будете использовать их, то разделителя- ми считайте только переносы строк и пробелы. 9. Напишите функцию, которая при каждом вызове возвращает количество раз, которое она была вызвана. Использовать глобаль- ные переменные не допускается, иначе говоря, в файле должны быть только определение функции (с ключевым словом def). Пример >>> for real_call_count in range(1, 5): >>> assert f() == real_call_count 1 https://docs.python.org/3/library/re.html 117 3. КЛАССЫ И МЕТОДЫ 1. Реализуйте класс MidSkipQueue, представляющий со- бой очередь, в которой хранятся только первые k и последние k добав- ленных элементов. В очереди должно быть реализовано следующее: – конструктор, принимающий первым аргументом параметр k (проверьте, что он имеет допустимое значение), а вторым опцио- нальным аргументом – iterable элементов, на основе которых нуж- но построить очередь; – метод, преобразующий очередь в строку (переопределите «ма- гический» метод __str__ и используйте модуль pprint); – оператор, позволяющий сравнивать на равенство две очереди; – «магический» метод, возвращающий длину очереди; – «магический» метод, позволяющий обратиться к элементу по индексу (используйте assert для проверки корректности индек- са) либо взять слайс элементов; – метод index, возвращающий индекс элемента в очереди или минус один, если такого элемента нет; – «магический» метод, позволяющий проверить, содержится ли некоторый элемент в очереди; – метод append, который в качестве аргумента принимает один и более (переменное число) объектов и добавляет все элементы в очередь; – оператор сложения с iterable элементов. Обратите внимание, что удаление из очереди реализовывать не требуется. От этого класса унаследуйте класс MidSkipPriorityQueue, в кото- ром при добавлении элементов в очередь будет учитываться их зна- чение так, что будут храниться не более k наименьших и k наиболь- ших добавленных элементов. В начале очереди храните наименьший элемент. Предполагайте, что добавляемые элементы реализуют все необходимые операторы сравнения. Пример MidSkipQueue >>> q = MidSkipQueue(1) >>> q.append(–1) # q: [–1] >>> q += (–2, –3) # q: [–1, –3] – the first and the last remain >>> q.append(4) # q: [–1, 4] – the last item has been replaced 118 Пример MidSkipPriorityQueue >>> q = MidSkipPriorityQueue(1) >>> q.append(–1) # q: [–1] >>> q += (–2, –3) # q: [–3, –1] – the smallest and the largest items >>> q.append(4) # q: [–3, 4] – the largest item is replaced >>> q.append(–5) # q: [–5, 4] – the smallest item is replaced 2. Реализуйте класс DependencyHelper, позволяющий эффек- тивно проверить наличие циклических зависимостей. Реализуйте следующие методы: – метод add, принимающий на вход два параметра – пару зави- симых объектов, где второй зависит от первого; – оператор сложения с кортежем (парой) зависимых элементов; – метод remove и соответствующий ему оператор вычитания; – метод копирования copy, возвращающий точную независимую копию данного объекта; – метод get_dependent, принимающий в качестве аргумента не- который элемент и возвращающий последовательность непосред- ственно зависимых от него элементов; – метод has_dependencies, проверяющий наличие циклической зависимости между объектами; – оператор преобразования к bool, возвращающий True, если зависимостей нет. Все добавляемые объекты предполагаются хешируемыми. Ис- пользовать готовые алгоритмы не допускается. Пример >>> dependency_helper = DependencyHelper() >>> dependency_helper.add(1, 2) >>> dependency_helper += (2, 1) >>> assert not dependency_helper # helper must find out dependend items >>> >>> dependency_helper.add(2, 3) >>> dependency_helper.remove(2, 1) >>> assert dependency_helper # no dependend items От класса DependencyHelper унаследуйте класс PriorityHelper. В нем реализуйте метод enumerate_priorities, возвращающий сло- варь, содержащий пары объектов и их приоритетов. Приоритеты должны быть расставлены так, что объекты с боль- шим приоритетом зависят от объектов с меньшим приоритетом. Значения приоритетов могут совпадать. Количество различных при- оритетов постарайтесь сделать минимальным и выбирать их после- довательно, начиная с нуля. Использовать готовые алгоритмы не до- пускается. Пример Пусть a ← b (b зависит от a), a ← c, d ← c, e ни от чего не зависит. Тогда оптимальная расстановка приоритетов такова: a, d и e имеют приоритет 0; b и c – приоритет 1. 120 4. ДЕКОРАТОРЫ И ИТЕРАТОРЫ 1. Реализуйте декоратор memorize, который будет сохра- нять результат выполнения некоторой функции и возвращать его, если функция была опять вызвана с этими же параметрами. Предпо- лагайте, что значения всех параметров хешируемы. Предполагайте также, что количество комбинаций различных значений аргументов разумно и не приведет к ошибкам выделения памяти. Для простоты случаи передачи параметров как позиционных ар- гументов и по ключевым словам считать различными. Также считать различными вызовы, когда функция вызвана без указания параме- тра, у которого есть значение по умолчанию, и когда она вызвана, а значение этого параметра равно значению по умолчанию. В Python 3.x есть декоратор functools.lru_cache. Использовать его для решения задания не разрешается. Усложненный вариант. Изучите модуль inspect. Реализуйте кор- ректную работу декоратора без учета предыдущего замечания, при- нимая во внимание полную сигнатуру функции. 2. Реализуйте декоратор profile, который при вызове функ- ции подсчитывает время выполнения этой функции, выводит его на экран и возвращает результат вызова функции. Рассмотрите стан- дартный модуль timeit и, в частности, функцию default_timer для измерения времени выполнения. 3. Реализуйте функцию scalar_product, которая считает скаляр- ное произведение двух iterable. Элементы могут иметь тип int или float, а также быть строками. Строки могут быть либо представлением целых чисел (в том числе в двоичной или шестнадцатиричной системе счисления – исполь- зуйте встроенную функцию int), либо состоять из букв. Обработайте этот случай с помощью исключений, результатом вычисления в та- ком случае считайте None. Воспользуйтесь функциями из модуля itertools и built- in- функциями. Использовать циклы не разрешается. Пример >>> expected = 1 >>> actual = scalar_product([1, ‘2’], [–1, 1]) >>> assert expected == actual >>> actual = scalar_product([1, ‘abc’], [–1, 1]) >>> assert actual is None 121 4. Реализуйте генератор unique, принимающий в качестве аргу- мента некоторый iterable и возвращающий последовательно из него только уникальные элементы в том порядке, в котором они встре- тились. Пример >>> expected = [1, 2, 3] >>> actual = unique([1, 2, 1, 3, 2]) >>> assert expected == list(actual) 5. Реализуйте функцию reverse_list, которая возвращает одно- связный список в обратном порядке. Предполагайте, что узел од- носвязного списка имеет тип Node. Пример >>> class Node(object): >>> def __init__(self, value, next_item=None): >>> self.value = value >>> self.next_item = next_item >>> >>> source = Node(3, Node(7, Node(9))) >>> expected = Node(9, Node(7, Node(3))) >>> assert expected == reverse_list(source) 6. Реализуйте функцию flatten_list, которая разворачивает одно- связный список с вложенными элементами в один односвязный спи- сок. Предполагайте, что узел односвязного списка имеет тип Node. Пример >>> class Node(object): >>> def __init__(self, value, next_item=None): >>> self.value = value >>> self.next_item = next_item >>> >>> # 3 -> (7 -> 9) -> 5 >>> source = Node(3, Node(Node(7, Node(9)), Node(5))) >>> # 3 -> 7 -> 9 -> 5 >>> expected = Node(3, Node(7, Node(9, Node(5)))) >>> assert expected == flatten_list(source) 7. Реализуйте функцию transpose, которая транспонирует iterable вложенных iterable. Предполагайте, что количество элементов во всех вложенных iterable одинаково. Другими словами, транспо- нирует прямоугольный двухмерный массив. Воспользуйтесь функциями из модуля itertools и built- in- функциями. Использовать циклы не разрешается. Пример >>> expected = [[1, 2], [–1, 3]] >>> actual = transpose([[1, –1], [2, 3]]) >>> assert expected == list(map(list, actual)) 123 5. КОНТЕКСТНЫЕ МЕНЕДЖЕРЫ И МЕТАКЛАССЫ 1. Реализуйте декоратор handle_error и контекстный ме- неджер – назовите его handle_error_context, – которые позволяют обрабатывать ошибки в зависимости от переданных параметров: – re_raise – флаг, отвечающий за то, будет произведен проброс исключения (типы исключений для обработки заданы параметром exc_type – см. ниже) из блока/функции на уровень выше или нет (по умолчанию True); – log_traceback – флаг, отвечающий за то, будет ли при возник- новении исключения типа exc_type отображен traceback (по умол- чанию True); – exc_type – параметр, принимающий либо отдельный тип, либо непустой кортеж типов исключений, которые должны быть обрабо- таны (для всех остальных блока except не будет) – значение по умол- чанию выставьте тип Exception. Для обработки и логирования traceback используйте функцию sys.exc_info() и схожие ей, модуль traceback, а логирование осущест- вляйте с помощью глобального для модуля объекта logger – Logger’а из стандартной библиотеки (модуль logging). Обратите внимание, что при реализации декоратора и менедже- ра контекста код должен быть переиспользован – простого копиро- вания требуется избежать. Пример 1 >>> # log traceback, re- raise exception >>> with handle_error_context(log_traceback=True, exc_type=ValueError): >>> raise ValueError() Пример 2 >>> # suppress exception, log traceback >>> @handle_error(re_raise=False) >>> def some_function(): >>> x = 1 / 0 # ZeroDivisionError >>> >>> some_function() >>> print(1) # line will be executed as exception is suppressed 124 Пример 3 >>> # re- raise exception and doesn’t log traceback as exc_type doesn’t match >>> @handle_error(re_raise=False, exc_type=KeyError) >>> def some_function(): >>> x = 1 / 0 # ZeroDivisionError >>> >>> some_function() >>> print(1) # line won’t be executed as exception is re - raised 2. Реализуйте метакласс BoundedMeta, который контролиру- ет количество созданных объектов, классы которых имеют данный метакласс. Допустимое количество объектов задайте параметром (по умолчанию один). В случае превышения бросайте исключение TypeError. Eсли зна- чение параметра равно None, то ограничений нет. Другими словами, у класса C с метаклассом BoundedMeta долж- но быть создано не более двух экземпляров. Заготовка метакласса BoundedMeta >>> class C(metaclass=BoundedMeta, max_instance_count=2): >>> pass >>> >>> c1 = C() >>> c2 = C() >>> >>> try: >>> c3 = C() >>> except TypeError: >>> print(‘everything works fine!’) >>> else: >>> print(‘something goes wrong!’) 3. Реализуйте класс BoundedBase, в котором определен абстракт- ный classmethod get_max_instance_count, возвращающий максималь- ное количество экземпляров, которые можно создать. Не допускайте создания объекта, если данное значение превы- шено – бросайте исключение TypeError. Значение, равное None – без ограничений. Заготовка класса BoundedBase >>> class D(BoundedBase): >>> @classmethod >>> def get_max_instance_count(cls): >>> return 1 >>> >>> d1 = D() >>> >>> try: >>> d2 = D() >>> except TypeError: >>> print(‘everything works fine!’) >>> else: >>> print(‘something goes wrong!’) 126 ДОМАШНИЕ ЗАДАНИЯ ОСНОВЫ ЯЗЫКА Игра «Жизнь» Напишите программу, моделирующую экологическую си- стему океана, в котором обитают хищники и жертвы (добыча). Океан представляется двухмерным массивом ячеек. В ячейке может нахо- диться или хищник, или добыча, или препятствие. В каждый квант времени ячейки последовательно обрабатываются. Хищник может съесть соседнюю добычу или просто переместиться на свободную клетку. Добыча также может переместиться на свободную клетку. Если в течение определенного времени хищник ничего не съел, то он погибает. Через определенные интервалы времени добыча и хищни- ки размножаются (если рядом есть свободная клетка). При этом по- томок занимает эту свободную клетку. Начальные параметры задаются в файле. Моделирование закан- чивается либо когда пройдет определенное число итераций, либо когда погибнут все хищники или вся добыча. Карта океана (положение всех объектов) должна задаваться так- же в файле. Предусмотрите возможность сгенерировать карту океа- на случайным образом (можно в дополнительном скрипте). При написании решения разрешено пользоваться только стан- дартной библиотекой. Старайтесь соблюдать code style, писать функ- ционально и не использовать глобальные переменные для хранения состояния. Использовать классы разрешено. Ради интереса понаблюдайте, как ведет себя популяция в зави- симости от начальных значений. Свои наблюдения можете описать в файле и прикрепить к решенной задаче. Программа должна находиться в файле model.py и принимать следующие аргументы командной строки: – «-i» – количество итераций; – «-c» – файл с общей конфигурацией (время жизни существ, пе- риоды размножения и т. д.). Формат можете выбрать произвольно, но рекомендуется использовать json. К решению приложите один файл с работающей конфигурацией; – «-o» – файл, в который записаны результаты (карта океана) мо- делирования. Формат может быть произвольным. Пример: model.py -i 100 -c config.json -o result.txt Напишите также юнит- тесты к программе и сохраните их в фай- ле model_ut.py. Тесты должны либо быть набором функций (с пре- фиксом test_), содержащими assert’ы и тестирующими поведение определенных функций внутри вашей программы, либо test case’а- ми, использующими библиотеку unittest. Интерпретатор Напишите код интерпретатора арифметических выраже- ний. Он должен поддерживать работу с операциями +, -, *, /, ** и скоб- ками (любой вложенности) для целых и дробных чисел. Числа мо- гут быть отрицательными. Унарный минус для скобок поддерживать не нужно. Функцией eval пользоваться нельзя. Приоритет операто- ров такой, как в Python. Деление целочисленным не является. На вход функции с названием interpret подается корректное арифметическое выражение, содержащее до 250 элементов, раз- деленных пробелами. Возможные элементы: +, -, *, /, **, (,), целые и дробные числа. Минус с отрицательными числами пишется слит- но. Функция должна возвращать результат вычисления выражения. Сама программа должна содержать указанную выше функцию и работать как интерпретатор, считывая в цикле строки с консоли и выводя результат на консоль. Пример >>> assert interpret(‘2 * (3 + 5)’) == 16 >>> assert interpret(1 + 2 * (1 + 2 * (1 + 2 * (– 1 + 2)))) == 15 128 ОБЪЕКТНО- ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ Менеджер событий Продумайте и реализуйте EventManager – менеджер со- бытий. Ваша задача – выработать универсальный способ выполне- ния некоторых действий (по сути, функций) при возникновении со- бытия. События. События будут возникать в произвольные моменты времени и индексироваться. Событие возникает при вызове метода notify у объекта класса EventManager. Метод, в свою очередь, при- сваивает событию следующий индекс (начиная с 0) и выполняет все зарегистрированные действия, которые удовлетворяют условиям. Действия. Все действия должны характеризоваться периодич- ностью вызова – вызываться либо на каждом k-том событии, либо на конкретных событиях (определенных индексах), либо на всех. Важным аспектом реализации здесь является оптимизация: не- обходимо обходить только те действия, которые должны выполнить- ся при очередном возникновении события. Не следует каждый раз проверять, должно или нет выполняться определенное действие. Сбор и регистрация действий. За сбор действий, которые мо- гут быть выполнены при возникновении события, отвечает класс Collector. Он должен уметь пройти по всем модулям (в том числе вложенным) в некотором/некоторых папках (пакетах), определить, что может быть подписано, и сообщить обо всех собранных действи- ях EventManager’у. Способ определения действий, которые могут быть подписаны, определите сами, но помните, что реализации следует быть расши- ряемой и максимально независимой. Также EventManager должен поддерживать регистрацию и уда- ление определенных действий между событиями. Вызов действий. При возникновении события EventManager должен вызывать все зарегистрированные действия, удовлетворя- ющие условиям на текущий индекс события. Действия должны вызываться согласно некоторому приоритету. Систему приоритетов для действий, а также то, как они будут хра- ниться и выглядеть, продумайте сами. Реализуйте обработку исключений: по умолчанию, исключения при вызове действий должны быть обработаны – залогировано со- общение об ошибке, а исключение – подавлено. Предусмотрите воз- можность действиям быть критическими: исключения при выпол- нении таких действий должны быть залогированы и проброшены далее из EventManager’а. Особенности реализации. Реализация системы должна быть рас- ширяемой: проверьте, насколько легко добавить действия, которые выполняются каждые k событий, но не более m раз. Добавьте под- держку такого типа действий. Также реализация должна быть максимально эффективной: используйте генераторы и итераторы для обхода, не создавайте коллекций- результатов. Реализация должна быть направленной на обработку большого количества действий при достаточном ко- личестве событий, а вот регистрация и удаление действий будут вы- полняться нечасто. В отдельном файле (или нескольких) реализуйте юнит- тесты для вашего кода. Тестируйте только самые тонкие и сложные моменты – не увлекайтесь и не тратьте время на мелочи. Реализация, разумеется, должна быть написана в хорошем Python- стиле с выполнением всего пройденного ранее и учетом сде- ланных вам замечаний. СПИСОК ЛИТЕРАТУРЫ Лутц М. Изучаем Python // Символ- Плюс. 2011. Лутц М. Программирование на Python : в 2 т. // Символ- Плюс. 2011. Маккини У. Python и анализ данных // ДМК Пресс, 2015. Pilgrim M. Dive Into Python 3 // Apress, 2009. Python documentation [Electronic resource]. Mode of access: https:// docs.python.org/ |