Ответ 1

Да, я нахожу это немного странным, особенно потому, что перегрузка, которая не принимает предикат (т.е. работает только с последовательностью), похоже, имеет "оптимизацию" быстрого броска.

Однако в защите BCL я бы сказал, что исключение InvalidOperation, которое Single throws представляет собой исключенное из соображений исключения, которое обычно не должно используется для управления потоком. Не нужно, чтобы такие случаи были оптимизированы библиотекой.

Код, который использует Single, где нулевые или множественные совпадения являются вполне допустимой возможностью, например:

try
{
     var item = source.Single(predicate);
     DoSomething(item);
}

catch(InvalidOperationException)
{
     DoSomethingElseUnexceptional();    
}

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

var firstTwo = source.Where(predicate).Take(2).ToArray();

if(firstTwo.Length == 1) 
{
    // Note that this won't fail. If it does, this code has a bug.
    DoSomething(firstTwo.Single()); 
}
else
{
    DoSomethingElseUnexceptional();
}

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

Это оставляет нам два случая:

• Утверждение: Существует одно совпадение. В этом случае мы хотим, чтобы Single потреблял всю последовательность, чтобы утверждать наше требование. Там нет выгоды для "оптимизации". На самом деле можно утверждать, что примерная реализация "оптимизации", предоставляемая OP, будет на самом деле медленнее из-за проверки каждой итерации цикла.
• Утверждение не выполняется: есть нулевые или множественные совпадения. В этом случае мы делаем бросок позже, чем мы могли, но это не так уж и сложно, поскольку исключение простужено: указывает на ошибку, которая должна быть исправлена.

Подводя итог, если "плохая реализация" кусает вас по производительности в производстве, либо:

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

РЕДАКТИРОВАТЬ: Уточнил мою точку зрения.

EDIT: Здесь допустимое использование Single, где ошибка указывает на ошибки в вызывающем коде (неверный аргумент):

public static User GetUserById(this IEnumerable<User> users, string id)
{
     if(users == null)
        throw new ArgumentNullException("users");

     // Perfectly fine if documented that a failure in the query
     // is treated as an exceptional circumstance. Caller job 
     // to guarantee pre-condition.        
     return users.Single(user => user.Id == id);    
}

Ответ 2

Update:
Я получил очень хорошие отзывы к моему ответу, что заставило меня задуматься. Таким образом, я сначала предоставлю ответ, который излагает мою" новую" точку зрения; вы можете найти мой первоначальный ответ чуть ниже. Обязательно прочитайте комментарии между ними, чтобы понять, где мой первый ответ пропустил точку.

Новый ответ:

Предположим, что Single должен генерировать исключение, если его предварительное условие не выполняется; то есть, когда Single обнаруживает, что либо нет, либо более одного элемента в коллекции соответствует предикату.

Single может преуспеть, не выбрасывая исключение, просматривая всю коллекцию. Он должен убедиться, что есть только один подходящий элемент, поэтому ему нужно будет проверить все элементы в коллекции.

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

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

Таким образом, на самом деле правильно, что Single может генерировать исключение раньше; но это не обязательно, потому что практически нет никакой дополнительной выгоды.

Старый ответ:

Я не могу дать техническую причину, почему этот метод реализуется так, как он есть, поскольку я не реализовал его. Но я могу изложить свое понимание цели оператора Single, и оттуда сделаю мой личный вывод о том, что это действительно плохо реализовано:

Мое понимание Single:

Какова цель Single и как она отличается от, например, First или Last?

Использование оператора Single в основном выражает одно предположение, что из коллекции нужно возвращать ровно один элемент:

• Если вы не укажете предикат, это должно означать, что коллекция должна содержать ровно один элемент.

• Если вы указываете предикат, это должно означать, что точно один элемент в коллекции должен удовлетворять этому условию. (Использование предиката должно иметь тот же эффект, что и items.Where(predicate).Single().)

Это делает Single отличным от других операторов, таких как First, Last или Take(1). Ни у одного из этих операторов нет требования о том, что должен быть ровно один (соответствующий) элемент.

Когда следует Single вызывать исключение?

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

Когда следует использовать Single?

Использование Single подходит, когда ваша программная логика может гарантировать, что коллекция предоставит ровно один элемент и только один элемент. Если возникает исключение, это должно означать, что ваша программная логика содержит ошибку.

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

Вывод:

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

Ответ 3

При рассмотрении этой реализации мы должны помнить, что это BCL: общий код, который должен работать достаточно хорошо во всех сценариях.

Сначала выполните следующие сценарии:

• Итерируйте более 10 чисел, где первый и второй элементы равны
• Итерируйте более 1.000.000 чисел, где первый и третий элементы равны.

Оригинальный алгоритм будет работать достаточно хорошо для 10 предметов, но 1M будет иметь серьезную трату циклов. Поэтому в тех случаях, когда мы знаем, что есть два или более ранних последовательностей, предлагаемая оптимизация будет иметь приятный эффект.

Затем просмотрите эти сценарии:

• Итерируйте более 10 чисел, где первый и последний элементы равны
• Итерируйте более 1.000.000 чисел, где первый и последний элементы равны.

В этих сценариях алгоритм по-прежнему требуется для проверки каждого элемента в списках. Нет ярлыка. Оригинальный алгоритм будет работать достаточно хорошо, он выполняет контракт. Изменение алгоритма, вводя if на каждой итерации, фактически снизит производительность. Для 10 предметов это будет незначительно, но 1M это будет большой успех.

IMO, первоначальная реализация является правильной, поскольку она достаточно хороша для большинства сценариев. Знать, что реализация Single хороша, потому что это позволяет нам принимать разумные решения на основе того, что мы знаем о тех последовательностях, в которых мы его используем. Если измерения производительности в одном конкретном сценарии показывают, что Single вызывает узкое место, хорошо: тогда мы можем реализовать наш собственный вариант, который лучше работает в этом конкретном сценарии.

Обновление: как CodeInChaos и Eamon правильно указали, тест if, представленный в оптимизации, действительно не, выполняемый для каждого элемента, только внутри блока соответствия предикатов. В моем примере я полностью игнорировал тот факт, что предлагаемые изменения не повлияют на общую производительность реализации.

Я согласен с тем, что введение оптимизации, вероятно, принесет пользу всем сценариям. Хорошо видеть, что в конечном итоге решение о внедрении оптимизации выполняется на основе измерений производительности.

Ответ 4

Я думаю, что это преждевременная оптимизация "ошибка".

Почему это НЕ разумное поведение из-за побочных эффектов

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

Хотя это разумный аргумент, он сталкивается с общей практикой в ​​библиотеках LINQ: они используют ленивую оценку повсюду. Это не общая практика, чтобы полностью перечислить последовательности, кроме случаев, когда это абсолютно необходимо; действительно, несколько методов предпочитают использовать IList.Count, когда они доступны по любой итерации вообще, даже если эта итерация может иметь побочные эффекты.

Кроме того, .Single() без предиката не проявляет этого поведения: оно завершается как можно скорее. Если аргумент заключался в том, что .Single() должен учитывать побочные эффекты перечисления, вы ожидаете, что все перегрузки сделают это эквивалентно.

Почему случай для скорости не выполняется

Питер Лиллевольд сделал интересное наблюдение, что это может быть быстрее сделать...

foreach(var elem in elems)
    if(pred(elem)) {
        retval=elem;
        count++;
    }
if(count!=1)...

чем

foreach(var elem in elems)
    if(pred(elem)) {
        retval=elem;
        count++;
        if(count>1) ...
    }
if(count==0)...

В конце концов, вторая версия, которая выйдет из итерации сразу после обнаружения первого конфликта, потребует дополнительного теста в цикле - теста, который в "правильном" является чисто балластом. Нейтральная теория, правильно?

За исключением того, что не вырваться цифрами; например, на моей машине (YMMV) Enumerable.Range(0,100000000).Where(x=>x==123).Single() на самом деле быстрее, чем Enumerable.Range(0,100000000).Single(x=>x==123)!

Возможно, это уловка JITTER этого точного выражения на этой машине - я не утверждаю, что Where, за которым следует предикат Single всегда быстрее.

Но независимо от того, что неудачное решение вряд ли будет значительно медленнее. В конце концов, даже в нормальном случае, мы имеем дело с дешевой ветвью: веткой, которая никогда не берется и, таким образом, легко на предикторах ветвей. И, конечно же; ветвь далее встречается только когда претит - это один раз за вызов в обычном случае. Эта стоимость просто незначительна по сравнению со стоимостью делегированного вызова pred и его реализации, а также стоимостью методов интерфейса .MoveNext() и .get_Current() и их реализаций.

Просто крайне маловероятно, что вы заметите ухудшение производительности, вызванное одной предсказуемой ветвью, по сравнению со всем другим штрафом за абстракцию - не говоря уже о том, что большинство последовательностей и предикатов действительно что-то делают сами.

Ответ 5

Мне кажется очень понятным.

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

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

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

Ответ 6

Это, по-моему, плохое выполнение.

Чтобы проиллюстрировать потенциальную серьезность проблемы:

var oneMillion = Enumerable.Range(1, 1000000)
                           .Select(x => { Console.WriteLine(x); return x; });

int firstEven = oneMillion.Single(x => x % 2 == 0);

Вышеуказанное выведет все целые числа от 1 до 1000000, прежде чем выбросить исключение.

Это голова-скребок наверняка.

Ответ 7

Я нашел этот вопрос только после подачи отчета https://connect.microsoft.com/VisualStudio/feedback/details/810457/public-static-tsource-single-tsource-this-ienumerable-tsource-source-func-tsource-bool-predicate-doesnt-throw-immediately-on-second-matching-result#

Аргумент побочного эффекта не содержит воды, потому что:

• Побочные эффекты на самом деле не являются функциональными, и они называются Func по какой-либо причине.
• Если вам нужны побочные эффекты, не имеет никакого смысла утверждать, что версия, которая имеет побочные эффекты на протяжении всей последовательности, является желательной, чем это требуется для версии, которая сразу бросается.
• Он не соответствует поведению First или другой перегрузки Single.
• Он не соответствует, по крайней мере, некоторым другим реализациям Single, например. Linq2SQL использует TOP 2 для обеспечения возврата только двух совпадающих случаев, необходимых для проверки более чем одного соответствия.
• Мы можем построить случаи, когда мы должны ожидать, что программа остановится, но она не останавливается.
• Мы можем построить случаи, когда бросается OverflowException, что не является документированным поведением и, следовательно, явно ошибкой.

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

Edit:

Питер Лиллевольд упоминает о повторном тесте, может быть причиной, по которой автор решил использовать подход, который они сделали, в качестве оптимизации для случая, не связанного с исключительным случаем. Если так, то это было бесполезно, хотя, даже в стороне от Eamon Nerbonne, показывающего, что это не улучшилось бы много. В первом цикле нет необходимости повторять тест, так как мы можем просто изменить то, что мы тестируем для первого совпадения:

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
  if(source == null)
    throw new ArgumentNullException("source");
  if(predicate == null)
    throw new ArgumentNullException("predicate");
  using(IEnumerator<TSource> en = source.GetEnumerator())
  {
    while(en.MoveNext())
    {
      TSource cur = en.Current;
      if(predicate(cur))
      {
        while(en.MoveNext())
          if(predicate(en.Current))
            throw new InvalidOperationException("Sequence contains more than one matching element");
       return cur;
      }
    }
  }
  throw new InvalidOperationException("Sequence contains no matching element");
}