Удаление дубликатов без Linq для IList из IList

Question

Что является наиболее эффективным способом удаления дубликатов в IList в C# без Linq

У меня есть следующий код от другого SO [1],

IList<IList<int>> output = new List<IList<int>>(); 
var lists = output; 
for (int i = 0; i < lists.Count; ++i) 
{ 
    //since we want to compare sequecnes, we shall ensure the same order of the items 
    var item = lists[i].OrderBy(x => x).ToArray(); 
    for (int j = lists.Count - 1; j > i; --j) 
     if (item.SequenceEqual(lists[j].OrderBy(x => x))) 
      lists.RemoveAt(j); 
} 

Я использую это в более сложной задаче кодирования и без Linq или синтаксических сахаров, я пытаюсь понять, есть ли какое-нибудь элегантное/быстрое решение?

Я думаю, что просто использую Hash, но я не уверен, какую функцию Hashing использовать для определения того, что List уже доступен?

Более четко Для входа как

{{1,2,4, 4}, {3,4,5}, {4,2,1,4} }

Промежуточный Выход [Сортировано вход/выход отлично]

{{1,2,4,4}, {3,4,5}, {1,2,4,4} }

Выход:

{{1,2,4,4}, {3,4,5}}

Answer 1

Я использовал модифицированную версию внутренностей CollectionAssert.AreEquivalent от Microsoft:

using System.Collections.Generic; 

public class Program 
{ 
    public static void Main() 
    { 
     var lists = new List<List<int>> 
     { 
      new List<int> {1, 4, 2}, 
      new List<int> {3, 4, 5}, 
      new List<int> {1, 2, 4} 
     }; 

     var dedupe = 
      new List<List<int>>(new HashSet<List<int>>(lists, new MultiSetComparer<int>())); 
    } 

    // Equal if sequence contains the same number of items, in any order 
    public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>> 
    { 
     public bool Equals(IEnumerable<T> first, IEnumerable<T> second) 
     { 
      if (first == null) 
       return second == null; 

      if (second == null) 
       return false; 

      if (ReferenceEquals(first, second)) 
       return true; 

      // Shortcut when we can cheaply look at counts 
      var firstCollection = first as ICollection<T>; 
      var secondCollection = second as ICollection<T>; 
      if (firstCollection != null && secondCollection != null) 
      { 
       if (firstCollection.Count != secondCollection.Count) 
        return false; 

       if (firstCollection.Count == 0) 
        return true; 
      } 

      // Now compare elements 
      return !HaveMismatchedElement(first, second); 
     } 

     private static bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second) 
     { 
      int firstNullCount; 
      int secondNullCount; 

      // Create dictionary of unique elements with their counts 
      var firstElementCounts = GetElementCounts(first, out firstNullCount); 
      var secondElementCounts = GetElementCounts(second, out secondNullCount); 

      if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count) 
       return true; 

      // make sure the counts for each element are equal, exiting early as soon as they differ 
      foreach (var kvp in firstElementCounts) 
      { 
       var firstElementCount = kvp.Value; 
       int secondElementCount; 
       secondElementCounts.TryGetValue(kvp.Key, out secondElementCount); 

       if (firstElementCount != secondElementCount) 
        return true; 
      } 

      return false; 
     } 

     private static Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount) 
     { 
      var dictionary = new Dictionary<T, int>(); 
      nullCount = 0; 

      foreach (T element in enumerable) 
      { 
       if (element == null) 
       { 
        nullCount++; 
       } 
       else 
       { 
        int num; 
        dictionary.TryGetValue(element, out num); 
        num++; 
        dictionary[element] = num; 
       } 
      } 

      return dictionary; 
     } 

     public int GetHashCode(IEnumerable<T> enumerable) 
     { 
      int hash = 17; 
      // Create and sort list in-place, rather than OrderBy(x=>x), because linq is forbidden in this question 
      var list = new List<T>(enumerable); 
      list.Sort(); 
      foreach (T val in list) 
       hash = hash * 23 + (val == null ? 42 : val.GetHashCode()); 

      return hash; 
     } 
    } 
} 

Это использует Hashset<T>, добавив к этой коллекции автоматически игнорирует дубликаты.

Последняя строка может прочитать:

var dedupe = new HashSet<List<int>>(lists, new MultiSetComparer<int>()).ToList(); 

Технически, которая использует System.Linq пространство имен, но я не думаю, что это ваша проблема с Linq.

Я буду эхом, что сказал Эрик Липперт. Вы просите нас показать вам необработанные работы Linq и внутренности каркаса, но это не закрытая коробка. Кроме того, если вы думаете, что просмотр исходного кода этих методов выявит очевидную неэффективность и возможности для оптимизации, то я часто нахожу это не так просто, что вам лучше читать документы и измерять.

Answer 2

Я думаю, что это было бы намного проще, чем принятый ответ, и он вообще не использует пространство имен System.Linq.

public class Program 
{ 
    public static void Main() 
    { 
     IList<IList<int>> lists = new List<IList<int>> 
     { 
      new List<int> {1, 2, 4, 4}, 
      new List<int> {3, 4, 5}, 
      new List<int> {4, 2, 1, 4}, 
      new List<int> {1, 2, 2}, 
      new List<int> {1, 2}, 
     }; 

     // There is no Multiset data structure in C#, but we can represent it as a set of tuples, 
     // where each tuple contains an item and the number of its occurrences. 

     // The dictionary below would not allow to add the same multisets twice, while keeping track of the original lists. 
     var multisets = new Dictionary<HashSet<Tuple<int, int>>, IList<int>>(HashSet<Tuple<int, int>>.CreateSetComparer()); 
     foreach (var list in lists) 
     { 
      // Count the number of occurrences of each item in the list. 
      var set = new Dictionary<int, int>(); 
      foreach (var item in list) 
      { 
       int occurrences; 
       set[item] = set.TryGetValue(item, out occurrences) ? occurrences + 1 : 1; 
      } 

      // Create a set of tuples that we could compare. 
      var multiset = new HashSet<Tuple<int, int>>(); 
      foreach (var kv in set) 
      { 
       multiset.Add(Tuple.Create(kv.Key, kv.Value)); 
      } 

      if (!multisets.ContainsKey(multiset)) 
      { 
       multisets.Add(multiset, list); 
      } 
     } 

     // Print results. 
     foreach (var list in multisets.Values) 
     { 
      Console.WriteLine(string.Join(", ", list)); 
     } 
    } 
} 

И выход будет:

1, 2, 4, 4 
3, 4, 5 
1, 2, 2 
1, 2