LawrencePeng's Blog

专注收集代码小精灵

Scala和Python的线性化算法

Scala的特性需要解决菱形继承问题，恰好Py也需要，但是两者却使用了不一样的方案，我们来看看究竟。

  • How

    • Scala

      • 1
        class C extends C1 with C2 with ... with Cn

      • lin(C) = C >> lin(C1) >> lin(C2) >> … >> lin(Cn)

      • 其中>>代表串联并去除重复项，右侧胜出。

    • Python

      • 经典的C3算法。

        • lin(C) = merge(C, lin(C1), lin(C2), …, lin (Cn), C1, C2, …, Cn)

        • merge实现为：

          • 持续的选出最好的头直到list枯竭，最好的头不可以在除了开头的list中位于最后一位。一个好的头可以在多个list中位于第一个，但不能再其他位置出现(除第一个)。
          • 可以记忆化实现。

        • demo

          1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          18
          19
          20
          21
          22
          23
          24
          25
          26
          27
          28
          29
          30
          31
          32
          33
          34
          35
          36
          37
          38
          39
          40
          41
          42
          43
          44
          45
          46
          47
          48
          49
          50
          51
          52
          53
          54
          55
          假定有如下的类继承体系：
          class A extends O
          class B extends O
          class C extends O
          class D extends O
          class E extends O
          class K1 extends A, B, C
          class K2 extends D, B, E
          class K3 extends D, A
          class Z extends K1, K2, K3
          那么C3运算过程如下：
          L(O)  := [O]                                                // the linearization of O is trivially the singleton list [O], because O has no parents
          L(A)  := [A] + merge(L(O), [O])                             // the linearization of A is A plus the merge of its parents' linearizations with the list of parents...
                 = [A] + merge([O], [O])
                 = [A, O]                                             // ...which simply prepends A to its single parent's linearization
          L(B)  := [B, O]                                             // linearizations of B, C, D and E are computed similar to that of A
          L(C)  := [C, O]
          L(D)  := [D, O]
          L(E)  := [E, O]
          L(K1) := [K1] + merge(L(A), L(B), L(C), [A, B, C])          // 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]
                 = [K1] + merge([A, O], [B, O], [C, O], [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, A] + merge([O], [B, O], [C, O], [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...
                 = [K1, A, B] + merge([O], [O], [C, O], [C])          // ...class B qualified, and so does class C; class O still appears in the tail of list 3
                 = [K1, A, B, C] + merge([O], [O], [O])               // finally, class O is a valid candidate, which also exhausts all remaining lists
                 = [K1, A, B, C, O]
          L(K2) := [K2] + merge(L(D), L(B), L(E), [D, B, E])
                 = [K2] + merge([D, O], [B, O], [E, O], [D, B, E])    // select D
                 = [K2, D] + merge([O], [B, O], [E, O], [B, E])       // fail O, select B
                 = [K2, D, B] + merge([O], [O], [E, O], [E])          // fail O, select E
                 = [K2, D, B, E] + merge([O], [O], [O])               // select O
                 = [K2, D, B, E, O]
          L(K3) := [K3] + merge(L(D), L(A), [D, A])
                 = [K3] + merge([D, O], [A, O], [D, A])               // select D
                 = [K3, D] + merge([O], [A, O], [A])                  // fail O, select A
                 = [K3, D, A] + merge([O], [O])                       // select O
                 = [K3, D, A, O]
          L(Z)  := [Z] + merge(L(K1), L(K2), L(K3), [K1, K2, K3])
                 = [Z] + merge([K1, A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K1, K2, K3])    // select K1
                 = [Z, K1] + merge([A, B, C, O], [K2, D, B, E, O], [K3, D, A, O], [K2, K3])        // fail A, select K2
                 = [Z, K1, K2] + merge([A, B, C, O], [D, B, E, O], [K3, D, A, O], [K3])            // fail A, fail D, select K3
                 = [Z, K1, K2, K3] + merge([A, B, C, O], [D, B, E, O], [D, A, O])                  // fail A, select D
                 = [Z, K1, K2, K3, D] + merge([A, B, C, O], [B, E, O], [A, O])                     // select A
                 = [Z, K1, K2, K3, D, A] + merge([B, C, O], [B, E, O], [O])                        // select B
                 = [Z, K1, K2, K3, D, A, B] + merge([C, O], [E, O], [O])                           // select C
                 = [Z, K1, K2, K3, D, A, B, C] + merge([O], [E, O], [O])                           // fail O, select E
                 = [Z, K1, K2, K3, D, A, B, C, E] + merge([O], [O], [O])                           // select O
                 = [Z, K1, K2, K3, D, A, B, C, E, O]                                               // done

          ​

AlgoScalaPythonLinearization