Runtime: Proposal: Linq extension HasDuplicates() and Duplicates()

[dmcnaughton]

A common scenario that I have come across in projects, as well as having seen others work around, has been dealing with identifying whether a set has duplicates as well as getting the duplicate values/counts.

I've written extensions for projects that utilize the optimized Set internal class that does a fast-return when the first duplicate object is hit for HasDuplicates(), as well as adding an int object to the to the Slot internal class that handles the number of times the object has been added/attempted to be added to the Set.

This would improve performance over the most common way I have seen developers do this:

HasDuplicates
Current workaround:

public static bool HasDuplicates<TSource>(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer){
    return source.Count() == source.Distinct(comparer).Count();
}

Optimized method (using Set):

public static bool HasDuplicates<TSource>(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer){
    var set = new Set<TSource>(comparer);
    foreach (var element in source)
    {
        if (!set.Add(element))
        {
            return true;
        }
     }
     return false;
}

Duplicates
Current workaround:

public static IEnumerable<KeyValuePair<TSource, int>> Duplicates<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer){
    return source.GroupBy(element => element).Select(x =>
                new KeyValuePair<TSource, int>(x.Key, x.Count())).Where(x => x.Value > 1);
}

Optimized method (using modified Set and Slot):

public static IEnumerable<KeyValuePair<TSource, int>> Duplicates<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer){
    var set = new Set<TSource>(comparer);
    foreach(var element in source)
    {
        set.Add(element);
    }
    return set.ToEnumerableWithCount();
}

New method to add to Set

public IEnumerable<KeyValuePair<TElement,int>> ToEnumerableWithCount(){
    return _slots.Where(x => x._count > 1).Select(x =< new KeyValuePair<TElement, int>(x._value, x._count));
}

There would be a couple other changes that would be made to the Add & Remove methods on Set<TSource>, as well as adding the internal int _count property to Slot<TSource>.

[svick]

How much would these additions improve performance? Specifically, I would like to see some benchmarks comparing:

1. Your oneliner "workarounds".
2. Still fairly simple ~10 line methods using HashSet<T> and Dictionary<T, int>.
3. The proposed additions.

Also, can you explain the logic behind the behavior of Duplicates? In what situations would you want counts of all items, except those that are only once in the collection? That doesn't sound like something that would be commonly useful.

[Wraith2]

And why would this be better in corefx than in a library on Nuget?

[Thaina]

might be related dotnet/runtime#23080 Linq Permutation Cross and Multiple variable for Zip and Join

C# var hasDup = list1.Cross(list2).Any((l,r) => l == r); var dups = list1.Cross(list2).Where((l,r) => l == r);

[GSPP]

I found the need for this fairly frequently. It happens a lot when ingesting data from external sources. It's sometimes necessary to validate that the data has some unique key. For example:

if (!incomingData.Select(x => x.SomeKey).IsDistinct())
    throw ...;

This is also useful in assertions in test and in production code.

I'd call this method IsDistinct.

To me, performance is a secondary concern here. But performance can certainly be better by using a low-overhead internal set collection type. The public hash table based types have certain overheads to them in the name of good API design.

There are also the usual optimizations such as testing for sequence as ICollection<T> c && c.Count == 0 and such. User code can do that but it's nice to have a high-quality implementation built-in.

Obtaining duplicates is also a common thing in my experience but I don't think this belongs in the framework. It is not common enough and the API shape would vary a lot based on use case.

[NetMage]

@GSPP Note: Based on testing in .Net Core 5.0 RC1, the internal Set class used by e.g. Distinct is slower than using HashSet I think due to optimizations ported from Dictionary. I opened an issue https://github.com/dotnet/runtime/issues/42760 for this.

[En3Tho]

@GSPP From the look of your example you don't really need to call Select / Distinct combo, but just Single/SingleOrDefault.This way you can throw on second already element if it's present

[eiriktsarpalis]

I've had to write similar code very frequently, although in most cases some kind of error reporting was required (e.g. needing to return the indices of the dupes as well). So I suspect a general-purpose duplicate detection method is probably not achievable, and many people would still have to roll their own implementation.

Another potential implementation could be the following:

public static IEnumerable<T> Duplicates<T>(this IEnumerable<T> source, IEqualityComparer<T>? comparer = null)
{
    var set = new HashSet<T>(source, comparer);
    foreach (var element in source)
    {
        if (!set.Add(element))
        {
            yield return element;
        }
    }    
}

It has the added benefit of being able to detect duplicates using source.Duplicates().Any() without needing to enumerate the entire source, however you now lose any frequency count information.

Apropos, duplicates in F# are typically detected using its CountBy implementation, which to my knowledge doesn't have an equivalent in LINQ. A naive implementation could have looked as follows:

public static IEnumerable<KeyValuePair<TKey, int>> CountBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> selector, IEqualityComparer<TKey>? keyComparer = null)
{
    var dict = new Dictionary<TKey, int>(keyComparer);
    foreach (var element in source)
    {
        var key = selector(element);
        bool found = dict.TryGetValue(key, out int count);
        dict[key] = found ? count + 1 : 1;
    }

    return dict;
}

Duplicates can be calculated using source.CountBy(x => x);