Быстрый алгоритм для кумулятивного пересечения двух массивов

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

Answer 2

Возможно, что-то вроде этого:

a1 = [1,3,4,5,2,6]
a2 = [4,1,5,2,3,7]
n = len(a1)
all_intersects = list()
current_intersect = list()
s1 = set()
s2 = set()
for i in range(n):
   if a2[i] not in s2 and a2[i] in s1:
      current_intersect.append(a2[i])
   if a1[i] not in s1 and a1[i] in s2:
      current_intersect.append(a1[i])
   all_intersects.append(list(current_intersect))
   s1.add(a1[i])
   s2.add(a2[i])

Общая идея - сохранить два набора чисел, которые были замечены. Набор s1 отслеживает числа, которые были замечены в списке a1. Набор s2 отслеживает числа, которые были замечены в списке a2.

При обработке числа из списка a1, если число еще не было замечено, но было замечено вlist a2, тогда мы можем добавить его в список чисел в current_intersect. Аналогично для номера из списка a2.

После обновления current_intersect, current_intersect добавляется к all_intersects. Кроме того, текущие элементы массива добавляются к двум наборам.