Comment trouver si un élément d'une liste se trouve dans une autre liste?

Question

Je veux savoir si au moins un élément d'une première liste peut être trouvé dans une deuxième liste.

Je vois deux façons de le faire. Disons que nos listes sont :

List list1 = new[] { "A", "C", "F", "H", "I" };
List list2 = new[] { "B", "D", "F", "G", "I" };

La première approche utilise une boucle :

bool isFound = false;
foreach (item1 in list1)
{
    if (list2.Contains(item1))
    {
        isFound = true;
        break;
    }
}

La deuxième utilise directement Linq :

bool isFound = list1.Intersect(list2).Any();

La première est longue à écrire et pas très directe / facile à lire. La deuxième est courte et claire, mais les performances seront faibles, surtout sur de grandes listes.

Quelle pourrait être une manière élégante de le faire ?

Answer 1

Le second a de meilleures performances sur de grandes listes que le premier. Intersect place les éléments d'une liste dans une table de hachage avant de vérifier si les éléments de l'autre liste sont membres.

Answer 2

Il semble étrange de critiquer les performances de LINQ lorsque l'original est clairement (dans le pire des cas) O(n*m); l'approche LINQ utiliserait, je m'attends, un HashSet sur une liste, puis utiliserait un bloc d'itérateur en continu - donc les performances devraient être O(n+m) - c'est-à-dire mieux.

Answer 3

Je pense que le deuxième sera plus rapide pour les grandes listes. Puisque le premier est en O (list1.Count*list2.Count) tandis que le deuxième est en O (list1.Count+list2.Count). Le deuxième prend cependant plus de mémoire.

Et le surcoût de Linq est généralement un facteur de multiplication constant par rapport au code artisanal. Je suppose que le deuxième est plus lent que le code impératif d'au plus un facteur de deux, probablement même moins. Il utilise O(list1.Count+list2.Count) mémoire qui peut être réduite à O(min(list1, list2)) si vous écrivez soigneusement votre code pour une utilisation optimale de la mémoire tout en conservant des performances linéaires.

Ce code devrait être relativement rapide sur de grandes listes :

bool isFound = false;
HashSet set2=new HashSet(list2);
foreach (item1 in list1)
{
    if (set2.Contains(item1))
    {
        isFound = true;
        break;
    }
}

Vous pouvez optimiser ce code davantage en transformant la plus petite liste en un hashset au lieu d'utiliser toujours list2.

Answer 4

La réponse acceptée est super, cependant elle ne fonctionne pas avec Linq-to-sql, car il n'y a pas de mapping pour Intersect. Dans ce cas, vous devriez utiliser :

bool isFound = table.Any(row => list2.Contains(row.FieldWithValue));

Ceci est compilé en WHERE EXSITS

Answer 5

Ceci est une autre façon de savoir si un élément d'une liste existe dans une autre liste.

bool present = List1.Any(t => List2.Any(y => y == t));