Как создать HashSet <List <Int>> с различными элементами? - PullRequest
Новая
       26

Как создать HashSet <List <Int>> с различными элементами?

7 голосов
/ 01 апреля 2011

У меня есть HashSet, который содержит несколько списков целых чисел - т.е. HashSet<List<int>>

Чтобы сохранить уникальность, мне нужно сделать две вещи: 1. Вручную зациклите существующие списки в поисках дубликатов, используя SequenceEquals. 2. Сортировка отдельных списков так, чтобы SequenceEquals работал в настоящее время.

Есть ли лучший способ сделать это? Существует ли существующий IEqualityComparer, который я могу предоставить HashSet, чтобы HashSet.Add() автоматически обрабатывал уникальность? 

var hashSet = new HashSet<List<int>>();

for(/* some condition */)
{
    List<int> list = new List<int>();

    ...

    /* for eliminating duplicate lists */

    list.Sort();

    foreach(var set in hashSet)
    {
        if (list.SequenceEqual(set))
        {
            validPartition = false;
            break;
        }
    }

    if (validPartition)
           newHashSet.Add(list);
}

Спасибо!

Ответы [ 4 ]

4 голосов
/ 02 апреля 2011

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

2 голосов
/ 02 апреля 2011

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

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

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

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

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
   } 
}

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

2 голосов
/ 02 апреля 2011

Вот возможный компаратор, который сравнивает 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();
}
0 голосов
/ 01 апреля 2011

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

...