Algorithme efficace pour produire l'intersection à n voies de tableaux triés en C

Question

J'ai besoin de produire l'intersection entre des tableaux triés d'entiers en C. Je sais comment trouver l'intersection entre deux tableaux triés, mais j'ai besoin de le faire pour plus de deux tableaux, efficacement et sans connaissance préalable du nombre de tableaux. Je peux imposer une limite raisonnable au nombre maximal - disons dix pour l'instant. Ces tableaux peuvent compter de quelques éléments à plusieurs centaines de milliers d'éléments, et ne sont pas nécessairement de la même longueur.

Pseudo-code pour produire l'intersection de deux tableaux triés :

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

Je travaille en C, et je cherche une explication claire plutôt que du code.

Answer 1

Vous avez déjà la logique d'intersect sur deux tableaux, il suffit donc de l'appeler plusieurs fois.

Votre logique d'intersection,

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

Encapsulez le code ci-dessus dans un Intersect(int[] array1, int[] array2, int array1Length, int array2Length) qui renvoie int[] . Appelez à nouveau la méthode sur le résultat.

• Call1 : int[] result = Intersect(array1, array2, array1Length, array2Length)
• Appel2 : result = Intersect(result, array3, resultArrayLength, array3Length)
• ...
• Appelez (n-1) : result = Intersect(result, arrayn, resultArrayLength, arraynLength)

Optimisations possibles :

• Poursuivez les appels uniquement si le resultArrayLength > 0 (sinon l'intérêt est un ensemble nul).
• Dans la méthode d'intersection, on compare le dernier élément du tableau 1 avec le premier élément du tableau 2, c'est-à-dire que l'on compare le dernier élément du tableau 1 avec le premier élément du tableau 2.

EDITED if (array1[array1Length - 1] < array2[0]) retourne un ensemble vide (en supposant que les tableaux sont triés).

Answer 2

Je suppose que tous vos tableaux sont triés. Supposons que nous ayons des tableaux A_1 a A_n . Avoir un compteur pour chaque tableau (ainsi, on a n compteurs i_1 a i_n comme vous l'avez fait pour deux tableaux).

Maintenant, nous introduisons un minimum-heap, qui contient tous les tableaux de manière à ce que le tableau minimum soit le tableau avec le numéro le plus bas actuellement pointé par le pointeur correspondant. Cela signifie que nous pouvons, à chaque instant, récupérer le tableau avec le numéro le plus bas pointé.

Maintenant, nous extrayons le tableau minimum du tas et nous le mémorisons. Nous continuons à extraire le tableau minimum tant que le nombre pointé reste le même. Si nous extrayons todos (c'est-à-dire que si tous les tableaux ont le même nombre pointé le plus bas), nous savons que ce nombre est dans l'intersection. Si ce n'est pas le cas (c'est-à-dire si tous les tableaux ne contiennent pas le même nombre actuellement le plus bas pointé), nous savons que le nombre que nous sommes en train d'examiner ne peut pas être dans l'intersection. Ainsi, nous incrémentons tous les compteurs des tableaux déjà extraits et les remettons dans le tas.

Nous faisons cela jusqu'à ce que le pointeur d'un tableau atteigne la fin du tableau. Je suis désolé pour la description non détaillée, mais je n'ai pas le temps de travailler plus en détail.

Edit.

Si vous avez un tableau avec très peu d'éléments, il peut être utile de faire une recherche binaire dans les autres tableaux pour trouver ces numéros ou de vérifier ces numéros en utilisant une table de hachage.

Answer 3

Je commencerais par intersecter les deux plus petits tableaux, puis je continuerais à intersecter le résultat avec le plus petit tableau intersecté restant. Cela garantit qu'à chaque intersection, l'un des deux tableaux en question n'est pas plus grand que le plus petit tableau d'origine, ce qui devrait permettre de gagner du temps.

Answer 4

Utilisez l'approche du mergesort.

Que les tableaux soient

1 2 3 4 5 6 7.

D'abord trouver l'intersection de 1 2, 2 4, 5 6, Pour 7 ne rien faire. Nouveaux ensembles : A(1-2 Intersection) B(3-4 Intersection) C(5 - 6 Intersection) 7. Répétez ce qui précède jusqu'à ce que vous obteniez un ensemble.

Answer 5

Vous pouvez probablement paralléliser le calcul car l'opération d'intersection est commutative et associative. Demandez à chaque thread de calculer l'intersection de deux tableaux, ce qui réduira le nombre de tableaux par deux à chaque étape.