且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

Python 的模式匹配性能如何?是 O(1) 吗?

更新时间:2023-02-13 21:07:31

单就时间复杂度而言,这两种结构基本是等价的.

In terms of time complexity alone, the two constructs are basically equivalent.

但是,在考虑可读性和代码结构时,它们非常不同.作为一般规则,如果您匹配或测试多个主题,if-elif-else***可能是完成这项工作的***工具:

They're very different, though, when considering readability and code structure. As a general rule, if you're matching values or testing several subjects, an if-elif-else ladder will probably be the best tool for the job:

def stringify_response(response: int) -> str:
    if 100 <= response < 200:
        kind = "info"
    elif 200 <= response < 300:
        kind = "success"
    elif 300 <= response < 400:
        kind = "redirect"
    elif 400 <= response < 500:
        kind = "client error"
    elif 500 <= response < 600:
        kind = "server error"
    else:
        kind = "unexpected response"
    return f"{kind} ({response})"

另一方面,如果您要匹配单个主题的结构,那么结构模式匹配可能是该工作的***工具:>

On the other hand, if you're matching the structure of a single subject, then structural pattern matching will probably be the best tool for the job:

from ast import *

def lint_function_def(function_def: FunctionDef) -> None:
    match function_def.body:
        case *_, Assign([Name(na)], e), Return(Name(nr, lineno=l)) if na == nr:
            print(f"line {l}: consider returning {unparse(e)} instead of "
                  f"assigning to {na!r} on line {e.lineno}")

未来的改进

话虽如此,对模式匹配的句法支持的好处之一是编译器和解释器拥有非凡的上下文知识.因此,他们可以做出普通控制流无法做出的假设.

Future Improvements

With that said, one of the benefits of syntactical support for pattern matching is that the compiler and interpreter possess an extraordinary knowledge of context. Because of this, they can make assumptions that ordinary control flow cannot.

考虑来自 PEP 636 的声明(稍微简化):

Consider this statement (slightly simplified) from PEP 636:

match command.split():
    case ["north"] | ["go", "north"]:
        # Code for moving north.
    case ["get", obj] | ["pick", "up", obj] | ["pick", obj, "up"]:
        # Code for picking up the given object.

当前"(CPython 3.10) 模式编译器非常幼稚,将其编译为如下所示:

The "current" (CPython 3.10) pattern compiler is quite naive, and compiles it to something like this:

_subject = command.split()
import _collections_abc
if (
    isinstance(_subject, _collections_abc.Sequence)
    and len(_subject) == 1
    and _subject[0] == "north"
):
    # Code for moving north.
elif (
    isinstance(_subject, _collections_abc.Sequence)
    and len(_subject) == 2
    and _subject[0] == "go"
    and _subject[1] == "north"
):
    # Code for moving north.
elif (
    isinstance(_subject, _collections_abc.Sequence)
    and len(_subject) == 2
    and _subject[0] == "get"
):
    obj = _subject[1]
    # Code for picking up the given object.
elif (
    isinstance(_subject, _collections_abc.Sequence)
    and len(_subject) == 3
    and _subject[0] == "pick"
    and _subject[1] == "up"
):
    obj = _subject[2]
    # Code for picking up the given object.
elif (
    isinstance(_subject, _collections_abc.Sequence)
    and len(_subject) == 3
    and _subject[0] == "pick"
    and _subject[2] == "up"
):
    obj = _subject[1]
    # Code for picking up the given object.

尽管这个例子很简单,但生成的代码充满了冗余检查.匹配命令 pick Spam up" 检查 isinstance(_subject, _collections_abc.Sequence) 五次,调用 len(_subject) 五次,并检查 _subject[0] == "pick" 两次!

Even though this example is quite simple, the generated code is full of redundant checks. Matching the command "pick Spam up" checks isinstance(_subject, _collections_abc.Sequence) five times, calls len(_subject) five times, and checks _subject[0] == "pick" twice!

然而,编译器完全有可能生成更高效的决策树".相反,没有执行不必要的工作.这可能是这样的:

However, it's entirely possible for the compiler to generate more efficient "decision trees" instead, where no unnecessary work is performed. Here's what that might look like:

_subject = command.split()
import _collections_abc
if isinstance(_subject, _collections_abc.Sequence):
    _len_subject = len(_subject)
    if _len_subject == 1:
        if _subject[0] == "north":
            # Code for moving north.
    elif _len_subject == 2:
        _subject_0 = _subject[0]
        if _subject_0 == "go":
            if _subject[1] == "north":
                # Code for moving north.
        elif _subject_0 == "get":
            obj = _subject[1]
            # Code for picking up the given object.
    elif _len_subject == 3:
        if _subject[0] == "pick":
            _subject_1 = _subject[1]
            if _subject_1 == "up":
                obj = _subject[2]
                # Code for picking up the given object.
            elif _subject[2] == "up":
                obj = _subject_1
                # Code for picking up the given object.

当你有守卫或嵌套模式时,它开始变得更加复杂……但我希望我们能够在 CPython 3.11 中加入这样的东西!

It starts getting more complicated when you have guards or nested patterns... but I'm hopeful that we'll be able to get something like this into CPython 3.11!