14

I have a HashSet that contains multiple lists of integers - i.e. HashSet<List<int>>

In order to maintain uniqueness I am currently having to do two things: 1. Manually loop though existing lists, looking for duplicates using SequenceEquals. 2. Sorting the individual lists so that SequenceEquals works currently.

Is there a better way to do this? Is there an existing IEqualityComparer that I can provide to the HashSet so that HashSet.Add() can automatically handle uniqueness?

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);
}
8
  • 1
    Check Jon Skeet's answer here: stackoverflow.com/questions/1023424/… Apr 1, 2011 at 19:34
  • 1
    Could you provide more info on what problem you are actually trying to solve? HashSet<List<int>> seems like an unlikely tool to use.
    – marcind
    Apr 1, 2011 at 20:19
  • @marcind, I am using it to maintain a list of all factorizations of a number.. so for 24 you can have for example {4, 2, 3} , {2, 2, 6} etc... the algorithm I use at the moment creates duplicate sets, I wish I knew how to solve THAT problem, but sadly I dont :-/
    – Preets
    Apr 1, 2011 at 20:51
  • You might want to ask that as a separate question. There should be a more elegant solution than what you're currently trying. Apr 1, 2011 at 20:55
  • @CodeInChaos, yup, I definitely think I should ! Any solution will be more elegant than the mess I've got going at the moment ;-)
    – Preets
    Apr 1, 2011 at 20:59

5 Answers 5

9

Here is a possible comparer that compares an IEnumerable<T> by its elements. You still need to sort manually before adding.

One could build the sorting into the comparer, but I don't think that's a wise choice. Adding a canonical form of the list seems wiser.

This code will only work in .net 4 since it takes advantage of generic variance. If you need earlier versions you need to either replace IEnumerable with List, or add a second generic parameter for the collection type.

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 = unchecked(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();
}
12
  • @downvoter Could you explain what the problem with this solution is, so I can fix/improve it? Apr 1, 2011 at 20:38
  • (not my downvote) Pretty close but missing the sort either before the add or in Equals
    – Rune FS
    Apr 1, 2011 at 20:39
  • That's why I explained in the beginning that he still needs to sort manually. Apr 1, 2011 at 20:41
  • @CodeInChaose I agree with the design choice you outline. Seems a waste to sorte all the already sorted lists. It was a comment to your (now updated) Main(). (and to me that wasn't worth downvoting for in the first place)
    – Rune FS
    Apr 1, 2011 at 20:47
  • Having the .Sort() in Main illustrates better how to use it. So that was a good suggestion :) Apr 1, 2011 at 20:50
7

This starts off wrong, it has to be a HashSet<ReadOnlyCollection<>> because you cannot allow the lists to change and invalidate the set predicate. This then allows you to calculate a hash code in O(n) when you add the collection to the set. And an O(n) test to check if it is already in the set with a very uncommon O(n^2) worst case if all the hashes turn out to be equal. Store the computed hash with the collection.

3
  • It's not like ReadOnlyCollection guarantees immutability. And if this set isn't exposed in a public API mutability doesn't matter. Storing the computed hash isn't that important either, since I think HashSet<T> already stores the hashes for the elements it already contains. Apr 1, 2011 at 20:34
  • A ReadOnlyCollection<int> does. Whether to store it or to create a derived class that overrides Equals+GetHashCode is up to the OP. Apr 1, 2011 at 20:41
  • 1
    What I meant is that if you don't create the ReadOnlyCollection yourself an outsider still has the reference to the underlying IList and can change that list, which is then reflected in the ReadOnlyCollection. If you control the creation of the ReadOnlyCollection you can guarantee (shallow) immutability. (And on int deep immutability) Apr 1, 2011 at 20:46
1

Is there a reason you aren't just using an array? int[] will perform better. Also I assume the lists contain duplicates, otherwise you'd just be using sets and not have a problem.

It appears that their contents won't change (much) once they've been added to the HashSet. At the end of the day, you are going to have to use a comparer that falls back on SequenceEqual. But you don't have to do it every single time. Instead or doing an exponential number of sequence compares (e.g. -- as the hashset grows, doing a SequenceEqual against each existing member) -- if you create a good hashcode up front, you may have to do very few such compares. While the overhead of generating a good hashcode is probably about the same as doing a SequenceEqual you're only doing it a single time for each list.

So, the first time you operate on a particular List<int>, you should generate a hash based on the ordered sequence of numbers and cache it. Then the next time the list is compared, the cached value can be used. I'm not sure how you might do this with a comparer off the top of my head (maybe a static dictionary?) -- but you could implement List wrapper that does this easily.

Here's a basic idea. You'd need to be careful to ensure that it isn't brittle (e.g. make sure you void any cached hash code when members change) but it doesn't look like that's going to be a typical situation for the way you're using 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
   } 
}

If the lists won't change once added, this should be very fast. Even in situations where the lists could change frequently, the time to create a new hash code is not likely very different (if even greater at all) than doing a sequence compare.

2
  • 1
    No particular reason to use List<>, I did not know about int[]s performing better. Thanks! And your assumption is correct, the lists do include duplicates, which is why I do not use sets.
    – Preets
    Apr 1, 2011 at 22:28
  • Generally a simpler construct is probably going to be faster than a more complex one, unless you're doing something that depends on some aspect of that complex structure (e.g. a linked list will be much faster to insert items than a non-linked list). The long and short of my long winded response is that you should use a construct that can cache hash codes. Since it's expensive to compare lists or create something that can uniquely identify one, and you're doing it lots of times on the same objects, just set something up that will remember that unique ID. Apr 1, 2011 at 22:34
0

If you don't specify an IEQualityComparer, then the types default will be used, so I think what you'll need to do is create your own implementation of IEQualityComparer, and pass that to the constructor of your HashSet. Here is a good example.

-1

When comparing hashsets of lists one option you always have is that instead of comparing each element, you sort lists and join them using a comma and compare generated strings.

So, in this case, when you create custom comparer instead of iterating over elements and calculating custom hash function, you can apply this logic.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.