Быстрый набор соответствия перекрытия алгоритм

Question

Допустим, у меня есть два набора:

A = [1, 3, 5, 7, 9, 11] 

и

B = [1, 3, 9, 11, 12, 13, 14] 

Оба набора могут быть произвольными (и различающимися числом элементов).

Я пишу приложение, критичное к производительности, которое требует от меня выполнить поиск, чтобы определить количество элементов, которые имеют оба набора. Мне действительно не нужно возвращать матчи, только количество матчей.

Очевидно, что наивный метод был бы грубой силой, но я подозреваю, что это почти не оптимально. Есть ли алгоритм для выполнения этого типа операции?

Если это помогает, во всех случаях наборы будут состоять из целых чисел.

Answer 1

Если оба набора имеют примерно одинаковый размер, ходьба по ним в синхронизации, аналогичная операции слияния слиянием, примерно такая же быстрая, как и она.

Посмотрите на первые элементы.
Если они совпадают, вы добавляете этот элемент к вашему результату и перемещаете оба указателя вперед.
В противном случае вы перемещаете указатель, указывающий на наименьшее значение вперед.

Некоторые псевдо-Python:

a = [] 
b = [] 
res = [] 
ai = 0 
bi = 0 
while ai < len(a) and bi < len(b): 
    if a[ai] == b[bi]: 
     res += a[ai] 
     ai+=1 
     bi+=1 
    elif a[ai] < b[bi]: 
     ai+=1 
    else: 
     bi+=1 
return res 

Если один набор значительно больше, чем другие, вы можете использовать бинарный поиск искать для каждого элемента из меньшего в большее.

Answer 2

Вот эта идея (очень хорошее описание уровня).

Кстати, я позволю себе предположить, что числа в каждом наборе не появляются более одного раза, например [1,3,5,5,7,7,9,11] не будут происходит.

Вы определяете две переменные, которые будут удерживать индексы, которые вы просматриваете в каждом массиве.

Вы начинаете с первого номера каждого набора и сравниваете его. Два возможных условия: они равны или один больше другого.

Если они равны, вы подсчитываете событие и перемещаете указатели в обоих массивах к следующему элементу.

Если они отличаются, вы перемещаете указатель нижнего значения на следующий элемент в массиве и повторяете процесс (сравниваете оба значения).

Петля заканчивается, когда вы достигаете последнего элемента любого из массивов.

Надеюсь, что я смог объяснить это ясным образом.

Answer 3

Если оба набора отсортированы, наименьший элемент обоих наборов является либо минимумом первого набора, либо минимумом второго набора. Если это мин первого набора, то следующим наименьшим элементом является либо минимум второго набора, либо второй минимум первого набора. Если вы повторите это до конца обоих наборов, вы заказали оба набора. Для вашей конкретной проблемы вам просто нужно сравнить, если элементы также равны.

Вы можете перебрать объединение обоих множеств со следующим алгоритмом:

intersection_set_cardinality(s1, s2) 
{ 
    iterator i = begin(s1); 
    iterator j = begin(s2); 

    count = 0; 
    while(i != end(s1) && j != end(s2)) 
    { 
     if(elt(i) == elt(j)) 
     { 
      count = count + 1; 
      i = i + 1; 
      j = j + 1; 
     } 
     else if(elt(i) < elt(j)) 
     { 
      i = i + 1; 
     } 
     else 
     { 
      j = j + 1;   
     } 
    } 
    return count 
}