Linq: All With value set and at least one with that value?

Question

I have a sub query where I need to know that at least one item exists, and that all items that exist are true.

Right now I'm doing an Any and an All but this is seriously slow compared to just an All or just an Any (because it's doing it twice).

I'm looking for a way to do AnyAll :) that would be much more efficient.

Any ideas?

Answer 1

/// <summary>
/// Same behavior as "enumerable.All()" but returns false for an empty enumerable instead of true. 
/// Does this while avoiding the double traversal of the enumerable caused by the usual
/// pattern of calling "enumerable.Any() && enumerable.All()".
/// </summary>
/// <typeparam name="T">The element type of the enumerable.</typeparam>
/// <param name="enumerable">The enumerable for which to test and get a single item.</param>
/// <param name="predicate">The test to run on all elements of the enumerable.</param>
/// <returns>True if the enumerable had at least one element and all elements tested true for the predicate.</returns>
public static bool AllWithAtLeastOne<T>(this IEnumerable<T> enumerable, Func<T, bool> predicate)
{
    IEnumerator<T> enumerator = enumerable.GetEnumerator();
    if (enumerator.MoveNext())
    {
        T singleElement = enumerator.Current;
        bool result = predicate(singleElement);
        while (result && enumerator.MoveNext())
        {
            singleElement = enumerator.Current;
            result = predicate(singleElement);
        }
        return result;
    }
    return false;
}

Answer 2

Short version: There isn't a better way than an Any and an All.

I have tried doing a concat (union all in SQL) and then doing the any and the all using a let statement, but it's slower than doing any on each table as ors and then alls. The fastest way is something like this:

from q in query 

let someSubQuery = (from s in query.SubQuery where <filter> select s)
let someSubQuery2 = (from s in query.SubQuery2 where <filter> select s)

where (someSubQuery.Any() || someSubQuery2.Any()) && someSubQuery.All(a => a.Boolean) && someSubQuery2.All(a => a.Boolean)

select q

I also tried doing internal selects in the sub queries to look for it's own matches but it was drastically slower as well.

As far as I can tell, there also is no built in T-SQL function that would assist either. An All is simply a NOT EXISTS against the inverse of the boolean operator so one must do the NOT EXISTS and an EXISTS to make sure that at least one true exists. It was my hope that I could find an SQL syntax that would optimize this query directly, and then I could use TVFs or stored procedures to do the querying on the server and expose those to Entity Framework, however it appears after doing a lot of research that no such optimization is possible.

The Query optimizer appears to do a relatively good job at optimizing this, however it's still pretty expensive.

So long story short, if you need to do this, do an All and an Any, it's the fastest way. All other approaches were slower by orders of magnitude.

Answer 3

Here are three tests. I'm seeing #2 being the fastest, then #1 and last of all #3.

    List<BooBoo> list1; // empty
    List<BooBoo> list2; // false, then lots of true
    List<BooBoo> list3; // lots of true, false
    List<BooBoo> list4; // one true
    List<BooBoo> list5; // lots of true
    List<BooBoo> list6; // one false
    List<BooBoo> list7; // lots of false
    private void button1_Click(object sender, EventArgs e)
    {
        MakeLists();

        long span1 = RunTest1(200000);
        long span2 = RunTest2(200000);
        long span3 = RunTest3(200000);
    }

    private long RunTest1(long numTimes)
    {
        DateTime time1 = DateTime.Now;
        for (int count = 0; count < numTimes; count++)
        {
            bool b1 = IsItGood1(list1);
            bool b2 = IsItGood1(list2);
            bool b3 = IsItGood1(list3);
            bool b4 = IsItGood1(list4);
            bool b5 = IsItGood1(list5);
            bool b6 = IsItGood1(list6);
            bool b7 = IsItGood1(list7);
        }
        DateTime time2 = DateTime.Now;
        TimeSpan span = time2 - time1;
        return span.Ticks;
    }
    private bool IsItGood1(List<BooBoo> list)
    {
        return (list.Count > 0) && (list.FirstOrDefault(b => !b.BooMe) == null); // false
    }
    private long RunTest2(long numTimes)
    {
        DateTime time1 = DateTime.Now;
        for (int count = 0; count < numTimes; count++)
        {
            bool b1 = IsItGood2(list1);
            bool b2 = IsItGood2(list2);
            bool b3 = IsItGood2(list3);
            bool b4 = IsItGood2(list4);
            bool b5 = IsItGood2(list5);
            bool b6 = IsItGood2(list6);
            bool b7 = IsItGood2(list7);
        }
        DateTime time2 = DateTime.Now;
        TimeSpan span = time2 - time1;
        return span.Ticks;
    }
    private bool IsItGood2(List<BooBoo> list)
    {
        if (list.Count == 0) return false;
        foreach (BooBoo boo in list)
        {
            if (!boo.BooMe) return false;
        }
        return true;
    }
    private long RunTest3(long numTimes)
    {
        DateTime time1 = DateTime.Now;
        for (int count = 0; count < numTimes; count++)
        {
            bool b1 = IsItGood3(list1);
            bool b2 = IsItGood3(list2);
            bool b3 = IsItGood3(list3);
            bool b4 = IsItGood3(list4);
            bool b5 = IsItGood3(list5);
            bool b6 = IsItGood3(list6);
            bool b7 = IsItGood3(list7);
        }
        DateTime time2 = DateTime.Now;
        TimeSpan span = time2 - time1;
        return span.Ticks;
    }
    private bool IsItGood3(List<BooBoo> list)
    {
        return list.Any() && list.All(i => i.BooMe);
    }
    private void MakeLists()
    {
        #region make lists
        // at least one item, all true
        list1 = new List<BooBoo>(); // empty

        list2 = new List<BooBoo>();
        list2.Add(new BooBoo { BooMe = false });
        list2.Add(new BooBoo { BooMe = true });
        list2.Add(new BooBoo { BooMe = true });
        list2.Add(new BooBoo { BooMe = true });
        list2.Add(new BooBoo { BooMe = true });
        list2.Add(new BooBoo { BooMe = true });
        list2.Add(new BooBoo { BooMe = true });

        list3 = new List<BooBoo>();
        list3.Add(new BooBoo { BooMe = true });
        list3.Add(new BooBoo { BooMe = true });
        list3.Add(new BooBoo { BooMe = true });
        list3.Add(new BooBoo { BooMe = true });
        list3.Add(new BooBoo { BooMe = true });
        list3.Add(new BooBoo { BooMe = true });
        list3.Add(new BooBoo { BooMe = false });

        list4 = new List<BooBoo>();
        list4.Add(new BooBoo { BooMe = true });

        list5 = new List<BooBoo>();
        list5.Add(new BooBoo { BooMe = true });
        list5.Add(new BooBoo { BooMe = true });
        list5.Add(new BooBoo { BooMe = true });
        list5.Add(new BooBoo { BooMe = true });
        list5.Add(new BooBoo { BooMe = true });
        list5.Add(new BooBoo { BooMe = true });
        list5.Add(new BooBoo { BooMe = true });

        list6 = new List<BooBoo>();
        list6.Add(new BooBoo { BooMe = false });

        list7 = new List<BooBoo>();
        list7.Add(new BooBoo { BooMe = false });
        list7.Add(new BooBoo { BooMe = false });
        list7.Add(new BooBoo { BooMe = false });
        list7.Add(new BooBoo { BooMe = false });
        list7.Add(new BooBoo { BooMe = false });
        list7.Add(new BooBoo { BooMe = false });
        list7.Add(new BooBoo { BooMe = false });
        #endregion
    }

Answer 4

Why not just count items and then look for at least one which is untrue:

class BooBoo { public bool BooMe { get; set; } }

public static void Run() {

List<BooBoo> list = new List<BooBoo>();

bool isGood1 = (list.Count > 1) && (list.FirstOrDefault(b => !b.BooMe) == null); // false

list.Add(new BooBoo { BooMe = false });

bool isGood2 = (list.Count > 1) && (list.FirstOrDefault(b => !b.BooMe) == null); // false

list.Add(new BooBoo { BooMe = true });

bool isGood3 = (list.Count > 1) && (list.FirstOrDefault(b => !b.BooMe) == null); // false

list.Clear();
list.Add(new BooBoo { BooMe = true });
list.Add(new BooBoo { BooMe = true });

bool isGood4 = (list.Count > 1) && (list.FirstOrDefault(b => !b.BooMe) == null);  // true

}