Check if all items in a Collection have the same value.

Question

an extension method on a collection named MeasurementCollection checks if the property Template.Frequency (Enum) of each item has the same value.

    public static bool IsQuantized(this MeasurementCollection items)
    {
        return  (from i in items 
                 select i.Template.Frequency)
                .Distinct()
                .Count()==1;

    }

edit info about underlying classes

    MeasurementCollection : ICollection<IMeasurement>

    IMeasurement 
    {
    IMeasurementTemplate Template { get; }        
    ......
    }

Is this a correct approach or is there an easier solution already in Linq? This method will be used intense in the application.

Have you got tips to take with me, back to the drawing board?

Answer 1

Edit: to address Timwi's concerns about 3 enumerators:

bool same = <your default> ;
var first = items.FirstOrDefault();
if (first != null)  // assuming it's a class
{
   same = items.Skip(1).All(i => i.Template.Frequency == first.Template.Frequency); 
}

Which still uses 2 enumerators. Not an issue for the average List<>, but for a DB query it might pay to use the less readable:

bool same = <your default> ;
Item first = null;

foreach(var item in items)
{
    if (first == null)
    {
        first = item;
        same = true;
    }
    else
    {
        if (item.Template.Frequency != first.Template.Frequency)
        {
           same = false;
           break;
        }
    }
}

Answer 2

It would be faster like this:

public static bool IsQuantized(this MeasurementCollection items)
{
    if(items == null || items.Count == 0)
       return true;

    var valueToCompare = items.First().Template.Frequency;

    return items.All(i => i.Template.Frequency == valueToCompare);
}

It will return false on the first item's template frequency that is different, while in your code, the algorithm passes the whole collection.

Answer 3

First of a general linq advise. If you just what to know if there's exactly one in a collection use Single() or SingleOrDefault(). Count will potentially iterate the entire collection which is more than you need since you can bail out if there's two.

public static bool IsQuantized(this MeasurementCollection items)
        {
            var first = items.FirstOrDefault();
            return first != null && items.Skip(1).All(i => first.Template.Frequency == i.Template.Frequency));
        }

Answer 4

You could just find the first value and check if ANY others are different, this will avoid having to eval the whole collection (unless the single different value is the last one)

public static bool IsQuantized(this MeasurementCollection items)
{
    if(!items.Any())
        return false; //or true depending on your use case

    //might want to check that Template is not null, a bit a violation of level of demeter, but just an example
    var firstProp = item.First().Template.Frequency;

    return !items.Any(x=> x..Template.Frequency != firstProp);

}

Answer 5

I got a bit of inspiration and thought about a solution with only speed in mind. This is really not that readable (which I usually preferre) but the characteristics when it comes to speed should be pretty good.

The once case is the same for most of the other implementations O(n) but it's highly unlikely since it would require all the first half of the elements to be the equal and the second half to all be equal but not equal to the value in the first half. and would require the same number of comparisons as a linear search. In most other cases with the first odd one in a random place this will require half as many comparisons as the linear. In the case where the values are in pairs. So that item[0] == item[1] and item[2] == item[3] and item[0] != item[2] (and similar) then the linear search will be faster. In general with either random data or few odd once this should be faster than a linear search

public static bool AllSame<T>(this IEnumerable<T> source,
                              IEqualityComparer<T> comparer = null)
        {
            if (source == null)
                throw new ArgumentNullException("source cannot be null.", "source");

            if (comparer == null)
                comparer = EqualityComparer<T>.Default;
            var enumerator = source.GetEnumerator();

            return source.Zip(comparer);
        }

        private static bool Zip<T>(this IEnumerable<T> sequence, IEqualityComparer<T> comparer)
        {
            var result = new List<T>();
            var enumerator = sequence.GetEnumerator();
            while (enumerator.MoveNext())
            {
                var first = enumerator.Current;
                result.Add(enumerator.Current);
                if (enumerator.MoveNext())
                {
                    if (!comparer.Equals(first, enumerator.Current))
                    {
                       return false;
                    }
                }
                else
                {
                    break;
                }
            }
            return result.Count == 1 ? true : result.Zip(comparer);
        }

with out tail call optimization this uses extra memory (with a worst case of an amount of memory close to the amount of memory used for the original source). The call stack shouldn't get to deep though since no IEnumerable concrete implementations (at least that I'm aware of) can hold more than int.MaxValue elements. which would require a max of 31 recursions.