Hướng dẫn c3 linearization algorithm python - python thuật toán tuyến tính hóa c3

02-05-2019 12:10 | | trong blog | 851 từ | 4 phút để đọc lại: Python Cpython MRO Thuật toán | | in Blog | 851 words | 4 min to read
tags: python cpython mro algorithms

Thứ tự độ phân giải phương pháp (MRO) là một thứ tự trong đó các phương thức nên được kế thừa trong trường hợp nhiều iheritance. Thuật toán tuyến tính hóa C3 là cách MRO hoạt động dưới mui xe kể từ phiên bản 2.3.MRO) is a order in which methods should be inherited in the case of multiple iheritance. C3 linearization algorithm is how MRO works under the hood since version 2.3.

Wikipedia thực hiện một công việc tuyệt vời giải thích thuật toán. Nó có thể được giảm xuống các bước sau & nbsp; các bước:

1. Tuyến tính hóa (tức là thứ tự độ phân giải) là một lớp và sự hợp nhất của tuyến tính hóa của cha mẹ và một danh sách cha mẹ & nbsp;
2. Tuyến tính hóa lớp không có phụ huynh bằng với lớp & nbsp;
3. Quá trình hợp nhất được thực hiện bằng cách chọn người đứng đầu đầu tiên của danh sách không xuất hiện trong đuôi của bất kỳ danh sách nào. Trường hợp đầu là yếu tố đầu tiên của danh sách và đuôi là tất cả nhưng các yếu tố đầu tiên của danh sách. Các đầu được chọn nhiều lần và thêm vào MRO kết quả cho đến khi tất cả các danh sách được & NBSP;MRO until all the lists are exhausted.
4. Nếu một đầu không thể được chọn trong khi không phải tất cả các danh sách đều không thể tính toán được là không thể tính toán do các thứ tự không nhất quán của các phụ thuộc trong hệ thống phân cấp kế thừa và không có tuyến tính hóa của lớp ban đầu & NBSP;

Ví dụ nhiều kế thừa phức tạp, lịch sự H2Power

Xem xét quá trình tuyến tính hóa cho lớp K1:

// first, find the linearizations of K1's parents, L(A), L(B), and L(C),
// and merge them with the parent list [A, B, C]
L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C])
// class A is a good candidate for the first merge step, because it only
// appears as the head of the first and last lists
       = [K1] + merge([A, O], [B, O], [C, O], [A, B, C])
// class O is not a good candidate for the next merge step, because it also
// appears in the tails of list 2 and 3; but class B is a good candidate
       = [K1, A] + merge([O], [B, O], [C, O], [B, C])
// class C is a good candidate; class O still appears in the tail of list 3
       = [K1, A, B] + merge([O], [O], [C, O], [C])
// finally, class O is a valid candidate, which also exhausts all remaining lists
       = [K1, A, B, C] + merge([O], [O], [O])
       = [K1, A, B, C, O]

Vì vậy, ở cấp độ cao hơn, việc triển khai ngây thơ của thuật toán tuyến tính hóa C3 có thể được biểu thị dưới dạng đơn giản & nbsp; đệ quy: đệ quy:

def mro(cls: type) -> List[type]:
  """
  Return a list of classes in order corresponding to Python's MRO.
  """
  result = [cls]

  if not cls.__bases__:
      return result
  else:
      return result + _merge(*[mro(kls) for kls in cls.__bases__], cls.__bases__)

Sau đó, _merge liên tục kiểm tra xem danh sách của nó có cạn kiệt và nối các đầu thích hợp vào MRO kết quả:MRO:

def _merge(*lists) -> list:
  result: List[Optional[type]] = []
  linearizations = DependencyList(*lists)

  while True:
      if linearizations.exhausted:
          return result

      for head in linearizations.heads:
          if head and (head not in linearizations.tails):  # type: ignore
              result.append(head)
              linearizations.remove(head)

              # Once candidate is found, continue iteration
              # from the first element of the list
              break
      else:
          # Loop never broke, no linearization could possibly be found
          raise ValueError('Cannot compute linearization, a cycle found')

Để ẩn một số danh sách phụ thuộc nội bộ và sự trừu tượng của danh sách phụ thuộc là & nbsp; được sử dụng:

from collections import deque
from itertools import islice
from typing import List, Tuple, Optional


class Dependency(deque):
    @property
    def head(self) -> Optional[type]:
        try:
            return self[0]
        except IndexError:
            return None

    @property
    def tail(self) -> islice:  # type: ignore
        """
        Return islice object, which is suffice for iteration or calling `in`
        """
        try:
            return islice(self, 1, self.__len__())
        except (ValueError, IndexError):
            return islice([], 0, 0)


class DependencyList:
    """
    A class represents list of linearizations (dependencies)

    The last element of DependencyList is a list of parents.
    It's needed  to the merge process preserves the local
    precedence order of direct parent classes.
    """
    def __init__(self, *lists: Tuple[List[type]]) -> None:
        self._lists = [Dependency(i) for i in lists]

    def __contains__(self, item: type) -> bool:
        """
        Return True if any linearization's tail contains an item
        """
        return any([item in l.tail for l in self._lists])  # type: ignore

    def __len__(self):
        size = len(self._lists)
        return (size - 1) if size else 0

    def __repr__(self):
        return self._lists.__repr__()

    @property
    def heads(self) -> List[Optional[type]]:
        return [h.head for h in self._lists]

    @property
    def tails(self) -> 'DependencyList':  # type: ignore
        """
        Return self so that __contains__ could be called

        Used for readability reasons only
        """
        return self

    @property
    def exhausted(self) -> bool:
        """
        Return True if all elements of the lists are exhausted
        """
        return all(map(lambda x: len(x) == 0, self._lists))

    def remove(self, item: Optional[type]) -> None:
        """
        Remove an item from the lists

        Once an item removed from heads, the leftmost elements of the tails
        get promoted to become the new heads.
        """
        for i in self._lists:
            if i and i.head == item:
                i.popleft()

Toàn bộ cơ sở mã có thể được tìm thấy trong kho lưu trữ C3linear của tôi. Bạn có thể cài đặt nó từ mã nguồn hoặc thông qua & nbsp; pypi:

python setup.py install  # from the source code
pip install c3linear  # from the Cheese Shop

Sau đó, chỉ cần nhập nó và kiểm tra đối với phương pháp MRO của Python đối tượng:

from c3linear.mro import mro

class A: pass
class B(A): pass
mro(B) == B.mro()

Hãy xem các bài kiểm tra để đi sâu vào nhiều kế thừa phức tạp hơn & nbsp; ví dụ.