Эффективный алгоритм для создания n-стороннего пересечения отсортированных массивов в C

Question

Мне нужно создать пересечение между некоторыми отсортированными массивами целых чисел в C. Я знаю, как найти пересечение между двумя отсортированными массивами, но мне нужно сделать это для более чем двух массивов, эффективно и без предварительного знания числамассивов.Я могу наложить разумное ограничение на максимальное количество - скажем, десять пока.Эти массивы могут иметь длину от нескольких элементов до пары сотен тысяч элементов и не обязательно имеют одинаковую длину.

Псевдокод для создания пересечения двух отсортированных массивов:

while i < m and j < n do:
    if array1[i] < array2[j]:
        increment i
    else if array1[i] > array2[j]: 
        increment j
    else 
        add array1[i] to intersection(array1, array2)
        increment i
        increment j

Я работаю с C, и я после четкого объяснения, а не кода.

Answer 1

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

Ваша логика пересечения,

while i < m and j < n do:
if array1[i] < array1[j]:
    increment i
else if array1[i] > array2[j]: 
    increment j
else 
    add array1[i] to intersection(array1, array2)
    increment i
    increment j

Инкапсулируйте вышеуказанный код в Intersect(int[] array1, int[] array2, int array1Length, int array2Length), который возвращает int[]. Вызовите метод еще раз для результата.

• Call1: int[] result = Intersect(array1, array2, array1Length, array2Length)
• Звонок2: result = Intersect(result, array3, resultArrayLength, array3Length)
• ...
• Звоните (n-1): result = Intersect(result, arrayn, resultArrayLength, arraynLength)

Возможные оптимизации:

• Продолжать вызовы, только если resultArrayLength > 0 (в противном случае интерес является нулевым набором).
• В методе пересечения сравните последний элемент array1 с первым элементом array2, т.е.

EDITED if (array1[array1Length - 1] < array2[0]) вернуть пустой набор (при условии, что массивы отсортированы).

Answer 2

Я предполагаю, что все ваши массивы отсортированы. Предположим, у нас есть массивы от A_1 до A_n. Есть счетчик для каждого массива (таким образом, у нас есть n счетчики i_1 до i_n, как вы сделали это для двух массивов).

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

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

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

Редактировать.

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

Answer 3

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

Answer 4

Вы, вероятно, можете распараллелить вычисления, поскольку операция пересечения коммутативна и ассоциативна.Пусть каждый поток вычислит пересечение двух массивов, что уменьшит число массивов на два на каждом шаге.

Answer 5

Используйте подход слияния.

Пусть массивы будут

1 2 3 4 5 6 7.

Сначала найдите пересечение 1 2, 2 4, 5 6, ибо 7 не делайте ничего. Новые наборы: A (пересечение 1-2) B (пересечение 3-4) C (пересечение 5-6) 7. Повторяйте выше, пока не получите один комплект.

Answer 6

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

Вот код Python для того же самого:

def intersection(arr_list):
    """
    >>> intersection([[1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6]])
    [3, 4]
    >>> intersection([[1, 2, 3, 4], [2, 3, 4, 5], [5, 6]])
    []
    """
    n = len(arr_list)
    ret = []
    d = {}
    for i in arr_list[0]:
        d[i] = 1
    for arr in arr_list[1:]:
        for j in arr:
            if j in d:
                d[j] += 1
    for k, v in d.items():
        if v == n:
            ret.append(k)
    return ret

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=True)