На этом шаге мы обобщим разработанные функции.

Функции linear_contains() и binary_contains() можно обобщить для работы практически с любой последовательностью Python. Следующие обобщенные версии почти идентичны

В примере ниже задействовано много импортированных типов. В дальнейшем мы еще раз воспользуемся файлом generic_search.py для многих дополнительных универсальных алгоритмов поиска, что избавит нас от необходимости импорта.

Прежде чем продолжить работу, вам нужно установить модуль typing_extensions с помощью команды

  pip install typing_extensions

или

  pip3 install typing_extensions

в зависимости от того, как настроен интерпретатор Python. Этот модуль понадобится для доступа к типу Protocol, который войдет в состав стандартной библиотеки в следующей версии Python (согласно РЕР 544). Так что в следующей версии Python импортировать модуль typing_extensions не понадобится и вместо строки

  from typing_extensions import Protocol

можно будет использовать

  from typing import Protocol

Ниже приведен текст этого файла.

from __future__ import annotations
from typing import TypeVar, Iterable, Sequence, Generic, 
        List, Callable, Set, Deque, Dict, Any, Optional
from typing_extensions import Protocol
from heapq import heappush, heappop

T = TypeVar('T')


def linear_contains(iterable: Iterable[T], key: T) -> bool:
    for codon in iterable:
        if codon == key:
            return True
    return False


C = TypeVar("C", bound="Comparable")


class Comparable(Protocol):
    def __eq__(self, other: Any) -> bool:
        return self == other

    def __lt__(self: C, other: C) -> bool:
        return (not self > other) and self != other

    def __gt__(self: C, other: C) -> bool:
        return (not self < other) and self != other

    def __le__(self: C, other: C) -> bool:
        return self < other or self == other

    def __ge__(self: C, other: C) -> bool:
        return not self < other

    def binary_contains(sequence: Sequence[C], key: C) -> bool:
        low: int = 0
        high: int = len(sequence) - 1
        while low <= high:  # пока еще есть место для поиска
            mid: int = (low + high) // 2
            if sequence[mid] < key:
                low = mid + 1
            elif sequence[mid] > key:
                high = mid - 1
            else:
                return True
        return False


if __name__ == "__main__":
    print(linear_contains([1, 5, 15, 15, 15, 15, 20], 5))  # True
    print(linear_contains(["a", "d", "е", "f", "z"], "f"))  # True
    print(linear_contains(["john", "mark", "ronald", "sarah"], "sheila"))  # False

Архив с файлом можно взять здесь.

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

Именно в этом заключается главная эффективность параметризованного кода. Единственный неудачный элемент в этом примере - запутанные аннотации типов Python в форме класса Comparable. Тип Comparable - это тип, который реализует операторы сравнения (<, >= и т. д.). В будущих версиях Python должен появиться более лаконичный способ создания аннотации типа для типов, которые реализуют эти общие операторы.

Со следующего шага мы начнем рассматривать прохождение лабиринта.

Предыдущий шаг Содержание Следующий шаг