C# Словарь с HashSet <int> как значение получить пересечение всех

Question

У меня есть словарь с HashSet как значение. У меня есть int [] с ключами, для которых я хочу получить Count общих значений в HashSet.

Вот фрагмент кода, который работает очень неэффективно, так как требуется создать HashSet и изменить его в памяти перед окончательным Count.

 Dictionary<int, HashSet<int>> d = new Dictionary<int, HashSet<int>>(); 

     HashSet<int> s1 = new HashSet<int>() { 3, 4, 5, 6, 7, 8, 9 }; 
     HashSet<int> s2 = new HashSet<int>() { 1, 2, 3, 4, 5, 8 }; 
     HashSet<int> s3 = new HashSet<int>() { 1, 3, 5, 10, 15, 20 }; 
     HashSet<int> s4 = new HashSet<int>() { 1, 20 }; 

     d.Add(10, s1); 
     d.Add(15, s2); 
     d.Add(20, s3); 
     d.Add(25, s4); 

     // List of keys from which I need the intersection of the HashSet's 
     int[] l = new int[3] { 10, 15, 20 }; 

     // Get an IEnumerator with the HashSet from the values of the selected Dictionary entries (10,15,20 selects s1, s2 and s3) 
     var hashlist = d.Where(x => l.Contains(x.Key)); 

     // Create a new HashSet to contain the intersection of all the HashSet's 
     HashSet<int> first = new HashSet<int>(hashlist.First().Value); 
     foreach (var hash in hashlist.Skip(1)) 
      first.IntersectWith(hash.Value); 

     // Show the number of common int's 
     Console.WriteLine("Common elements: {0}", first.Count); 

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

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

Лучшие regargs, Jorge

Answer 1

`IntersectWith()», вероятно, столь же эффективным, как вы можете получить.

Использование LINQ можно сделать код понятнее (?):

var result = l.Aggregate(null, (acc, key) => acc == null? d[key] : acc.Intersect(d[key])); 

Answer 2

Это, безусловно, может быть улучшена:

var hashlist = d.Where(x => l.Contains(x.Key)); 

Переписывая как:

var hashlist = l.Select(x => d[x]); 

Это займет преимущество Dictionary's HashSet для эффективного получения значения на s вместо повторного повторения по int[].

Ваша следующая большая проблема в том, что Linq is lazy, поэтому по телефону Fist() и Skip(1) отдельно, вы на самом деле требует несколько перечислений над коллекцией, используя ранее упомянутый Where(…) фильтр.

Чтобы избежать многочисленных перечислений, можно переписать так:

HashSet<int> first = new HashSet<int>(hashlist.First().Value); 
foreach (var hash in hashlist.Skip(1)) 
    first.IntersectWith(hash.Value); 

В:

var intersection = hashlist.Aggregate(
    (HashSet<int>)null, 
    (h, j) => 
    { 
     if (h == null) 
      h = new HashSet<int>(j); 
     else 
      h.IntersectWith(j); 
     return h; 
    }); 

Но в зависимости от вашего точного случая использования это может быть просто быстрее (и легче понять) просто сначала произведите результат в List, затем используйте простую петлю for:

var hashlist = l.Select(x => d[x]).ToList(); 

HashSet<int> first = hashlist[0]; 
for (var i = 0; i < hashlist.Count; i++) 
    first.IntersectWith(hashlist[i]); 

Вот быстрый тест с этими различными вариантами (ваши результаты могут отличаться):

Original  2.285680 (ms) 
SelectHashList 1.912829 
Aggregate  1.815872 
ToListForLoop 1.608565 
OrderEnumerator 1.975067 // Scott Chamberlain's answer 
EnumeratorOnly 1.732784 // Scott Chamberlain's answer without the call to OrderBy() 
AggIntersect 2.046930 // P. Kouvarakis's answer (with compiler error fixed) 
JustCount  1.260448 // Ivan Stoev's updated answer 

Answer 3

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

Кроме того, если вы вручную создать свой IEnumerable вместо того, чтобы использовать foreach вам не нужно перечислять список дважды (EDIT: также использовать трюк p.s.w.g mentioned, выберите против словаря вместо использования .Contains().

Важное примечание: этот метод только даст вам преимущества, если вы комбинируя большое количество HashSets с широким диапазоном числа элементов. Накладные расходы на вызов OrderBy будут значительными и в небольшом наборе данных, как у вас в вашем примере, и маловероятно, что вы увидите какую-либо выгоду.

Dictionary<int, HashSet<int>> d = new Dictionary<int, HashSet<int>>(); 

HashSet<int> s1 = new HashSet<int>() { 3, 4, 5, 6, 7, 8, 9 }; 
HashSet<int> s2 = new HashSet<int>() { 1, 2, 3, 4, 5, 8 }; 
HashSet<int> s3 = new HashSet<int>() { 1, 3, 5, 10, 15, 20 }; 
HashSet<int> s4 = new HashSet<int>() { 1, 20 }; 

d.Add(10, s1); 
d.Add(15, s2); 
d.Add(20, s3); 
d.Add(25, s4); 

// List of keys from which I need the intersection of the HashSet's 
int[] l = new int[3] { 10, 15, 20 }; 

HashSet<int> combined; 
//Sort in increasing order by count 
//Also used the trick from p.s.w.g's answer to get a better select. 
IEnumerable<HashSet<int>> sortedList = l.Select(x => d[x]).OrderBy(x => x.Count); 

using (var enumerator = sortedList.GetEnumerator()) 
{ 
    if (enumerator.MoveNext()) 
    { 
     combined = new HashSet<int>(enumerator.Current); 
    } 
    else 
    { 
     combined = new HashSet<int>(); 
    } 

    while (enumerator.MoveNext()) 
    { 
     combined.IntersectWith(enumerator.Current); 
    } 
} 


// Show the number of common int's 
Console.WriteLine("Common elements: {0}", combined.Count); 

Answer 4

То, что я ищу является эффективным способом (LinQ возможно?), Чтобы графа общих элементов

Если вы действительно хотите максимальную производительность, забыть о LINQ, здесь это старый школьный путь со всеми возможными оптимизациями (что я могу придумать):

// Collect the non empty matching sets, keeping the set with the min Count at position 0 
var sets = new HashSet<int>[l.Length]; 
int setCount = 0; 
foreach (var key in l) 
{ 
    HashSet<int> set; 
    if (!d.TryGetValue(key, out set) || set.Count == 0) continue; 
    if (setCount == 0 || sets[0].Count <= set.Count) 
     sets[setCount++] = set; 
    else 
    { 
     sets[setCount++] = sets[0]; 
     sets[0] = set; 
    } 
} 
int commonCount = 0; 
if (setCount > 0) 
{ 
    if (setCount == 1) 
     commonCount = sets[0].Count; 
    else 
    { 
     foreach (var item in sets[0]) 
     { 
      bool isCommon = true; 
      for (int i = 1; i < setCount; i++) 
       if (!sets[i].Contains(item)) { isCommon = false; break; } 
      if (isCommon) commonCount++; 
     } 
    } 
} 
Console.WriteLine("Common elements: {0}", commonCount); 

Надеюсь, что код сам пояснительный.