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?

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

Solution 2

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 = items.First().Template.Frequency;

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

}

Solution 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));
        }

Solution 4

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 worse 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.

Solution 5

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.

View more solutions

Comments

[Rune FS]

you're code does not do the same comparison as OPs. He's comparing a property of a property. Yours is doing a ref comparison

[ssss]

This assumes that the collection is indexable.

[Henk Holterman]

@Rune: I'll add that for completeness but it's not a fundamental difference. Unless some properties are null which would make it a mess.

[ssss]

This is the same as the Trick #2 in my second answer. It instantiates two enumerators and evaluates the first item twice — and if you don’t want it to throw, you’d need a third to check for Any() first. This can be a performance problem if the collection is lazy and the first element takes a while to compute.

[Rune FS]

@Henk I agree that it's not fundamental to the way of solving the task your proposing but I disagree with it not being fundamental to the solution since the code as is would yield an incorrect result quite often (as I'm sure you are aware of)

[Rune FS]

@Timwi but on the upside this approach is a lot more readable since it can be written so that it almost reads as the requirements

[Henk Holterman]

@Timwi: The name Collection suggests an enumerator isn't expensive, but we don't really know.

[Henk Holterman]

@Rune: No, I don't see the big problem.

[StriplingWarrior]

The OP put an #arrays tag on this question, which may indicate that MeasurementCollection is implemented as an array or similar structure.

[Henk Holterman]

@Timwi: there is an [arrays] tag

[Henk Holterman]

Not my -1 but your code seems like it wouldn't deal with an empty collection very well. And you were the perfectionist.

[Rune FS]

@Henk you're right so I've updated my answer. I would however call it perfectionistic to comment on an implementation that in most case would yield an incorrect answer. Neither do I see how praising your general approach for it's readability is perfectionistic :)

[Reed Copsey]

@Henk: I think his problem is that, in your option1, you're comparing items of the collection directly (by ref), but in option 2, you're comparing items by item.Template.Frequency... If they're classes, your first solution will always say every item is unique (since they're different references)

[Henk Holterman]

@Reed: correct, I was thinking (but not writing) something like x.Value. I'll delete the first part.

[ssss]

Henk, your new version now has a serious bug. It will say all the items in the collection are the same if the first item is null.

[ssss]

① The edited version returns true when the input is null, thus masking a likely bug. It should throw ArgumentNullException instead. ② This still assumes that the collection has a Count. Admittedly, the name suggests that it does, but the question doesn’t state that, and the question asked about a solution in LINQ, which works with pure enumerables.

[Henk Holterman]

@Timwi: I don't think the collection contains null values.

[ssss]

@Henk: How do you know? Your code doesn’t check for that. When you write a method that takes a collection of items, your method needs to be prepared to be given any collection and not have some unexpected, hard-to-debug side-effect when given something that you didn’t happen to think anyone would give it.

[Henk Holterman]

@timWi: if you look carefully you might see that I didn't write a method at all. And I minimize errorhandling in answers.

[CodesInChaos]

fails if the first item in the collection is null