воскресенье, 4 октября 2009 г.

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.

9 комментариев:

Shaddix комментирует...

Очень многа букав и на мой взгляд более чем очевидный пример, который я лично промотал :)

Ну и решение/ответ тоже как-то разлилось по древу, а немаловажная деталь с мсдн-а осталась "непереведенной".

Стандартный юз-кейс Single предполагает всё-таки успех, а, следовательно, итерацию по всем элементам. Соответственно, ты готов ждать это время. То есть с задержкой на милиард элементов или долгим предикатом ты уже смирился.

Это не отменяет других аргументов (в том числе и против такой реализации), но просто имхо это тоже важный момент :)

Idsa комментирует...

>>Очень многа букав и на мой взгляд более чем очевидный пример, который я лично промотал :)

Были у меня сомнения по поводу необходимости примера... в итоге убрал его ввиду излишней очевидности.

>>Ну и решение/ответ тоже как-то разлилось по древу, а немаловажная деталь с мсдн-а осталась "непереведенной".

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

Вообще вся эта возня с реализацией Single для LINQ To Objects, по большому счету, ерунда... но все-таки хочется, чтобы хотя бы ключевые моменты .NET Framework'а были реализованы так, что ни прикопаешься.

Игорьбек комментирует...

На мой взгляд, здесь вообще лучше использовать итератор напрямую:

var en = source.GetEnumerator();
while (en.MoveNext())
{
var v = en.Current;
if (predicate(v))
{
while (en.MoveNext())
if (predicate(en.Current))
Error.MoreThanOneMatch();
return v;
}
}
Error.NotMatch();

Удивлен что так некачественно реализовано!

Игорьбек комментирует...

А вариант без предиката вообще прост:

if (!en.MoveNext()) Error.NotMatch();
var v = en.Current;
if (en.MoveNext()) Error.MoreThanOneMatch();
return v;

Игорьбек комментирует...

А вот эта коллекция убьет этот Single:

IEnumerable InfinityZero()
{ while (true) yield return 0; }

=)

Idsa комментирует...

>>На мой взгляд, здесь вообще лучше >>использовать итератор напрямую

А чем лучше, если компилятор может сделать это за нас?

Игорьбек комментирует...

> А чем лучше, если компилятор может сделать это за нас?

а вы посмотрите на приведенную мной реализацию и скажите, можно ли сделать через foreach также без использования счетчика? А через IEnumerator можно свободно использовать вложенный цикл.

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

oxfn комментирует...

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

Игорь Олейников комментирует...

Ого, через 3 года возобновили дискуссию =)

Конечно, мой код там не очень качественный, там надо в using обернуть конечно, но смысл не меняется.