Границы окна
и неверный k

Категория

Код и тесты

Уровень

Средний

Опирается на

Главы 9.2–9.5; глава 8.6: разбор кода по строкам

Зачем это знать

Пройти review и тесты границ из контроля КТП

§1Разбор best_window по строкам

В главе 9.4 функция собрана из строк и пройдена по шагам. Здесь каждая строка разобрана отдельно: за что она отвечает и что получится, если записать её иначе. Под таблицей изменённые версии запущены.

def best_window(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    total = sum(nums[:k])
    best, start = total, 0
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]
        if total > best:
            best, start = total, r - k + 1
    return (start, best)

§2Запуск изменённых версий

Три изменения из таблицы, которые в главах 9.3 и 9.4 ещё не запускались. На каждой вкладке отличается одна строка, вход подобран так, чтобы изменение проявилось. Ошибочный ответ сопоставлен с верным.

Первые две вкладки показывают, почему проверку пишут первой строкой. Без неё функция на неверном входе возвращает правдоподобный ответ: (0, 0) и (0, 3) выглядят как обычные результаты.

§3Граничные входы всех функций

В модуле четыре функции. Три написаны по контракту курса и проверяют вход. max_vowels — решение LeetCode 1456, где условие гарантирует 1 ≤ k ≤ len(s), поэтому проверки в нём нет. Все значения в таблице получены запуском.

При k = 1 окно — один элемент: суммы окон совпадают со списком, лучшее окно — наибольший элемент. При k = n окно одно, цикл сдвигов не выполняется ни разу. Эти два значения k проверяют, что код верен и тогда, когда сдвигов максимальное число, и тогда, когда их нет совсем.

У max_events вместо k — длина окна по времени w. w = 0 и отрицательное w дают ValueError, пустой список — 0, а очень большое w допустимо: все события попадают в одно окно. На [1, 2] при w = 100 функция возвращает 2.

§4Почему исключение

На неверный k функция могла бы ответить по-разному: вернуть None, вернуть (0, 0) или бросить исключение. Интервьюер в главе 9.2 выбрал исключение. Причины видны в §2.

ValueError выбран потому, что тип аргумента верный — целое число, — а значение недопустимое. Так же поступает и стандартная библиотека: int("abc") бросает ValueError.

Проверку можно было бы записать через assert, но assert выключается при запуске Python с ключом -O. Тогда проверки нет совсем, и функция возвращает ответ на неверный вход:

$ cat a_test.py
def f(k):
    assert k >= 1, "k должно быть не меньше 1"
    return k
print(f(0))
$ python a_test.py
AssertionError: k должно быть не меньше 1
$ python -O a_test.py
0

Поэтому проверку входных данных пишут через if … raise, а assert оставляют для тестов и проверок, без которых программа может работать.

§5Тесты границ

Тесты ниже входят в tests.py стартового набора занятия 9. Тест неверного k запускается для двух функций и четырёх входов — восемь проверок одной функцией благодаря двум декораторам parametrize. Ожидание исключения записывается через pytest.raises: тест проходит, только если внутри блока with было брошено ValueError.

import pytest

from solution import best_window, max_events, window_sums

K_FUNCS = [window_sums, best_window]


@pytest.mark.parametrize("func", K_FUNCS)
@pytest.mark.parametrize("nums, k", [([1, 2], 0), ([1, 2], -1), ([1, 2], 3), ([], 1)],
                         ids=["k_zero", "k_negative", "k_over_n", "empty"])
def test_bad_k_raises(func, nums, k):
    with pytest.raises(ValueError):
        func(nums, k)


def test_k_is_one():
    assert window_sums([3, -2, 7], 1) == [3, -2, 7]
    assert best_window([3, -2, 7], 1) == (2, 7)


def test_k_is_n():
    assert window_sums([4, 1, 2], 3) == [7]
    assert best_window([4, 1, 2], 3) == (0, 7)


def test_bad_w_raises():
    for w in (0, -1):
        with pytest.raises(ValueError):
            max_events([1, 2], w)


def test_events_right_edge_and_empty():
    assert max_events([0, 5], 5) == 1
    assert max_events([], 3) == 0

В полном tests.py 34 теста. Ключ -k оставляет только тесты, в имени которых есть одно из перечисленных слов, — это двенадцать проверок границ. Вывод на эталонном решении:

collected 34 items / 22 deselected / 12 selected

tests.py::test_bad_k_raises[k_zero-window_sums] PASSED                   [  8%]
tests.py::test_bad_k_raises[k_zero-best_window] PASSED                   [ 16%]
tests.py::test_bad_k_raises[k_negative-window_sums] PASSED               [ 25%]
tests.py::test_bad_k_raises[k_negative-best_window] PASSED               [ 33%]
tests.py::test_bad_k_raises[k_over_n-window_sums] PASSED                 [ 41%]
tests.py::test_bad_k_raises[k_over_n-best_window] PASSED                 [ 50%]
tests.py::test_bad_k_raises[empty-window_sums] PASSED                    [ 58%]
tests.py::test_bad_k_raises[empty-best_window] PASSED                    [ 66%]
tests.py::test_k_is_one PASSED                                           [ 75%]
tests.py::test_k_is_n PASSED                                             [ 83%]
tests.py::test_bad_w_raises PASSED                                       [ 91%]
tests.py::test_events_right_edge_and_empty PASSED                        [100%]

====================== 12 passed, 22 deselected in 0.01s =======================

Вывод, если в best_window убрать проверку k, как на первой вкладке §2:

FAILED tests.py::test_bad_k_raises[k_zero-best_window] - Failed: DID NOT RAIS...
FAILED tests.py::test_bad_k_raises[k_negative-best_window] - IndexError: list...
FAILED tests.py::test_bad_k_raises[k_over_n-best_window] - Failed: DID NOT RA...
FAILED tests.py::test_bad_k_raises[empty-best_window] - Failed: DID NOT RAISE...
4 failed, 8 passed, 22 deselected in 0.02s

DID NOT RAISE означает, что функция вернула значение там, где тест ждал исключения. На k = −1 функция без проверки падает, но не с тем исключением: IndexError вместо ValueError. Тесты window_sums проходят — в ней проверка на месте.

§6Исправьте функцию

В окне ниже best_window с двумя ошибками из §2: нет проверки k, и цикл начинается с k + 1. Исправьте функцию так, чтобы прошли все семь тестов. Сначала запустите тесты и посмотрите, какие падают и с каким сообщением.

§7Review обновления окна

В КТП контроль занятия 9 включает «Git review на корректность обновления окна»: решение сдаётся Pull Request, и проверяющий читает код окна по строкам. Ниже — что он проверяет, затем три фрагмента для самостоятельного review.

def window_sums(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    total = sum(nums[:k])
    sums = [total]
    for r in range(k, len(nums)):
        sums.append(total)
        total += nums[r] - nums[r - k]
    return sums

def best_window(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError("k должно быть от 1 до len(nums)")
    total = sum(nums[:k])
    best, start = total, 0
    for r in range(k, len(nums)):
        total += nums[r] - nums[r - k]
        if total > best:
            best, start = total, r - k
    return (start, best)

def test_example():
    assert best_window([12, 15, 9, 20, 18, 7, 25], 3) == (4, 50)

def test_negative():
    assert best_window([-5, -2, -8, -1], 2) == (0, -7)

def test_bad_k():
    with pytest.raises(ValueError):
        best_window([1, 2], 0)