practice_1.1

Практическая работа №1 "Массивы и бинарный поиск"

Реализуйте модуль для языка программирования Python для работы с массивами.

Предусмотрите следующие возможности модуля:

• создание динамических массивов для чисел разных типов(целые (long), числа с плавающей точкой (double));
• создание пустого массива;
• создание массива, заполненного заранее заданными данными;
• реализуйте следующие функции для работы с массивом:
  • добавление элемента в конец массива (append);
  • вставка элемента в нужную позицию (insert);
  • удаление первого вхождения элемента в массив (remove);
  • удаление первого вхождения элемента в массив с возвратом (pop);
  • инвертирование массива (__reversed__ для поддержки функции reversed);
  • определение длины массива (поддержка функции len);
  • определение количества памяти, занимаемой массивом (sys.getsizeof, __sizeof__);
  • сравнение со стандартным массивом из модуля array или списком (__eq__);
• возможность итерирования по массиву;
• алгоритм бинарного поиска, возвращающий индекс найденного элемента или None если ничего не найдено

Не забудьте предусмотреть функцию изменения размера, которая будет работать "под капотом".

Для большей справки можно обратиться к документации модуля array стандартной библиотеки Python.

Требования к реализации

Модуль dynamic_array необходимо реализовать как Си расширение для Python. Это можно выполнить с помощью Cython - специальной надстройки для Python, позволяющей вызывать функции из Си напрямую, а также обладающей приближенным к Python синтаксисом. Документацию по Cython см. в полезных материалах. Также можно сразу реализовать этот модуль на языке Си и подключить его к Python с помощью Cython.

Обратите внимание, что при реализации на Cython или Си обертка на Python вокруг массива не нужна. Здесь dynamic_array содержит обертку только для тестов.

Метод инициализации класса Array должен принимать два аргумента:

• код типа в виде строки, 'd' для чисел с плавающей точкой и 'i' для целых чисел;
• набор инициализирующих данных, которые сразу будут занесены в массив.

Интерфейс методов и функций должен быть аналогичен методам модуля array стандартной библиотеки Python.

Модуль binary_search, содержащий реализацию бинарного поиска разрешается реализовать на Python. Этот модуль должен поддерживать работу с объектами из dynamic_array.

search(array: Iterable, item: Any=False) -> Optional[int]:

В файлах dynamic_array.py и binary_search.py размещены упрощенные шаблоны классов и функций. В Файлах test_dynamic_array.py и test_binary_search.py размещены тесты для проверки решения. Тесты можно запустить с помощью модуля unittest или pylint.

В файле my_array.pyx приведен пример реализации расширения для Python на Cython. Для компиляции этого модуля необходимо создать файл setup.py пример которого можно найти в текущей директории. Затем достаточно выполнить команду:

python setup.py build_ext --inplace

По завершении выполнения компиляции и при отсутствии ошибок появятся файлы:

• my_array.c
• my_array.cp39-win_amd64.pyd
• а также директория build

В файле my_array.cp39-win_amd64.pyd будет содержаться скомпилированный модуль, его можно использовать как обычный модуль Python. Для удобства его можно переименовать в my_array.pyd.

Для прохождения тестов вам понадобиться pytest и плагин pytest-timeout. Установить их можно командами:

python -m pip install pytest
python -m pip install pytest-timeout

Также нужен файл conftest.py расположите его рядом с тестами. Подробнее об этом файле можно узнать в документации.

Запустить тесты можно командой:

pytest test_dynamic_array.py -s

Входные и выходные данные

Пример входных данных для бинарного поиска:

Исходный список: [-3, 0, 2, 5, 5], 0
Результат: 1

Исходный список: [-3, 0, 2, 5, 5], 5
Результат: 3

Исходный список: [-3, 0, 2, 5, 5], 10
Результат: None

Методика оценивания

Оценка выставляется в соответствии со следующими требованиями:

1. Общие требования:
   • код работы проходит проверку утилитой pylint с конфигурационным файлом .pylintrc.
   • код работы успешно проходит тесты, если таковые имеются.
   • наличие документации к модулям, функциям, классам и методам.
   • наличие аннотации типов.
2. На оценку 3 балла:
   • реализовать методы append, insert, remove, __eq__.
3. На оценку 4 балла:
   • дополнительно реализовать методы pop, reverse.
4. На оценку 5 балла:
   • реализовать все методы, указанные в описании к работе.

Полезные материалы

• Cython tutorial
• Memory Allocation in Cython
• Использование Cython для ускорения вычислений в Python
• Cython. A Guide for Python Programmers
• Python __reverse__ magic method
• Binary Search in Java