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

Question

Я пытаюсь сделать то, что я считаю «де-пересечением» (я не уверен, как правильно назвать это имя, но именно так его назвал Тим Суини из EpicGames в старом UnrealEd)

// foo and bar have some identical elements (given a case-insensitive match)
List‹string› foo = GetFoo();
List‹string› bar = GetBar();

// remove non matches
foo = foo.Where(x => bar.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList();
bar = bar.Where(x => foo.Contains(x, StringComparer.InvariantCultureIgnoreCase)).ToList();

Затем я сделаю еще одну вещь, где вычту результат из оригинала, чтобы посмотреть, какие элементы я удалил. Это очень быстро с использованием .Except (), так что никаких проблем нет.

Должен быть более быстрый способ сделать это, потому что этот довольно плохо работает с ~ 30 000 элементов (из строки) в любом списке. Желательно, чтобы метод, выполняющий этот шаг, а потом - одним махом, был бы хорош. Я пытался использовать .Exists () вместо .Contains (), но это немного медленнее. Я чувствую себя немного толстым, но я думаю, что это должно быть возможно с некоторой комбинацией .Except () и .Intersect () и / или .Union ().

Answer 1

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

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

UPDATE:

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

Оригинал : 79499 мс

Hashset : 33 мс

Кстати, в 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;
    }
}

Answer 2

С пересечением это будет сделано так:

var matches = ((from f in foo 
                select f)
              .Intersect(
                  from b in bar 
                  select b, StringComparer.InvariantCultureIgnoreCase))

Answer 3

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

Answer 4

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

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

Answer 5

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