Algorithme efficace d'intersection des listes

avec deux listes (pas nécessairement triées), Quel est l'algorithme non récursif le plus efficace pour trouver l'intersection de ces listes?

70
demandé sur mwfearnley 2009-01-31 00:35:40

15 réponses

vous pouvez mettre tous les éléments de la première liste dans un jeu de hachage. Ensuite, itérez le second et, pour chacun de ses éléments, vérifiez le hachage pour voir s'il existe dans la première liste. Si oui, sortie comme un élément de l'intersection.

31
répondu Frank 2009-01-30 21:39:46

vous pourriez vouloir jeter un oeil aux filtres de fleur. Ils sont vecteurs de bits qui donnent une réponse probabiliste si un élément est un membre d'un jeu. Set intersection peut être mis en œuvre avec un simple bitwise et l'opération. Si vous avez un grand nombre d'intersections nulles, le filtre de fleur peut vous aider à les éliminer rapidement. Vous aurez toujours besoin de recourir à l'un des autres algorithmes mentionnés ici pour calculer l'intersection réelle, cependant. http://en.wikipedia.org/wiki/Bloom_filter

20
répondu Aneil Mallavarapu 2010-05-23 16:22:00

sans hachage, je suppose que vous avez deux options:

  • la manière naïve va être comparer chaque élément à chaque autre élément. O (N^2)
  • une autre façon serait de trier les listes d'abord, puis de les itérer: O (N lg n) * 2 + 2 * O (n)
9
répondu Tom Ritter 2009-01-30 21:49:10

De la eviews liste des fonctionnalités de il semble qu'il prend en charge complexe des fusions et des jointures (si c'est "rejoindre", comme dans la bd de la terminologie, on va calculer une intersection). Maintenant, fouillez dans votre documentation: -)

en outre, eviews a leur propre forum d'utilisateur-pourquoi ne pas demander there_151930920"

7
répondu zvrba 2010-05-23 16:56:30

avec l'ensemble 1 Construisez un arbre de recherche binaire avec O(log n) et itérez set2 et recherchez le BST m X O(log n) ainsi total O(log n) + O(m)+O(log n) ==> O(log n)(m+1)

6
répondu khaja 2012-04-17 07:31:31

en C++ ce qui suit peut être essayé en utilisant la carte STL

vector<int> set_intersection(vector<int> s1, vector<int> s2){

    vector<int> ret;
    map<int, bool> store;
    for(int i=0; i < s1.size(); i++){

        store[s1[i]] = true;
    }
    for(int i=0; i < s2.size(); i++){

        if(store[s2[i]] == true) ret.push_back(s2[i]);

    }
    return ret;
}
6
répondu quasar 2016-02-13 07:07:57

Voici une autre solution possible que j'ai trouvé prend O(nlogn) dans la complexité du temps et sans aucun stockage supplémentaire. Vous pouvez le consulter ici https://gist.github.com/4455373

, Voici comment cela fonctionne: en Supposant que les ensembles ne contiennent pas de répétition, fusionner tous les jeux et de les trier. Puis boucle à travers l'ensemble fusionné et sur chaque itération créer un sous-ensemble entre l'index I et i+n courant où n est le nombre d'ensembles disponible dans l'univers. Ce que nous recherchons en boucle est une séquence répétée de taille n égale au nombre d'ensembles dans l'univers.

Si ce sous-ensemble i est égal à celui sous-ensemble de n, cela signifie que l'élément i est répétée n fois, qui est égal au nombre total de groupes. Et comme il n'y a pas de répétitions dans un ensemble qui signifie que chacun des ensembles contient cette valeur, nous l'ajoutons à l'intersection. Puis on déplace l'indice de i + ce qui reste entre lui et n parce qu'aucun de ces index ne va former une séquence répétitive.

3
répondu Ayman Farhat 2013-01-04 19:55:31

d'abord, trier les deux listes en utilisant quicksort : O(N*log(n). Ensuite, comparez les listes en parcourant d'abord les valeurs les plus basses et ajoutez les valeurs communes. Par exemple, dans lua):

function findIntersection(l1, l2)
    i, j = 1,1
    intersect = {}

    while i < #l1 and j < #l2 do
        if l1[i] == l2[i] then
            i, j = i + 1, j + 1
            table.insert(intersect, l1[i])
        else if l1[i] > l2[j] then
            l1, l2 = l2, l1
            i, j = j, i
        else
            i = i + 1
        end
    end

    return intersect
end

, qui est O(max(n, m))n et m sont les tailles des listes.

EDIT: quicksort est récursive, comme dit dans les commentaires, mais il semble qu'il y a non-récursive implémentations

2
répondu Wookai 2009-01-30 22:00:23

pourquoi ne pas mettre en œuvre votre propre table de hachage simple ou jeu de hachage? Il vaut la peine d'éviter l'intersection de nlogn si vos listes sont grandes comme vous le dites.

puisque vous connaissez un peu vos données à l'avance, vous devriez être en mesure de choisir une bonne fonction de hachage.

1
répondu Imran 2009-01-31 22:39:17

j'appuie l'idée des" décors". Dans JavaScript, vous pouvez utiliser la première liste pour peupler un objet, en utilisant les éléments de liste comme noms. Ensuite, vous utilisez les éléments de liste de la deuxième liste et voir si ces propriétés existent.

1
répondu Nosredna 2009-01-31 22:55:26

S'il y a un support pour sets (comme vous les appelez dans le titre) comme intégré Habituellement il y a une méthode d'intersection.

de toute façon, comme quelqu'un a dit que vous pourriez le faire facilement (Je ne posterai pas de code, quelqu'un l'a déjà fait) si vous avez les listes triées. Si vous ne pouvez pas utiliser la récursion, il n'y a aucun problème. Il existe des implémentations de tri rapide recursion-sans .

1
répondu Andrea Ambu 2011-10-06 18:37:03

en PHP, quelque chose comme

function intersect($X) { // X is an array of arrays; returns intersection of all the arrays
  $counts = Array(); $result = Array();
  foreach ($X AS $x) {
    foreach ($x AS $y) { $counts[$y]++; }
  }
  foreach ($counts AS $x => $count) {
    if ($count == count($X)) { $result[] = $x; }
  }
  return $result;
}
0
répondu 2009-07-16 12:47:07

De la définition de " Big-Oh notation:

T(N) = O(f (N)) s'il existe des constantes positives c et n 0 telles que T(N) ≤ cf (N) Lorsque N ≥ n 0.

ce qui signifie en pratique que si les deux listes sont relativement petites en taille dire quelque chose de moins 100 éléments dans chaque deux pour les boucles fonctionne très bien. Boucle la première liste et cherche un objet similaire dans la seconde. Dans mon cas, ça marche très bien parce que je n'aurai pas plus de 10-20 éléments max dans Mes listes. Cependant, une bonne solution est de trier le premier O(N log n), de trier le second O(N log n) et de les fusionner, un autre O(N log n) à peu près parlant O(3 n log n), dire que les deux listes sont de la même taille.

0
répondu Adelin 2015-10-19 10:08:28

utilisant skip pointers et SSE instructions peut améliorer l'efficacité de l'intersection de liste.

0
répondu Wolf Garbe 2016-06-16 14:11:25

j'ai eu quelques bonnes réponses de ce que vous pouvez être en mesure d'appliquer. Je n'ai pas encore eu la chance de les essayer, mais comme ils couvrent aussi les intersections, vous pourriez les trouver utiles.

-1
répondu StingyJack 2017-05-23 11:54:59