LINQ SelectMany Usage

Select and SelectMany are two projection operators in LINQ. Select simply goes through a sequence of elements (IEnumerable), and for each input element it exactly projects one output element. On the contrast, SelectMany can projects 0, 1 or multiple elements for each input elements. It works something like this, for each input element, I can do something based on the element context or just fixed logic, then produces some new elements to return.

For instance, each instructor offers many courses in the school, Instructors.SelectMany(i => i.Courses) means for each instructor in the Instructors list, return his/her Courses, so you get all courses for all instructors.

A SelectMany overloading method accepts the second parameter which gives us more power to control the output. Let’s look at a statement:

Instructors.SelectMany(i => i.Courses, (i, c) => new { InstructorName = i.Name, CourseName = c } ).

The first parameter "i => i.Courses" will get all Courses for each instructor, and transform it to the second parameter, so inside "(i, c)", "i" is the original input element just like what we have in "i => i.Courses", and "c" here is each element sent from "i.Courses". What the statement does is go through each instructor’s courses, and return the instructor’s name and course name with anonymous type of object.

Following code example demos a few usages of SelectMany, including how you can join a sequence to another sequence, and do you your customized logic inside the lambda function:

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    class Instructor
    {
        public string Name { get; set; }
        public string DeptID { get; set; }
        public string[] Courses { get; set; }
    }

    class Department
    {
        public string ID { get; set; }
        public string Name { get; set; }
    }

    static void Main()
    {
        var departments = new List<Department>()
            {
                new Department() { ID = "EE", Name = "Electrical Engineering" },
                new Department() { ID = "CS", Name = "Computer Science" },
                new Department() { ID = "ME", Name = "Mechanical Engineering" }
            };
        var instructors = new List<Instructor>()
            {
                new Instructor() { Name = "EE1", DeptID = "EE", Courses = new string [] { "EE101", "EE102", "EE103" } },
                new Instructor() { Name = "EE2", DeptID = "EE", Courses = new string [] { "EE201", "EE202", "EE203" } },
                new Instructor() { Name = "CS1", DeptID = "CS", Courses = new string [] { "CS101", "CS102", "CS103" } },
                new Instructor() { Name = "CS2", DeptID = "CS", Courses = new string [] { "CS201", "CS202", "CS203" } },
                new Instructor() { Name = "ME1", DeptID = "ME", Courses = new string [] { "ME101", "ME102", "ME103" } },
                new Instructor() { Name = "ME2", DeptID = "ME", Courses = new string [] { "ME201", "ME202", "ME203" } },
            };
        var CSInstructors = instructors.Where(i => i.DeptID == "CS").Select(i => "CS Instructor: " + i.Name).ToArray();
        // CSInstructors: { "CS Instructor: CS1", "CS Instructor: CS2" }
  
        var CSCourses = instructors.Where(i => i.DeptID == "CS").SelectMany(i => i.Courses).ToArray();
        // CSCourses.Count = 6
        // CSCourses: { "CS101", "CS102", "CS103", "CS201", "CS202", "CS203" }

        var CSInstructorCourses = instructors.Where(i => i.DeptID == "CS").
            SelectMany(i => i.Courses, (i, c) => i.Name + ":" + c).ToArray();
        // CSInstructorCourses.Count = 6
        // CSInstructorCourses: { "CS1:CS101", "CS1:CS102", "CS1:CS103", "CS2:CS201", "CS2:CS202", "CS2:CS203" } 

        var instructorDepartment = instructors.SelectMany(i => departments.Where(d => d.ID == i.DeptID),
            (i, d) => i.Name + ":" + d.Name).ToArray(); 
        // instructorDepartment.Count = 6
        // instructorDepartment: { "EE1:Electrical Engineering", "EE2:Electrical Engineering", "CS1:Computer Science" ... }

        var departmentCourses = instructors.SelectMany(
            (i, index) => i.Courses.Select(c => new { Index = index, CourseName = c}),
            (i, c) => new { Course = c.CourseName, Instructor = i.Name, 
                DeptName= departments.Find(d => d.ID == i.DeptID).Name, Index = c.Index, }).ToArray();
        /* departmentCourses.Count = 18
         * departmentCourses: 
            { Course = "EE101", Instructor = "EE1", DeptName = "Electrical Engineering", Index = 0 }
            { Course = "EE102", Instructor = "EE1", DeptName = "Electrical Engineering", Index = 0 }
            { Course = "EE103", Instructor = "EE1", DeptName = "Electrical Engineering", Index = 0 }
            { Course = "EE201", Instructor = "EE2", DeptName = "Electrical Engineering", Index = 1 }
            { Course = "EE201", Instructor = "EE2", DeptName = "Electrical Engineering", Index = 1 }
            ...
            { Course = "ME202", Instructor = "ME2", DeptName = "Mechanical Engineering", Index = 5 }
            { Course = "ME203", Instructor = "ME2", DeptName = "Mechanical Engineering", Index = 5 }
         */

        var courses101 = instructors.SelectMany(
            i => {
                List<string> filterCourses = new List<string>();
                foreach(var course in i.Courses)
                {
                    if (course.EndsWith("101"))
                        filterCourses.Add(course);
                }
                return filterCourses;
            }, 
            (i, c) => {
                var dept = departments.Find(d => d.ID == i.DeptID);
                var deptName = (dept == null) ? "N/A" : dept.Name;
                return new { Course = c, Instructor = i.Name, DeptName = deptName };
            }).ToArray();
        /* courses101.Count = 3
         * courses101:
            { Course = "EE101", Instructor = "EE1", DeptName = "Electrical Engineering" }
            { Course = "CS101", Instructor = "CS1", DeptName = "Computer Science" }
            { Course = "ME101", Instructor = "ME1", DeptName = "Mechanical Engineering" }
         */

        Console.Read();
    }
}

The Cost Of Linq And IQueryable

The Language Integrated Query (Linq) is part of the .NET 3.5. We can easily do Linq queries against IEnumerable objects using very concise syntax by passing a delegate or the new Lambda expression. You can even create your own Linq Provider and implement the IQueryable interface, building something like Linq to Google or Linq to MySql.

It's super great, right? Basically yes, but remember a lot of new features from Microsoft have a cost. In my previous post we discussed the Linq deferred execution issue. Today let's do some tests to see how expensive the Linq queries are. Below is the simple test code. We build a simple key/Value collection (array). Because all collections including array have implemented IEnumerable interface, we can query the objects inside the array with Linq. Furthermore, we can convert the array object to be IQueryable and do query over IQueryable.

using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    // A simple class presenting key/value pair
    class KeyValue
    {
        public KeyValue(string key, int value)
        {
            Key = key;
            Value = value;
        }
        public string Key { get; set; }
        public int Value { get; set; }
    }

    // Simple linear search 
    static KeyValue LinearSearch(KeyValue[] keyValues, string key)
    {
        foreach (KeyValue item in keyValues)
        {
            if (item.Key == key)
                return item;
        }
        return null;
    }

    /// <summary>
    /// Compare search performance with three methods:
    /// 1. Manually go through each object inside collection
    /// 2. Linq search by IEmuerable<T>.Where(lambda_expression);
    /// 3. Convert to IQueryable and then IQueryable<T>.Where(lambda_expression)
    /// </summary>
    /// <param name="keyValues">The array to be search on</param>
    /// <param name="key">Search object by KeyValue.Key</param>
    /// <param name="repeat">Number for repeating the search</param>
    static void SearchTest(KeyValue[] keyValues, string key, int repeat)
    {
        Stopwatch watch = new Stopwatch();

        // Test linear search
        watch.Start();
        for (int i = 0; i < repeat; i++)
            LinearSearch(keyValues, key);
        watch.Stop();
        Console.WriteLine("Linear search over {0} objects (repeating {1} times) takes {2} ms",
            keyValues.Count(), repeat, watch.ElapsedMilliseconds);
        watch.Reset(); watch.Start();

        // Test Linq search
        for (int i = 0; i < repeat; i++)
            keyValues.FirstOrDefault(item => item.Key == key);
        watch.Stop();
        Console.WriteLine("Linq search over {0} objects (repeating {1} times) takes {2} ms",
            keyValues.Count(), repeat, watch.ElapsedMilliseconds);

        // Test IQueryable search
        IQueryable<KeyValue> queryables = keyValues.AsQueryable();
        watch.Reset(); watch.Start();
        for (int i = 0; i < repeat; i++)
            queryables.FirstOrDefault(item => item.Key == key);
        watch.Stop();
        Console.WriteLine("Linq IQueryable search over {0} objects (repeating {1} times) takes {2} ms",
            keyValues.Count(), repeat, watch.ElapsedMilliseconds);
        Console.WriteLine();
    }


    static void Main()
    {
        // Build test data
        KeyValue[] keyValues1 =
            Enumerable.Range(0, 1000).Select(i => new KeyValue(i.ToString(), i)).ToArray();
        KeyValue[] keyValues2 =
            Enumerable.Range(0, 2000).Select(i => new KeyValue(i.ToString(), i)).ToArray();
        KeyValue[] keyValues3 =
            Enumerable.Range(0, 3000).Select(i => new KeyValue(i.ToString(), i)).ToArray();

        // Start Test
        SearchTest(keyValues1, "5000", 1000);
        SearchTest(keyValues2, "10000", 1000);
        SearchTest(keyValues3, "20000", 1000);

        Console.Read();
    }
}

Result:


As expected Linq to objects is slightly slower than the regular linear search, and we can assume Linq uses linear search internally. But IQueryable search is much slower than others. Why that happened? Not like Linq to object where Lambda expression is passing as a function delegate, Lambda expression passed to the IQueryable is converted to Expression tree which is a quite expensive.

The interesting thing is that explicit delegate passed to IQueryable won't be converted to Expression tree. In following code there's no noticeable performance difference between the two queries.

    KeyValue keyValueObj = keyValues.FirstOrDefault(
        delegate(KeyValue obj) { return obj.Key == key; });
    IQueryable<KeyValue> queryables = keyValues.AsQueryable();
    keyValueObj = queryables.FirstOrDefault(
        delegate(KeyValue obj) { return obj.Key == key; });

Conclusion: Linq to objects are working fine for .NET collections, but be cautious to make a collection as IQueryable (collection.AsQueryable() method) if you are using Lambda expression inside the IQueryable queries, because there's performance degradation for it.

.NET Linq Deferred Execution

The new Linq (Language Integrated Query) feature shipped with .NET 3.5 is fantastic. With Linq now we can write more concise and meaningful queries. Like anonymous method pitfall we discussed in previous post, Linq has a similar behavior called deferred execution; it could be problematic if you are not aware of that. Let's look at following code:

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Test Data
        string[] names = new string [] { "NameA", "NameB"};
        string _name = "NameA";

        // Query by delegate
        IEnumerable<string> searchName1 = names.Where(
            delegate(string name)
            {
                return name == _name;
            });
        // Query by Lambda expression
        IEnumerable<string> searchName2 = names.Where(name => name == _name);

        // Rename the search keyword
        _name = "NameB";

        // Redo the queries
        IEnumerable<string> searchName3 = names.Where(
            delegate(string name)
            {
                return name == _name;
            });
        IEnumerable<string> searchName4 = names.Where(name => name == _name);

        Console.WriteLine("{0} \t {1} \t {2} \t {3}",
            searchName1.First(), searchName2.First(), searchName3.First(), searchName4.First());

        Console.Read();
    }
}

What's the result? you may think it must be "NameA NameA NameB NameB". But you will get "NameB NameB NameB NameB" instead if you run the console application.

Why's that? Because Linq's Where search is by default a deferred execution function. For example, the statement

string searchName2 = names.Where(name => name == _name);

is telling the compiler that we have a Lambda expression attached to the Where search. But it's not invoked until we are actually reading data from the search result. So searchName1, searchName2, searchName3 and searchName4 in our case are the same because they all compare the same value when their condition is examined.

How to avoid this issue? Reading data immediately after the query such as looping through the data inside the IEnumerable collection. The other way is use ToList() or ToArray() methods to force immediate execution of a Linq query.

Following Linq methods have deferred execution behavior:

Except, Take, TakeWhile, Skip, SkipWhile, Where

While the others don't have such behavior, and will be executed immediately:

Any, Average, Contains, Count, First, FirstOrDefault, Last, LastOrDefault, Single,
 SingleOrDefault, Sum, Max, Min, ToList, ToArray, ToDictionary, ToLookup

How to remember all this? The tip is to look at the return type of the method. It would be deferred execution if the return type is IEnumerable<TSource>. Why? Yield return is used by those methods. That's the root cause of the deferred execution.