Как получить из списка элементы которые не повторяются в другом списке?

Question

Какой лучший (быстрее) способ получить из List<string> элементы - которые не повторяются в другом List<string> ?

UPD - код

        List<string> spisok1 = new(); // 25кк элементов
        List<string> spisok2 = new(); // 200к элементов

        foreach (var itemSpiska2 in spisok2)
        {
            for (int i = 0; i < spisok1.Count; i++)
            {
                if (spisok1[i] == itemSpiska2)
                {
                    spisok1[i] = "";
                    break;
                }
            }
        }

        foreach (string itemSpiska1 in spisok1)
        {
            if (itemSpiska1?.Length != 0)
            {
                // Забрать элемент
            }
        }

UPD - ответы на вопросы aepot

Пожалуйста дополните вопрос: 1) Как вы измеряли произодительность, что такое для вас "медленно" или "плохо"? 2) Что такое "быстрее"? Быстрее чем что? 3) Как вообще до такого дошло, что 25кк строковых элементов в список попали? Какую задачу вы решаете?

По ощущениям
Быстрее - значительней быстрее чем сейчас
Это не так, но так объясню для простоты. Представим что 25кк это id вконтакте Вот в spisok1 все необходимые для отработки id, а в spisok2 когда то отработанные id. Вот и надо как то убрать / пометить в spisok1 ранее отработанные и взять потом часть не отработаннх xD

Answer 1

Попробуйте так

list1.RemoveAll(x => list2.Contains(x));

У меня в тесте list1 - 25к элементов, list2 - 2к элементов выполнилось за 1,97 сек.

UPD

Справедливости ради, при list1 = 25к, list2 = 20к у меня отрабатывает за 15с. Если использовать Except, как предложили выше

List<string> list3 = list1.Except(list2).ToList()

отрабатывает за 30мс, что в 500 раз быстрее.

Answer 2

Можно всё сделать короче:

List<string> spisok1 = new(); // 25кк элементов
List<string> spisok2 = new(); // 200к элементов
var spisok3 = spisok1.Except(spisok2).ToList();

У меня отрабатывает секунд за 6, насколько быстрее Вам надо?

UPD: Добавил пример, который отрабатывает за 6 секунд.

List<string> main = new List<string>();
List<string> slave = new List<string>(); 
for (int i = 0; i < 25000000; i++)
{
    main.Add(i.ToString());
}
for (int i = 29999970; i < 50000000; i++)
{
    slave.Add(i.ToString());
}
var final = main.Except(slave).ToList();

UPD2: Данный метод ресурсозатратен.

UPD3: Тест производительности от @aepot

class Program
{
    static void Main(string[] args)
    {
        var result = BenchmarkRunner.Run<ListTest>();
        Console.ReadKey();
    }
}

[MemoryDiagnoser]
public class ListTest
{
    readonly List<string> list1 = Enumerable.Range(1, 25000000).Select(i => "id" + i).ToList();
    readonly List<string> list2 = Enumerable.Range(123456, 200000).Select(i => "id" + (i * 3)).ToList();

    [Benchmark]
    public List<string> ExceptTest()
    {
        return list1.Except(list2).ToList();
    }
}

BenchmarkDotNet=v0.13.0, OS=Windows 10.0.19042.985 (20H2/October2020Update)
Intel Core i7-9700K CPU 3.60GHz (Coffee Lake), 1 CPU, 8 logical and 8 physical cores
.NET SDK=5.0.203
  [Host]     : .NET 5.0.6 (5.0.621.22011), X64 RyuJIT
  DefaultJob : .NET 5.0.6 (5.0.621.22011), X64 RyuJIT

Method	Mean	Error	StdDev	Gen 0	Gen 1	Gen 2	Allocated
ExceptTest	5.023 s	0.0129 s	0.0107 s	-	-	-	2 GB

Сравнивать с List.Contains или List.BinarySearch не стал, потому что это долго ждать: они во много раз медленнее, хоть и потребляют значительно меньше памяти.

БЛОГ НА HUSL

Как получить из списка элементы которые не повторяются в другом списке?

Ответы (2 шт):