如何在Python中找到几种类型的最近公共祖先（基础类型）？

Question

如何在Python中找到几种类型的最近公共祖先（基础类型）？

3

我需要找到一组类的最后一个共同祖先，以便返回该类型。

背景是我正在进行一些相当复杂的元编程，涉及重载numpy的功能。(不要问我)我有一个函数的可变数量的参数，我已经将其类型提取到一个集合中(通过过滤掉不相关的类型)，使用这些信息，我需要弄清楚在类型树上所有类型共享相同基类型的最远距离。我有一些第一次尝试，但我被多继承等问题绊倒了。

第一次尝试:

def lca_type(types):
    if len(types) == 1:
        return types.pop()
    filtered_types = set()
    for type in types:
        if not any(issubclass(type, x) for x in types):
            filtered_types.add(type)
    if len(filtered_types) == 1:
        return filtered_types.pop()
    # TODO: things get tricky here

考虑以下类层次结构：

class A(object):
    pass
class B(A):
    pass
class C(A):
    pass
class D(A):
    pass
class B1(B):
    pass
class B2(B):
    pass
class BC(C, B1):
    pass
class CD(C, D):
    pass
class D1(D):
    pass
class BD(B, D):
    pass
class B1_1(B1):
    pass

预期结果：

lca_type({A,BD}) == A
lca_type({C}) == C
lca_type({B1,B2}) == B
lca_type({{B1_1, D}) == A
lca_type({CD, BD}) == D
lca_type({B1_1, BC}) == B1

- user1424589

可能有一个递归的解决方案。我同意多重继承会使它变得复杂，你需要进行广度优先搜索来找到任何分支上的MRCA。 - Barmar

@barmer 我认为这是正确的。 - user1424589

2个回答

2

取所有共同祖先的集合，使用朴素的最小算法找到最低的共同祖先，然后验证它是否实际上是最近的：

def lca_type(types):
    mros = [t.__mro__ for t in types]
    all_common_ancestors = set(mros[0]).intersection(*mros[1:])

    ancestor_iter = iter(all_common_ancestors)
    candidate = next(ancestor_iter)
    for next_candidate in ancestor_iter:
        if issubclass(next_candidate, candidate):
            candidate = next_candidate

    if all(issubclass(candidate, ancestor) for ancestor in all_common_ancestors):
        return candidate
    else:
        raise ValueError("No unambiguous lowest common ancestor")

使用天真的最小值可能看起来有问题，但实际上即使在多重继承中也是可以的。如果存在一个明确的最低公共祖先，则它是all_common_ancestors中每个元素（包括它自己）的子类，因此当我们到达最低公共祖先时，我们将candidate设置为最低公共祖先，然后再也不更改candidate。如果不存在明确的最低公共祖先，则无论循环结束时candidate变成什么，它都不会通过验证检查。

处理__subclasscheck__/__subclasshook__覆盖的部分比较棘手。我认为这个实现应该足够强大，可以处理大多数常见的ABC情况，但当任意__subclasscheck__实现使由issubclass定义的图形不是DAG时，整个最低公共祖先的概念就变得奇怪了。

- user2357112

不强烈推荐使用reduce（通常被认为是不好的做法），但你可以用candidate = functools.reduce(lambda x, y: x if issubclass(x, y) else y, all_common_ancestors)替换从ancestor_iter定义到for循环结束的所有代码（在Python 2中无需import和限定functools）。将一系列值压缩成一个单一的胜者是reduce的几个典型用例之一，在这种情况下，它大大减少了冗余代码（尽管对于那些不理解reduce的人来说，可读性可能会降低）。 - ShadowRanger

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- blhsing · Accepted Answer

您可以使用每个类的mro方法来获取祖先类列表。将祖先列表映射到collections.Counter，这样您就可以在它们上使用&运算符以获取共同祖先并保持键顺序，从而有效地模拟获取有序集合的交集。然后在聚合的Counter对象的键序列上使用next函数来获取最近的祖先：

from functools import reduce
from operator import and_
from collections import Counter

def lca_type(classes):
    return next(iter(reduce(and_, (Counter(cls.mro()) for cls in classes))))

为了使以下表达式均返回True：

lca_type({A, BD}) == A
lca_type({C}) == C
lca_type({B1, B2}) == B
lca_type({B1_1, D}) == A
lca_type({CD, BD}) == D
lca_type({B1_1, BC}) == B1
lca_type({B1_1, BC, BD}) == B

请注意，键的顺序仅在Python 3.7+中保留，因此对于以前的Python版本，您可以将Counter替换为collections.OrderedDict的子类，该子类重用Counter的属性：

from functools import reduce
from operator import and_
from collections import Counter, OrderedDict
import collections

collections.Counter = Counter = type('Counter', (OrderedDict,), dict(vars(Counter)))

def lca_type(classes):
    return next(iter(reduce(and_, (Counter(cls.mro()) for cls in classes))))