Статьи

SelectMany: возможно, самый мощный оператор LINQ

Привет обратно. Надеюсь, что все уже используют возможности LINQ на довольно регулярной основе. Хорошо, теперь все знают, как простые запросы LINQ с помощью where и select (и orderby, Take, Skip and Sum и т. Д.) Переводятся из понимания запроса в эквивалентное выражение для дальнейшего перевода:

from p in products where p.Price > 100 select p.Name

становится

products.Where(p => p.Price > 100).Select(p => p.Name)

Вся синяя подсветка синтаксиса исчезла; компилятор доволен тем, что осталось, и берет его оттуда слева направо (поэтому, это зависит от сигнатуры найденного метода Where, независимо от того, выбираем ли мы маршрут анонимных методов или, в случае Expression, <…> Подпись, маршрут деревьев выражений ).

Но давайте сделаем вещи немного более сложными и абстрактными:

from i in afrom j in bwhere i > jselect i + j

Это сложнее, потому что у нас есть два предложения; это более абстрактно, потому что мы используем имена без внутреннего значения. Давайте предположим, что a и b являются последовательностями IEnumerable <int> в дальнейшем. Фактически, что вышеупомянутый запрос означает в абстрактных терминах:

(a X b).Where((i, j) => i > j).Select((i, j) => i + j)

где X — гипотетический оператор декартового произведения, т. е. с учетом a = {1, 4, 7} и b = {2, 5, 8}, он производит {(1,2), (1,5), (1,8 ), (4,2), (4,5), (4,8), (7,2), (7,5), (7,8)} или всех возможных пар с элементами из первой последовательности в сочетании с элементом из второй последовательности. Для записи, обобщенный из такой пары, имеющей любое количество элементов, будет кортежем. Если бы у нас была такая возможность, Где бы получить последовательность таких кортежей, и он мог бы идентифицировать кортеж в своем лямбда-выражении как набор параметров (i, j). Аналогично, Select сделает то же самое, и все будут счастливы. Вы можете проверить результат будет {6, 9, 12}.

Вернемся к реальности сейчас: у нас нет прямого эквивалента декартова произведения в форме, которая производит кортежи. В дополнение к этому, оператор Where в LINQ имеет такую ​​подпись:

IEnumerable<T> Where<T>(this IEnumerable<T> source, Func<T, bool> predicate)

где параметр предиката является функцией одного и только одного аргумента. Лямбда (i, j) => i> j не совместима с этим, поскольку имеет два аргумента. Аналогичное замечание справедливо и для Select. Итак, как мы можем обойти это ограничение? SelectMany является ответом.

Демистификация SelectMany

В чем же волшебство SelectMany? С чего бы нам лучше начать наше расследование, чем с одной из подписей?

IEnumerable<TResult> SelectMany<TSource, TCollection, TResult>(    this IEnumerable<TSource> source,    Func<TSource, IEnumerable<TCollection>> collectionSelector,    Func<TSource, TCollection, TResult> resultSelector)

Вау, поначалу может быть немного ошеломляющим. Что оно делает? Учитывая последовательность элементов (называемых источником ) типа TSource, он запрашивает у каждого такого элемента (используя collectionSelector ) последовательность — каким-либо образом связанных — элементов типа TCollection. Затем он объединяет текущий выбранный элемент TSource со всеми элементами TCollection в возвращаемой последовательности и передает его в resultSelector для получения возвращаемого TResult. Все еще не ясно? Реализация говорит само за себя и состоит всего из трех строк:

foreach (TSource item in source)    foreach (TCollection subItem in collectionSelector(item))        yield return resultSelector(item, subItem);

Это уже дает нам огромное количество энергии. Вот пример:

products.SelectMany(p => p.Categories, (p, c) => p.Name + “ has category “ + c.Name)

Как мы можем использовать эту конструкцию для перевода нескольких предложений, которые могут вас заинтересовать? Что ж, нет причин, по которым функция, переданная в качестве первого аргумента (на самом деле второй после переписывания метода расширения, т.е. collectionSelector), использует аргумент TSource для определения результата IEnumerable <TCollection>. Например:

products.SelectMany(p => new int[] { 1, 2, 3 }, (p, i) => p.Name + “ with irrelevant number “ + i)

создаст последовательность строк, таких как «Чай с нерелевантным номером 1», «Чай с нерелевантным номером 2», «Чай с нерелевантным номером 3» и аналогичные для всех последующих продуктов. Этот пример не имеет смысла, но он показывает, что SelectMany может использоваться для формирования декартовой последовательности, подобной продукту. Давайте сосредоточимся на нашем первоначальном примере:

var a = new [] { 1, 4, 7 };var b = new [] { 2, 5, 8 };from i in afrom j in bselect i + j;

Я упустил предложение where, чтобы немного упростить ситуацию. С нашим знанием SelectMany выше мы можем теперь перевести запрос LINQ в:

a.SelectMany(i => b, …)

Это значит: для каждого i в a «извлечь» последовательность b и передать ее в…. Что за… подпись? Что-то из a (то есть int) и что-то из результата collectionSelector (то есть int из b) отображается на некоторый результат. Что ж, в этом случае мы можем объединить эти два значения, суммируя их, поэтому переведем предложение select за один раз:

a.SelectMany(i => b, (i, j) => i + j)

Что происходит, когда мы вводим, казалось бы, невинный пункт where между ними?

from i in afrom j in bwhere i > jselect i + j;

Первые две строки снова выглядят так:

a.SelectMany(i => b, …)

Тем не менее, для дальнейшего продвижения вперед нам нужно иметь возможность ссылаться на i (из a) и j (из b) в последующем предложении where и select, но оба соответствующих метода Where и Select принимают только «одиночные значения» :

IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate);IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> projection);

Итак, что мы можем сделать, чтобы объединить значения i и j в один объект? Хорошо, используйте анонимный тип:

a.SelectMany(i => b, (i, j) => new { i = i, j = j })

Это создает последовательность объектов, которые имеют два общедоступных свойства «i» и «j» (поскольку оно анонимно, нас не заботит регистр, и действительно, в запросе выше тип никогда не всплывает на поверхность, из-за того, что следует :

a.SelectMany(i => b, (i, j) => new { i = i, j = j }).Where(anon => anon.i > anon.j).Select(anon => anon.i + anon.j)

Другими словами, все ссылки на i и j в предложениях where и select в исходном выражении запроса были заменены ссылками на соответствующие свойства в анонимном типе, порожденном SelectMany.

Утрачено при переводе

Весь этот перевод этого небольшого запроса, приведенного выше, возлагает немало усилий на плечи компилятора (при условии, что a и b равны IEnumerable <int> и ничего более, т.е. нет IQueryable <int>):

  • Лямбда-выражение i => b захватывает переменную b, поэтому необходимо замыкание.
  • Это же лямбда-выражение действует как параметр для SelectMany, поэтому внутри класса замыкания будет создан анонимный метод .
  • Для нового {i = i, j = j} необходимо сгенерировать анонимный тип.
  • Второй аргумент SelectMany, где первый аргумент и первый аргумент Select — это лямбда-выражения, которые также генерируют анонимные методы.

В качестве небольшого жаркого летнего вечернего упражнения я написал все это вручную, чтобы показать, сколько кода потребуется в C # 2.0, за исключением замыканий и анонимных методов (более или менее C # 1.0 плюс универсальные шаблоны). Вот с чего мы начнем:

class Q{    IEnumerable<int> GetData(IEnumerable<int> a, IEnumerable<int> b)    {        return from i in a               from j in b               where i > j               select i + j;    }}

Это переводится на:

class Q{    IEnumerable<int> GetData(IEnumerable<int> a, IEnumerable<int> b)    {        Closure0 __closure = new Closure0();        __closure.b = b;        return Enumerable.Select(            Enumerable.Where(                Enumerable.SelectMany(                    a,                    new Func<int, IEnumerable<int>>(__closure.__selectMany1),                    new Func<int, int, Anon0<int, int>>(__selectMany2)                ),                new Func<Anon0<int, int>, bool>(__where1)            ),            new Func<Anon0<int, int>, int>(__select1)        );    }    private class Closure0    {        public IEnumerable<int> b;        public IEnumerable<int> __selectMany1(int i)        {            return b;        }    }    private static Anon0<int, int> __selectMany2(int i, int j)    {        return new Anon0<int, int>(i, j);    }    private static bool __where1(Anon0<int, int> anon)    {        return anon.i > anon.j;    }    private static int __select1(Anon0<int, int> anon)    {        return anon.i + anon.j;    }}private class Anon0<TI, TJ> // generics allow reuse of type for all anonymous types with 2 properties, hence the use of EqualityComparers in the implementation{    private readonly TI _i;    private readonly TJ _j;    public Anon0(TI i, TJ t2) { _i = i; _j = j; }    public TI i { get { return _i; } }    public TJ j { get { return _j; } }    public override bool Equals(object o)    {        Anon0<TI, TJ> anonO = o as Anon0<TI, TJ>;        return anonO != null && EqualityComparer<TI>.Default.Equals(_i, anonO._i) && EqualityComparer<TJ>.Default.Equals(_j, anonO._j);    }    public override int GetHashCode()    {        return EqualityComparer<TI>.Default.GetHashCode(_i) ^ EqualityComparer<TJ>.Default.GetHashCode(_j); // lame quick-and-dirty hash code    }    public override string ToString()    {        return “( i = “ + i + “, j = ” + j + “ }”; // lame without StringBuilder    }}

Подумайте немного … Хотели бы вы пройти через это бремя, чтобы написать запрос? «Синтаксический сахар» может иметь некоторую плохую коннотацию для некоторых, но это может быть очень милый ребенок!

Привязать скрытно

Поклонники «монад», термин из теории категорий, который дал отличные результаты в области функционального программирования как способа сделать явные побочные эффекты через систему типов (например, монаду IO в Haskell), распознает SelectMany (ограниченный) подпись, совпадающая с подписью bind:

IEnumerable<TResult> SelectMany<TSource, TResult>(    this IEnumerable<TSource> source,    Func<TSource, IEnumerable<TResult>> collectionSelector)

соответствует:

(>>=) :: M x –> (x –> M y) –> M y

Который является оператором связывания Хаскелла. Для тех, кто знаком с Haskell, нотация «do», позволяющая создать визуальную иллюзию встраивания стиля «императивное программирование» с запятой в фигурную скобку в код на Haskell, является синтаксическим сахаром над этим оператором, который определяется (рекурсивно) следующим образом:

do { e }            = edo { e; s }         = e >>=  \_ –> do { s }do { x <- e; s }    = e >>= (\x –> do { s })do { let x = e; s } = let x = e in do { s }

Переименуйте в SelectMany, замените M x на IEnumerable <x> и примите форму без каррирования, и вы получите:

SelectMany :: (IEnumerable<x>, x –> IEnumerable<y>) –> IEnumerable<y>

Отождествление x с TSource, y с TResult и превращение a -> b в Func <a, b> дает:

SelectMany :: Func<IEnumerable<TSource>, Func<TSource, IEnumerable<TResult>>, IEnumerable<TResult>>

и вы получили ту же подпись, что и SelectMany, с которой мы начали. Любопытно, что M в исходной форме действует как конструктор типов, что CLR не поддерживает, так как в нем отсутствует родственный полиморфизм высшего порядка; это еще одна абстракция на один уровень выше, чем дженерики, которые математические фанаты любят использовать в теории категорий. Идея состоит в том, что если вы можете доказать, что законы являются истинными в некоторой «структуре», и вы можете отобразить эту структуру на другую «целевую структуру» с помощью некоторой функции отображения, соответствующие законы будут также выполняться в «целевой структуре» , Например:

({ even, odd }, +)

и

({ pos, neg }, *)

могут быть отображены друг на друга попарно и рекурсивно, что позволяет отображать законы от первого ко второму, например

even + odd –> oddpos * neg –> neg

Конечно, это в значительной степени упрощенный образец, я бы порекомендовал всем, кто заинтересован, получить приличную книгу по теории категорий, чтобы вникнуть в кровавые подробности.

Слово предостережения

Теперь, когда вы знаете, как работает SelectMany, можете ли вы подумать о возможных последствиях при выборе из нескольких источников? Позвольте мне дать вам совет: вложенные foreachs. Это неинтересное предложение, которое играет роль заполнителя в пространстве времени, пока вы размышляете над вопросом. Понял? Действительно, порядок имеет значение. Написание следующих двух строк кода приводит к другому запросу с совершенно другим шаблоном выполнения:

from i in a from j in b …from j in b from i in a …

Те примерно соответствуют:

foreach (var i in a)    foreach (var j in b)        …

против

foreach (var j in b)    foreach (var i in a)        …

Но разве это много шума из ничего? Нет, не совсем. Что если итерация по b намного дороже, чем итерация по a? Например,

from p in localCollectionOfProductsfrom c in sqlTableOfCategories…

Это означает, что для каждого продукта, повторяемого локально, мы обращаемся к базе данных, чтобы выполнить итерацию по (извлеченным) категориям. Если бы оба были местными, не было бы проблемы, конечно; если бы оба были удаленными, перевод (например) SQL позаботился бы об этом, чтобы сохранить тяжелую работу на удаленной машине. Если вы хотите увидеть разницу сами, вы можете использовать следующую симуляцию:

    using System;    using System.Collections.Generic;    using System.Diagnostics;    using System.Linq;    using System.Threading;    class Q    {        static void Main()        {            Stopwatch sw = new Stopwatch();            Console.WriteLine("Slow first");            sw.Start();            foreach (var s in Perf<int,char>(Slow(), Fast()))                Console.WriteLine(s);            sw.Stop();            Console.WriteLine(sw.Elapsed);            sw.Reset();            Console.WriteLine("Fast first");            sw.Start();            foreach (var s in Perf<char,int>(Fast(), Slow()))                Console.WriteLine(s);            sw.Stop();            Console.WriteLine(sw.Elapsed);        }        static IEnumerable<string> Perf<S,T>(IEnumerable<S> a, IEnumerable<T> b)        {            return from i in a                   from j in b                   select i + "," + j;        }        static IEnumerable<int> Slow()        {            Console.Write("Connecting... ");            Thread.Sleep(2000); // mimic query overhead (e.g. remote server)            Console.WriteLine("Done!");            yield return 1;            yield return 2;            yield return 3;        }        static IEnumerable<char> Fast()        {            return new [] { 'a', 'b', 'c' };        }    }

Это производит:

[Img_assist | NID = 4625 | название = | убывание = | ссылка = нет | Align = нет | ширина = 259 | Высота = 374]

Очевидно, это может быть случай, когда вы создаете запрос, который может быть выполнен только при обращении к серверу несколько раз, например, потому что порядок результата имеет значение (см. Скриншот выше для иллюстрации влияния упорядочения — но некоторые операции локальной сортировки может также помочь, чтобы удовлетворить такое требование), или потому что второй источник запроса зависит от первого (от i в a от j в b (i)…). Для решения не существует серебряной пули, но знание того, что происходит под одеялом, несомненно, дает необходимую информацию для решения конкретных сценариев.

Счастливого связывания!