Более быстрый способ сделать Список <T>.Contains ()

Эту операцию можно назвать симметричным различием.

Вам нужна другая структура данных, как хеш-таблица. Добавьте пересечение обоих множеств к нему, затем различие пересечение от каждого набора.

ОБНОВЛЕНИЕ:

Я заставил немного времени пробовать это в коде. Я использовал HashSet<T> с рядом 50 000 строк, от 2 до 10 символов в длину со следующими результатами:

Исходный: 79 499 мс

Hashset: 33 мс

BTW, на названном HashSet существует метод SymmetricExceptWith то, которое я думал, сделает работу для меня, но она на самом деле добавляет различные элементы от обоих наборов до набора, к методу обращаются. Возможно, это - то, что Вы хотите, вместо того, чтобы оставить начальные два набора неизмененными, и код был бы более изящным.

Вот код:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        // foo and bar have some identical elements (given a case-insensitive match)
        var foo = getRandomStrings();
        var bar = getRandomStrings();

        var timer = new Stopwatch();

        timer.Start();
        // remove non matches
        var f = foo.Where(x => !bar.Contains(x)).ToList();
        var b = bar.Where(x => !foo.Contains(x)).ToList();
        timer.Stop();

        Debug.WriteLine(String.Format("Original: {0} ms", timer.ElapsedMilliseconds));

        timer.Reset();

        timer.Start();
        var intersect = new HashSet<String>(foo);
        intersect.IntersectWith(bar);

        var fSet = new HashSet<String>(foo);
        var bSet = new HashSet<String>(bar);

        fSet.ExceptWith(intersect);
        bSet.ExceptWith(intersect);
        timer.Stop();

        var fCheck = new HashSet<String>(f);
        var bCheck = new HashSet<String>(b);

        Debug.WriteLine(String.Format("Hashset: {0} ms", timer.ElapsedMilliseconds));

        Console.WriteLine("Sets equal? {0} {1}", fSet.SetEquals(fCheck), bSet.SetEquals(bCheck)); //bSet.SetEquals(set));
        Console.ReadKey();
    }

    static Random _rnd = new Random();

    private const int Count = 50000;

    private static List<string> getRandomStrings() 
    {
        var strings = new List<String>(Count);

        var chars = new Char[10];

        for (var i = 0; i < Count; i++)
        {
            var len = _rnd.Next(2, 10);

            for (var j = 0; j < len; j++)
            {
                var c = (Char)_rnd.Next('a', 'z');
                chars[j] = c;
            }

            strings.Add(new String(chars, 0, len));
        }

        return strings;
    }
}

С отсортированным списком можно использовать двоичный поиск.

Если элементы уникальны в рамках каждого списка, необходимо рассмотреть использование HashSet

HashSet (T) класс обеспечивает высокопроизводительные операции присвоения. Набор является набором, который не содержит дублирующихся элементов, и чьи элементы без определенного порядка.

Содержит в списке, O (N) операция. Если бы у Вас была другая структура данных, такая как отсортированный список или Словарь, то Вы существенно уменьшили бы свое время. Доступ к ключу в отсортированном списке обычно O (зарегистрируйте N), время, и в хеше обычно O (1) время.