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

Question

Я пытаюсь сделать то, что, по моему мнению, является «de-intersect» (я не уверен, что такое собственное имя, но это то, что назвал его Тим Суини из 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

С пересекаться это будет сделано так:

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

Answer 2

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

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

UPDATE:

я получил немного времени, чтобы попробовать это в коде. Я использовал HashSet<T> с набором 50000 строк, от 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 3

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

Answer 4

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

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

Answer 5

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