Как создать HashSet‹List‹Int›› с отдельными элементами?

Вот возможный компаратор, который сравнивает IEnumerable<T> по его элементам. Вам все еще нужно отсортировать вручную перед добавлением.

Можно было бы встроить сортировку в компаратор, но я не думаю, что это разумный выбор. Добавление канонической формы списка кажется более разумным.

Этот код будет работать только в .net 4, поскольку он использует общую дисперсию. Если вам нужны более ранние версии, вам нужно либо заменить IEnumerable на List, либо добавить второй общий параметр для типа коллекции.

class SequenceComparer<T>:IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> seq1,IEnumerable<T> seq2)
    {
        return seq1.SequenceEqual(seq2);
    }

    public int GetHashCode(IEnumerable<T> seq)
    {
        int hash=1234567;
        foreach(T elem in seq)
            hash=hash*37+elem.GetHashCode();
        return hash;
    }
}

void Main()
{
    var hashSet = new HashSet<List<int>>(new SequenceComparer<int>());

    List<int> test=new int[]{1,3,2}.ToList();
    test.Sort();
    hashSet.Add(test);

    List<int> test2=new int[]{3,2,1}.ToList();
    test2.Sort();       
    hashSet.Contains(test2).Dump();
}

Это начинается неправильно, это должно быть HashSet<ReadOnlyCollection<>>, потому что вы не можете позволить спискам изменяться и делать предикат set недействительным. Затем это позволяет вам вычислять хэш-код за O (n) при добавлении коллекции в набор. И тест O (n), чтобы проверить, находится ли он уже в наборе с очень необычным наихудшим случаем O (n ^ 2), если все хеши окажутся равными. Сохраните вычисленный хэш вместе с коллекцией.

Есть ли причина, по которой вы не просто используете массив? int[] будет работать лучше. Также я предполагаю, что списки содержат дубликаты, иначе вы бы просто использовали наборы и не имели бы проблем.

Похоже, что их содержимое не изменится (сильно) после того, как они будут добавлены в HashSet. В конце концов, вам придется использовать компаратор, который использует SequenceEqual. Но вам не нужно делать это каждый раз. Вместо этого или выполнения экспоненциального числа сравнений последовательностей (например, по мере роста хеш-набора выполняется SequenceEqual для каждого существующего члена) — если вы создаете хороший хэш-код заранее, вам, возможно, придется делать очень мало таких сравнений. Хотя накладные расходы на создание хорошего хэш-кода, вероятно, примерно такие же, как на создание SequenceEqual, вы делаете это только один раз для каждого списка.

Таким образом, в первый раз, когда вы работаете с определенным List<int>, вы должны сгенерировать хэш на основе упорядоченной последовательности чисел и кэшировать его. Затем при следующем сравнении списка можно будет использовать кэшированное значение. Я не уверен, как вы могли бы сделать это с помощью компаратора (может быть, статического словаря?) - но вы могли бы реализовать оболочку List, которая делает это легко.

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

public class FasterComparingList<T>: IList<T>, IList, ... 
    /// whatever you need to implement
{
   // Implement your interfaces against InnerList
   // Any methods that change members of the list need to
   // set _LongHash=null to force it to be regenerated
   public List<T> InnerList { ... lazy load a List }
   public int GetHashCode()
   {
       if (_LongHash==null) {
           _LongHash=GetLongHash();
       }
       return (int)_LongHash;
   }
   private int? _LongHash=null;
   public bool Equals(FasterComparingList<T> list)
   {
       if (InnerList.Count==list.Count) {
           return true;
       }
       // you could also cache the sorted state and skip this if a list hasn't
       // changed since the last sort
       // not sure if native `List` does
       list.Sort();
       InnerList.Sort();
       return InnerList.SequenceEqual(list);
   }
   protected int GetLongHash()
   {
       return .....
       // something to create a reasonably good hash code -- which depends on the 
       // data. Adding all the numbers is probably fine, even if it fails a couple 
       // percent of the time you're still orders of magnitude ahead of sequence
       // compare each time
   } 
}

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

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

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

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