06-通用示例

2.1.4　通用示例

函数 linear_contains() 和 binary_contains() 可以广泛应用于几乎所有Python序列。以下通用版本与之前的版本几乎完全相同，只不过有一些名称和类型提示信息有一些变化。具体代码如代码清单2-9所示。

注意 　代码清单2-9中有很多导入的类型。本章后续有很多通用搜索算法都将复用generic_search.py文件，这样就可以避免导入的麻烦。

注意 　 在往下继续之前，需要用 pip install typing_extensions 或 pip3 install typing_extensions 安装 typing_extensions 模块，具体命令取决于Python解释器的配置方式。这里需要通过该模块获得 Protocol 类型，Python后续版本的标准库中将会包含这个类型（PEP 544已有明确说明）。因此在Python的后续版本中，应该不需要再导入 typing_extensions 模块了，并且会用 from typing import Protocol 替换 from typing_extensions import Protocol 。

代码清单2-9　generic_search.py

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 item in iterable:
        if item == key:
            return True
    return False
C = TypeVar("C", bound="Comparable")
class Comparable(Protocol):
    def __eq__(self, other: Any) -> bool:
       ...
    def __lt__(self: C, other: C) -> bool:
       ...
    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:  # while there is still a search space
        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(binary_contains(["a", "d", "e", "f", "z"], "f"))  # True
    print(binary_contains(["john", "mark", "ronald", "sarah"], "sheila"))  # False

现在可以尝试搜索其他类型的数据了。这些函数几乎可以复用于任何Python集合类型。这正是编写通用代码的威力。上述例子中唯一的遗憾之处就是为了满足Python类型提示的要求，必须以 Comparable 类的形式实现。 Comparable 是一种实现比较操作符（<、> =等）的类型。在后续的Python版本中，应该有一种更简洁的方式来为实现这些常见操作符的类型创建类型提示。