La meilleure façon de trouver une intersection entre deux tableaux ?

Question

J'ai été confronté à ce problème à plusieurs reprises dans diverses situations. Il est générique à tous les langages de programmation bien que je sois à l'aise avec C ou Java.

Considérons deux tableaux (ou collections) :

char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};

Comment obtenir les éléments communs entre les deux tableaux dans un nouveau tableau ? Dans ce cas, l'intersection des tableaux A et B est la suivante char[] c = {'c', 'd'} .

Je veux éviter l'itération répétée d'un tableau à l'intérieur d'un autre tableau, ce qui augmentera le temps d'exécution de (longueur de A fois la longueur de B). augmenterait le temps d'exécution de (longueur de A fois la longueur de B), ce qui est excessif dans le cas de grands tableaux.

Est-il possible de faire un seul passage dans chaque tableau pour obtenir les éléments communs ?

Answer 1

foreach element e in array A
    insert e into hash table H

foreach element e in array B
    if H contains e 
        print e

Cet algorithme est O(N) dans le temps et O(N) dans l'espace.

Pour éviter l'espace supplémentaire, vous pouvez utiliser l'approche basée sur le tri.

Answer 2

La limite inférieure de l'efficacité est O(n) - il faut au moins lire tous les éléments. Il existe donc plusieurs approches :

L'approche la plus simple et la plus stupide

Recherche de chaque élément du tableau 1 dans le tableau 2. Complexité en temps O(n^2).

Approche du tri

Vous devez trier uniquement le tableau 1, puis rechercher les éléments du tableau 2 en utilisant la recherche binaire. Complexité en temps : tri O(nlogn), recherche O(n * logn) = O(nlogn), total O(nlogn).

Approche par hachage

Créer une table de hachage à partir d'un tableau de un éléments. Recherchez les éléments du deuxième tableau dans la table de hachage. La complexité temporelle dépend de la fonction de hachage. Vous pouvez obtenir O(1) pour les recherches dans le cas optimal (tous les éléments auront une valeur de hachage différente), mais O(n) dans le pire des cas (tous les éléments auront la même valeur de hachage). Complexité totale en temps : O(n^x), où x est un facteur d'efficacité de la fonction de hachage (entre 1 et 2).

Certaines fonctions de hachage sont garanties pour construire une table sans collisions. Mais la construction ne prend plus strictement O(1) temps pour chaque élément. Elle sera O(1) dans la plupart des cas, mais si la table est pleine ou si une collision est rencontrée, alors la table doit être réorganisée - ce qui prend O(n) temps. Cela n'arrive pas si souvent, beaucoup moins fréquemment que les ajouts propres. Ainsi, la complexité temporelle AMORTISSÉE est de O(1). Nous ne nous soucions pas du fait que certains ajouts prennent O(n) de temps, tant que la majorité des ajouts prend O(1) de temps.

Mais même ainsi, dans un cas extrême, la table doit être remaniée à chaque insertion, donc la complexité temporelle stricte serait O(n^2).

Answer 3

Il y a quelques méthodes dans certains langages que je connais qui font exactement ce que vous voulez, avez-vous envisagé de regarder certaines de ces implémentations ?

PHP - array_intersect()

$array1 = array("a" => "green", "red", "blue");
$array2 = array("b" => "green", "yellow", "red");
$result = array_intersect($array1, $array2);
print_r($result);

>> green
   red

Java - Liste.retainAll

Collection listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta"));
Collection listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo"));

listOne.retainAll( listTwo );
System.out.println( listOne );

>> dingo, hafil, iga

Answer 4

Puisque cela me semble être un algorithme de chaîne de caractères, je suppose pour le moment qu'il n'est pas possible de trier cette séquence (donc chaîne de caractères). Algorithme de la plus longue séquence commune (LCS)

En supposant que la taille des entrées est constante, le problème est d'une complexité de O(nxm), (longueur des deux entrées).

Answer 5

    public static void main(String[] args) {
        char[] a = {'a', 'b', 'c', 'd'};
        char[] b = {'c', 'd', 'e', 'f'};
        System.out.println(intersect(a, b));
    }

    private static Set<Character> intersect(char[] a, char[] b) {
        Set<Character> aSet = new HashSet<Character>();
        Set<Character> intersection = new HashSet<Character>();
        for (char c : a) {
            aSet.add(c);
        }
        for (char c : b) {
            if (aSet.contains(c)) {
                intersection.add(c);
            }
        }
        return intersection;
    }