最通用的父类

Question

有没有什么简单的方法可以找到一组对象的“最大公共超类”？比如，如果

class A(object): pass
class B(A): pass
class C(A): pass
class D(B, C): pass
class E(C): pass
class F(D, E): pass

和

b = B()
d = D()
e = E()

那么

gcs(b, e) is A
gcs(d, e) is C
gcs(e, e) is E

Answer 1

我觉得这里有一个问题，就是可能会有不止一个最大的共同父类。比如说，看看下面这个类的继承结构：

AB ---> A
   \ /
    x
   / \
BA ---> B

在这个例子中，A和B都是gca([AB, BA])的合理答案。

在我自己的代码中遇到这个问题后，我意识到我需要重新思考这个问题，变成：

找到一个指定类列表中共享的最小共同基类集合；这个集合的定义是：所有的类必须满足两个条件，1）是原始列表中所有类的父类，2）没有子类也包含在返回的列表中。

这个最后的要求确保我们只得到“最近”的类，同时也处理了有多个这样的值的情况。

下面的代码实现了这个功能：

def minimal_common_bases(classes):
    # pull first class, and start with it's bases
    gen = iter(classes)
    cls = next(gen, None)
    if cls is None:
        return set()
    common = set(cls.__mro__)

    # find set of ALL ancestor classes,
    # by intersecting MROs of all specified classes
    for cls in gen:
        common.intersection_update(cls.__mro__)

    # remove any bases which have at least one subclass also in the set,
    # as they aren't part of "minimal" set of common ancestors.
    result = common.copy()
    for cls in common:
        if cls in result:
            result.difference_update(cls.__mro__[1:])

    # return set
    return result

• 注意：在Python 2中，你需要使用inspect.getmro(cls)而不是cls.__mro__。

Answer 2

这其实是一个简化版的最长公共子序列问题；我们要比较MRO序列，并返回索引和最小的类型：

def gcs(a, b):
    """Find the common base class between two classes or instances"""
    try:
        a, b = a.mro(), b.mro()
    except AttributeError:
        a, b = type(a).mro(), type(b).mro()
    a_idx, b_idx = {t: i for i, t in enumerate(a)}, {t: i for i, t in enumerate(b)}
    try:
        return min(a_idx.viewkeys() & b_idx.viewkeys(),
                   key=lambda t: a_idx[t] + b_idx[t])
    except ValueError:
        return None

这个算法的复杂度是O(M+N)，其中M和N分别是两个对象的MRO的大小。这个函数可以处理类和实例。

下面是用你提供的示例对象的演示：

>>> gcs(e, b)
<class '__main__.A'>
>>> gcs(e, d)
<class '__main__.C'>
>>> gcs(e, e)
<class '__main__.E'>

Answer 3

这个内容是基于Martijn的想法，但采用了一种更简单的方法，因为在这里时间复杂度不是问题（感谢@veedrac的建议）：

def gcs(*instances):
    classes = [type(x).mro() for x in instances]
    for x in classes[0]:
        if all(x in mro for mro in classes):
            return x

print gcs(b, e)
print gcs(d, e)
print gcs(e, e)

输出结果：

<class '__main__.A'>
<class '__main__.C'>
<class '__main__.E'>

上面代码的一个小变种，使用了集合：

def gcs(*instances):
    mros = (type(ins).mro() for ins in instances)
    mro = next(mros)
    common = set(mro).intersection(*mros)
    return next((x for x in mro if x in common), None)