python - 两个数组累积交集的快速算法

Question

我想计算两个数组的累积交集。例如

> cumulative_intersection([1,3,4,5,2,6], [4,1,5,2,3,7])
[[], [1], [1,4], [1,4,5], [1,4,5,3,2], [1,4,5,3,2]]

我可以使用循环暴力实现它。例如，在 Python 中，

a1 = [1,3,4,5,2,6]
a2 = [4,1,5,2,3,7]
n = len(a1)
all_intersects = list()
for i in range(n):
    intersect = np.intersect1d(a1[:i], a2[:i])
    all_intersects.append(intersect)

有没有更有效的算法来计算这个？我的直觉是计算可以按对数方式减少，因为每个连续列表都是前一个列表的超集。

Answer 1

如果您将交集算法替换为不对结果进行排序的算法(因此需要线性时间)，则您的蛮力算法的渐近复杂度变为 O(n²)，这已经达到了您的要求问题的下界渐近复杂性。

为了证明这个下限，为了便于论证，我们假设您有一个 O(1) 方法来确定需要将哪些数字添加到第 i 个交点以获得第 (i+1) 个交点。因此，如果 C(i) 是复制第 i 个交集的时间，则您的总运行时间将为

那么，复制一个数组是一个复杂度为 O(n) 的操作，在最坏的情况下，您的两个数组相同，第 i 个交集的长度为 i+1。因此，最坏情况下的运行时间是

也就是说，您可以通过修改用于生成两个列表的交集的 O(n) 贪婪算法，以常数因子击败您的原始算法的运行时间。

def intersection(a: list,b: list):
    ''' Computes the interection of lists a and b. Assumes that a and b have the same 
    length'''
    a_leftover = set()
    b_leftover = set()
    stored = set() # We only want unique values
    n = len(a)
    result = []
    for i in range(n):
        a_elm = a[i]
        b_elm = b[i]
        if a_elm not in stored and a_elm == b_elm:
            result.append(a_elm)
            stored.add(a_elm)
        else:
            if a_elm not in stored:
                if a_elm in b_leftover:
                    # a_elm was previously encountered in b
                    result.append(a_elm)
                    stored.add(a_elm)
                    b_leftover.remove(a_elm)
                else:
                    a_leftover.add(a_elm)
            if b_elm not in stored:
                if b_elm in a_leftover:
                    # b_elf was previously encountered in a
                    result.append(b_elm)
                    stored.add(b_elm)
                    a_leftover.remove(b_elm)
                else:
                    b_leftover.add(b_elm)
    return result

您需要做的就是修改算法以存储和返回中间结果。

def cumulative_intersection(a: list,b: list):
    ''' Computes the cumulative interection of lists a and b. Assumes that a and b have the same 
    length'''
    a_leftover = set()
    b_leftover = set()
    stored = set() # We only want unique values
    n = len(a)
    result = []
    results = []
    for i in range(n):
        a_elm = a[i]
        b_elm = b[i]
        if a_elm not in stored and a_elm == b_elm:
            result.append(a_elm)
            stored.add(a_elm)
        else:
            if a_elm not in stored:
                if a_elm in b_leftover:
                    # a_elm was previously encountered in b
                    result.append(a_elm)
                    stored.add(a_elm)
                    b_leftover.remove(a_elm)
                else:
                    a_leftover.add(a_elm)
            if b_elm not in stored:
                if b_elm in a_leftover:
                    # b_elf was previously encountered in a
                    result.append(b_elm)
                    stored.add(b_elm)
                    a_leftover.remove(b_elm)
                else:
                    b_leftover.add(b_elm)
        results.append(result[:])
    return results