Практикум: выбор решения под ограничения

Что делаем в этом модуле

На лекции разбирали, как найти ошибку: уточнить условие, подобрать тесты, пройти код вручную. Здесь ошибок нет. В архиве две задачи, и к каждой лежит файл с десятью решениями. Все десять дают правильный ответ, пока соблюдены их требования к входу — это проверяется запуском, и проверка приложена.

Тогда чем они отличаются? Временем, дополнительной памятью и тем, что каждое требует от входа: одно портит исходный список, другому нужен узкий диапазон значений, третьему — уже отсортированный вход. Какое решение подходит, зависит от ограничений задачи. А ограничений в условии не будет: их узнают вопросами, как на секции.

Порядок работы

1. Прочитайте условие задачи и запишите не меньше пяти вопросов, ответы на которые меняют выбор решения. Файл с вариантами пока не открывайте: вопросы задают до того, как увидели код.
2. Откройте файл задачи и заполните карту вариантов: время, дополнительная память, требования к входу. Всё это есть в докстроке каждой функции — читать нужно именно её, а не угадывать по названию.
3. Разберите заказы. Заказ — это набор ограничений: размер входа, диапазон значений, можно ли менять список, сколько памяти. Под каждый выберите один вариант и запишите, почему он, а не соседний по таблице.
4. Назовите варианты, которые не подошли ни одному заказу, и условия, при которых они были бы уместны. Таких в каждой задаче два-три.
5. Запустите проверку — она подтвердит, что дело не в правильности, а в ограничениях.
6. Сверьтесь с парой и разберите расхождения в выборе.

Работают парами: участник 1 берёт задачу A, участник 2 — задачу B. Через десять минут меняются задачами, ещё три минуты — на сверку выбора. Разбор на странице открывается через минуту после того, как блок появился на экране: это время на собственный ответ.

Задача A. k-й по величине элемент

Условие дают в таком виде, и больше в нём ничего нет:

«Верните k-й по величине элемент списка целых чисел».

Отсюда уже видно, чего не хватает: неизвестен размер списка, неизвестно, какие бывают значения, не сказано, считать ли повторы и можно ли менять исходный список. Каждый такой пробел меняет выбор варианта, поэтому с вопросов и начинают.

Теперь файл. В нём десять функций с одинаковой сигнатурой (numbers, k); ниже три из них, чтобы было видно, насколько они разные:

def v01_sort_kopii(numbers, k):
    """Сортировка копии по убыванию. O(n log n) времени, O(n) памяти."""
    return sorted(numbers, reverse=True)[k - 1]


def v04_kucha_iz_k(numbers, k):
    """Своя куча из k наибольших. O(n log k) времени, O(k) памяти.
    Подходит, когда весь список сразу в память не помещается."""
    heap = []
    for value in numbers:
        if len(heap) < k:
            heapq.heappush(heap, value)
        elif value > heap[0]:
            heapq.heapreplace(heap, value)
    return heap[0]


def v09_dve_peremennye(numbers, k):
    """Один проход с двумя переменными. O(n) времени, O(1) памяти.
    Работает только при k = 2: для другого k нужен другой код."""
    if k != 2:
        raise ValueError('вариант v09 написан только для k = 2')

Первый вариант не требует от входа ничего и тратит O(n) памяти на копию. Второй экономит память, но платит логарифмом от k на каждом элементе. Третий быстрее обоих и при этом бесполезен, если k не равно двум. Такую же строку нужно написать про каждый из десяти вариантов — в файле для этого есть докстроки.

Заказы

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

Задача B. Есть ли значение в списке

Вторая задача устроена так же: условие без ограничений и десять рабочих решений в файле zadacha_b_poisk.py.

«Отвечайте на запросы, есть ли число x в списке».

Здесь появляется ограничение, которого не было в задаче A: запросов может быть много. Один поиск и двести тысяч поисков по одному и тому же списку — разные задачи, хотя условие у них одно. Функция получает список и список запросов, а возвращает список ответов True/False.

def v03_set_zaranee(numbers, zaprosy):
    """Множество строится один раз до запросов.
    O(n + q) времени в среднем, O(n) памяти."""
    vidennye = set(numbers)
    return [x in vidennye for x in zaprosy]


def v08_set_kazhdyy_raz(numbers, zaprosy):
    """Множество строится внутри каждого запроса. Проверка быстрая,
    но построение стоит O(n), поэтому всего снова O(n * q)."""
    return [x in set(numbers) for x in zaprosy]

Эти две функции отличаются одним словом в строке, и обе используют set. Но первая строит множество один раз, а вторая — на каждый запрос, и вся выгода пропадает. Такие пары и есть то, ради чего читают код целиком, а не по названиям.

Заказы

Проверка запуском

Выбор варианта — это утверждение о цене, а не о правильности. Чтобы это было видно, в архиве лежит проверка: она прогоняет все варианты на общих входах и сверяет ответы с эталоном, а для вариантов с особыми требованиями проверяет ещё и эти требования. Запускают её из папки praktikum:

test_obshchiy_kontrakt (test_variantov.ZadachaA.test_obshchiy_kontrakt)
Восемь вариантов работают на любом допустимом входе. ... ok
test_v02_menyaet_vhod (test_variantov.ZadachaA.test_v02_menyaet_vhod)
v02 сортирует переданный список: это его цена за O(1) памяти. ... ok
test_v07_trebuet_neotricatelnyh (test_variantov.ZadachaA.test_v07_trebuet_neotricatelnyh)
v07 строит массив по значениям, поэтому отрицательные ему не подходят. ... ok
test_v09_tolko_k2 (test_variantov.ZadachaA.test_v09_tolko_k2)
v09 отвечает верно при k = 2 и отказывается при другом k. ... ok
test_v10_drugoy_kontrakt (test_variantov.ZadachaA.test_v10_drugoy_kontrakt)
v10 отвечает на другой вопрос: k-е различное значение. ... ok
test_obshchiy_kontrakt (test_variantov.ZadachaB.test_obshchiy_kontrakt)
Восемь вариантов работают на любом списке целых чисел. ... ok
test_v05_menyaet_vhod (test_variantov.ZadachaB.test_v05_menyaet_vhod)
v05 сортирует переданный список, v04 работает с копией. ... ok
test_v06_trebuet_neotricatelnyh (test_variantov.ZadachaB.test_v06_trebuet_neotricatelnyh)
v06 держит флаги по значениям: нужен непустой список от 0 до m. ... ok
test_v09_trebuet_sortirovki (test_variantov.ZadachaB.test_v09_trebuet_sortirovki)
v09 верен на отсортированном входе и ошибается на неотсортированном. ... ok

----------------------------------------------------------------------
Ran 9 tests in 0.001s

OK

Девять проверок проходят, и это ожидаемо: все варианты правильные. Два теста при этом фиксируют цену — что v02 и v05 меняют переданный список, — а ещё два показывают, где вариант откажется работать: отрицательные значения для счётчика и неотсортированный вход для двоичного поиска.

Если хочется увидеть разницу во времени своими числами, в архиве есть zamer.py: он берёт несколько вариантов, прогоняет их на списках разного размера и печатает медиану трёх запусков, как в теме 4. Своих чисел здесь не приводим — их печатает ваш компьютер.

Что сдать

Работа сдаётся одним бланком на пару. В нём должно быть заполнено:

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

Бланк есть в архиве в виде blank.md и в PDF для печати — там же напечатан код всех двадцати вариантов, чтобы заполнять карту можно было без экрана.

Готовую работу кладут в репозиторий в папку lesson_05: заполненный бланк, файл vybor.py с выбранными функциями и номером заказа в комментарии над каждой, и файл с выводом проверки.

Как оценивается

Всего 10 баллов. Баллы даются за то, что выбор объяснён ограничениями, а не за совпадение с ключом. Шкалу перевода в отметку задаёт преподаватель.