Плохая реализация Enumerable.Single?

Question

Я сталкивался с этой реализацией в Enumerable.cs по рефлектору.

public static TSource Single<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    //check parameters
    TSource local = default(TSource);
    long num = 0L;
    foreach (TSource local2 in source)
    {
        if (predicate(local2))
        {
            local = local2;
            num += 1L;
            //I think they should do something here like:
            //if (num >= 2L) throw Error.MoreThanOneMatch();
            //no necessary to continue
        }
    }
    //return different results by num's value
}

Я думаю, что они должны разорвать петлю, если существует более 2 предметов, удовлетворяющих условию, почему они всегда перебирают всю коллекцию? В случае, если этот отражатель неправильно разбирает dll, я пишу простой тест:

class DataItem
{
   private int _num;
   public DataItem(int num)
   {
      _num = num;
   }

   public int Num
   {
      get{ Console.WriteLine("getting "+_num); return _num;}
   }
} 
var source = Enumerable.Range(1,10).Select( x => new DataItem(x));
var result = source.Single(x => x.Num < 5);

Для этого тестового примера, я думаю, он напечатает «получение 0, получение 1», а затем выдаст исключение. Но правда в том, что он «получает 0 ... получает 10» и создает исключение. Есть ли какая-либо алгоритмическая причина, по которой они реализуют этот метод следующим образом?

РЕДАКТИРОВАТЬ Некоторые из вас думали, что это из-за побочных эффектов предикатного выражения , после глубокого размышления и некоторых тестовых случаев я пришел к выводу, что побочные эффекты в данном случае не имеет значения . Пожалуйста, приведите пример, если вы не согласны с этим выводом.

Answer 1

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

---

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

Код, который использует 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, должен использоваться для представления ошибок в программе (либо в методе, выполняющем запрос, либо в аргументах, передаваемых ему вызывающей стороной).

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

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

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

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

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

РЕДАКТИРОВАТЬ: Вот действительное использование 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's job 
     // to guarantee pre-condition.        
     return users.Single(user => user.Id == id);    
}

Answer 2

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

Новый ответ:

Предположим, что 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 нарушается, как только он обнаруживает второй (соответствующий) элемент в коллекции.

Answer 3

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

Сначала возьмем следующие сценарии:

1. Итерация по 10 числам, где первый и второй элементы равны
2. Итерация по 1.000.000 чисел, где первый и третий элементы равны

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

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

1. Итерация по 10 числам, где первый и последний элементы равны
2. Итерация по 1.000.000 чисел, где первый и последний элементы равны

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

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

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

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

Answer 4

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

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

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

Хотя это разумный аргумент, он идет вразрез с общей практикой в ​​библиотеках 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) * ​​1030 * на самом деле быстрее , чем Enumerable.Range(0,100000000).Single(x=>x==123)!

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

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

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

Answer 5

Мне кажется, это очень ясно.

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

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

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

Answer 6

На мой взгляд, это плохая реализация.

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

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

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

Приведенное выше будет выводить все целые числа от 1 до 1000000 перед выдачей исключения.

Это, конечно, головокружение.

Answer 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#

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

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

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

Edit:

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

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");
}