LINQ. First vs. Single. Часть вторая.

Неожиданно предыдущий пост про LINQ породил несколько вопросов, которые в свою очередь породили еще несколько :) О них-то мы сегодня и поговорим.

Основная мысль того поста была настолько очевидной, что я даже сомневался, писать или нет. Когда же пост уже был написан, решил сделать его хоть немного менее унылым, снабдив исходниками реализаций методов First и Single LINQ To Objects. При этом реализация метода Single мне показалась неоптимальной. За комментариями по этому поводу я обратился на форумы MSDN. К сожалению, я не сразу понял мысль коллег про "exceptional cases"... но в целом дискуссия получилась довольно конструктивной.

Итак, напомню, как выглядел код, полученный при помощи Reflector'a:

TSource local = default(TSource);
long num = 0L;
foreach (TSource local2 in source)
{
    if (predicate(local2))
    {
        local = local2;
        num += 1L;
    }
}
long num2 = num;
if ((num2 <= 1L) && (num2 >= 0L))
{
    switch (((int) num2))
    {
        case 0:
            throw Error.NoMatch();

        case 1:
            return local;
    }
}
throw Error.MoreThanOneMatch();

А почему бы не добавить в тело условия if (predicate(local2)) проверку на равенство num двум:

TSource local = default(TSource);
long num = 0L;
foreach (TSource local2 in source)
{
    if (predicate(local2))
    {
        local = local2;
        num += 1L;
        if (num == 2)
          throw Error.MoreThanOneMatch();
    }
}
long num2 = num;
if ((num2 <= 1L) && (num2 >= 0L))
{
    switch (((int) num2))
    {
        case 0:
            throw Error.NoMatch();

        case 1:
            return local;
    }
}

С одной стороны, этот код привносит условие, которое тоже требует машинного времени для своего выполнения. Но, во-первых, условие if (num == 2) - элементарное, а во-вторых, при любом раскладе оно выполнится не более двух раз. Что же мы при этом экономим? Экономим мы k проходов Enumenator'а (который лежит в основе foreach) и столько же выполнений предиката (только в случае наличия дубликатов, ибо если элемент уникальный, нам все равно придется пройти коллекцию полностью). Очевидно, что стандартная реализация проигрывает.

В принципе у текущей реализации есть оправдание. Вызывая метод Single, мы заранее предполагаем, что в коллекции будет находиться один подходящий элемент (иначе воспользовались бы методом First), поэтому данная реализация проигрывает лишь в редких случаях, отсрачивая генерацию исключения. Сюда же можно добавить, что цена генерации исключения в большинстве случаев будет гораздо выше издержек алгоритма.

В целом, конечно, данный вопрос представляет собой, в большей степени, академический интерес (кстати, неплохая иллюстрация закона дырявых абстракций): на практике в 99.9% случаев проблем из-за текущей реализации метода Single не будет. Если же для Вас метод Single стал проблемой, замените его на собственный extension method.

На этом с LINQ To Objects на сегодня закончим - поговорим о LINQ To Entities и его реализации метода Single. Напомню, что в EF v1 метод Single не поддерживался: приходилось либо довольствоваться First, либо использовать разные костыли, например, вот этот. Проблема приведенного по ссылке workaround'а в том, что при вызове query.Count из базы будут возвращены все удовлетворяющие запросу записи (в том числе и дублирующиеся). В случае, если мы обращаемся к "тяжелым" данным, результат может быть плачевным.

Так как же с Single обстоят дела в EF 4? Добравшись до VS 2010, я был приятно удивлен - работает. Но маленький параноик в моей голове убедил меня (спасибо ему за это) открыть Profiler и посмотреть на генерируемый SQL-код. А вот и он:

SELECT TOP (2) 
[Extent1].[AddressId] AS [AddressId], 
[Extent1].[City] AS [City], 
[Extent1].[Street] AS [Street], 
[Extent1].[PostalCode] AS [PostalCode], 
[Extent1].[Apartment] AS [Apartment]
FROM [dbo].[Addresses] AS [Extent1]
WHERE 1 = [Extent1].[AddressId]

Данный код при наличии дубликатов возвращает две записи. Это, конечно, чуть лучше, чем решение, обсуждавшееся выше (там возвращалось неограниченное число дубликатов), но хотелось бы большего: хотелось бы, чтобы вопрос наличия дубликатов решался на стороне СУБД (например, при помощи подзапросов), а возвращалась бы либо одна (уникальная) запись, либо вообще ничего (если есть дубликаты).

За комментариями я в очередной раз обратился на форумы MSDN (прекрасное место :) ). Прежде всего, меня интересовало, финальное ли это решение для EF 4. Как Вы можете судить по ответу, шансов на то, что это поведение изменится до релиза .NET 4, мало.

На этой печальной ноте и закончим сегодняшний разговор о LINQ.