Comparaison des éléments communs entre les deux listes

Question

Étant donné deux listes d'entrée, comment puis-je créer une liste des éléments qui sont communs aux deux entrées ?

Par exemple : pour les entrées [1,2,3,4,5,6] y [3,5,7,9] le résultat devrait être [3, 5] ; pour les entrées ['this','this','n','that'] y ['this','not','that','that'] le résultat devrait être ['this', 'that'] .

---

_{<p><strong>Voir aussi</strong></p><ul><li><a href="https://stackoverflow.com/questions/18264471/">En Python, comment trouver des mots communs dans deux listes tout en préservant l'ordre des mots ? </a>(pour maintenir l'ordre)</li><li><a href="https://stackoverflow.com/questions/3852780/">Python -Intersection de plusieurs listes ? </a>(pour calculer l'intersection entre >= 3 listes)</li><li><a href="https://stackoverflow.com/questions/37645053/">Intersection de deux listes comprenant des doublons ? </a>(pour conserver les éléments en double)</li></ul>}

Answer 1

Set est un autre moyen de résoudre ce problème

a = [3,2,4]
b = [2,3,5]
set(a)&set(b)
{2, 3}

Answer 2

J'ai comparé chacune des méthodes mentionnées dans les réponses. Pour l'instant, j'utilise python 3.6.3 pour cette implémentation. Voici le code que j'ai utilisé :

import time
import random
from decimal import Decimal

def method1():
    common_elements = [x for x in li1_temp if x in li2_temp]
     print(len(common_elements))

def method2():
    common_elements = (x for x in li1_temp if x in li2_temp)
    print(len(list(common_elements)))

def method3():
    common_elements = set(li1_temp) & set(li2_temp)
    print(len(common_elements))

def method4():
    common_elements = set(li1_temp).intersection(li2_temp)
    print(len(common_elements))

if __name__ == "__main__":
    li1 = []
    li2 = []
    for i in range(100000):
        li1.append(random.randint(0, 10000))
        li2.append(random.randint(0, 10000))

    li1_temp = list(set(li1))
    li2_temp = list(set(li2))

    methods = [method1, method2, method3, method4]
    for m in methods:
        start = time.perf_counter()
        m()
        end = time.perf_counter()
        print(Decimal((end - start)))

Si vous exécutez ce code, vous pouvez voir que si vous utilisez une liste ou un générateur (si vous itérez sur le générateur, et non pas si vous l'utilisez simplement). C'est ce que j'ai fait lorsque j'ai forcé le générateur à imprimer sa longueur), vous obtenez pratiquement les mêmes performances. Mais si vous utilisez set, vous obtenez de bien meilleures performances. De même, si vous utilisez la méthode de l'intersection, vous obtiendrez des performances légèrement supérieures. Le résultat de chaque méthode sur mon ordinateur est listé ci-dessous :

1. method1: 0.8150673999999999974619413478649221360683441
2. method2: 0.8329545000000001531148541289439890533685684
3. method3: 0.0016547000000000089414697868051007390022277
4. method4: 0.0010262999999999244948867271887138485908508

Answer 3

Les réponses précédentes permettent toutes de trouver les éléments communs uniques, mais ne tiennent pas compte des éléments répétés dans les listes. Si vous voulez que les éléments communs apparaissent dans le même nombre qu'ils sont communs dans les listes, vous pouvez utiliser la réponse suivante :

l2, common = l2[:], [ e for e in l1 if e in l2 and (l2.pop(l2.index(e)) or True)]

En or True n'est nécessaire que si l'on s'attend à ce qu'un élément soit évalué à False .

Answer 4

1) Méthode1 sauvegarde de list1 comme dictionnaire et itération de chaque élément de list2

def findarrayhash(a,b):
    h1={k:1 for k in a}
    for val in b:
        if val in h1:
            print("common found",val)
            del h1[val]
        else:
            print("different found",val)
    for key in h1.iterkeys():
        print ("different found",key)

Trouver des éléments communs et différents :

2) Méthode2 en utilisant l'ensemble

def findarrayset(a,b):
    common = set(a)&set(b)
    diff=set(a)^set(b)
    print list(common)
    print list(diff)

Answer 5

Il existe des solutions qui permettent d'atteindre cet objectif en O(l1+l2) sans tenir compte des éléments répétitifs, et des solutions plus lentes (au moins O(l1*l2), mais probablement plus coûteuses) qui prennent en compte les éléments répétitifs.

Je me suis donc dit qu'il fallait ajouter une solution O(l1*log(l1)+l2*(log(l2)). Cette solution est particulièrement utile si les listes sont déjà triées.

def common_elems_with_repeats(first_list, second_list):
    first_list = sorted(first_list)
    second_list = sorted(second_list)
    marker_first = 0
    marker_second = 0
    common = []
    while marker_first < len(first_list) and marker_second < len(second_list):
        if(first_list[marker_first] == second_list[marker_second]):
            common.append(first_list[marker_first])
            marker_first +=1
            marker_second +=1
        elif first_list[marker_first] > second_list[marker_second]:
            marker_second += 1
        else:
            marker_first += 1
    return common

Une autre solution plus rapide consisterait à créer une carte item->count à partir de la liste 1, et à parcourir la liste 2, tout en mettant à jour la carte et en comptant les dups. Cela ne nécessiterait pas de tri. Il faudrait un peu plus de mémoire, mais c'est techniquement O(l1+l2).