Сохранение порядка с LINQ

поэтому, поскольку OrderBy является стабильной сортировкой, тогда: seq.OrderBy (_ => _.Key) разместит элементы в том же порядке, что и seq.GroupBy (_ => _.Key) .SelectMany (_ => _ ). Это верно?

@dmg: Нет, не будет. Только GroupBy, за которым следует SelectMany, даст результаты, сгруппированные по ключам, но не в порядке возрастания ключей ... он выдаст их в том порядке, в котором ключи были изначально.

вы говорите, что LINQ to SQL не сохраняет порядок?

@symbiont: Во многих операциях SQL является не имеет четко определенного порядка для начала. В основном я пытаюсь давать обещания только в том, что я могу гарантировать, например, в LINQ to Objects.

@JonSkeet Если я использую OrderBy, гарантирует ли это, что n объектов с одним и тем же ключом сохранят свою исходную последовательность, за исключением того, что они все вместе. то есть: в list<x> {a b c d e f g}, если c, d, e все имеют один и тот же ключ, тогда результирующая последовательность будет содержать c, d, e рядом друг с другом AND в порядке c, d, e. Я не могу найти категорического ответа на основе MS.

@Paulustrious: в LINQ to Objects - да. У других поставщиков это зависит от реализации.

@JonSkeet Ты в порядке. Вы ответили, пока я редактировал свой вопрос

@Paulustrious: From msdn.microsoft.com/en-us/library/bb534966(v=vs.110).aspx: «Этот метод выполняет стабильную сортировку; то есть, если ключи двух элементов равны, порядок элементов сохраняется. Напротив, нестабильная сортировка не сохраняет порядок элементов, которые имеют тот же ключ ".

Если я не ошибаюсь, ToDictionary() просто не делает обещания о порядке, но на практике поддерживает порядок ввода (пока вы что-то из него не удалите). Я не говорю, что на это нужно полагаться, но «скремблирование» кажется неточным.

На самом деле, я думаю, что Distinct сохраняет исходный (первый найденный) порядок - поэтому {1,2,1,3,1,3,4,1,5} будет {1,2,3,4,5}

Марк: то, что вы говорите, может быть правдой, но было бы плохой идеей полагаться на такое поведение.

@Amy B Я думаю, что было бы неразумно реализовывать Distinct (для linq для объектов) таким образом, чтобы не сохранять порядок, поскольку это будет работать хуже, чем если бы оно сохраняло порядок.

@dan пожимать плечами, если вы хотите нарушить документацию, решать вам.

@Amy B да, но это не относится к Linq to Objects. В Linq to Sql отдельный () помещает ключевое слово unique в сгенерированный sql, и упорядочение из sql не гарантируется. Мне было бы интересно увидеть реализацию отдельной для linq для объектов, которая не сохраняет порядок и более эффективна, чем та, которая сохраняет порядок. Например, вы можете использовать весь ввод и поместить его в хэш-набор, а затем получить значения, перечислив хэш-набор (порядок потери), но это еще хуже. Так что да, я не против время от времени бросать вызов документации :)

@Dan «Найден первым» разрушает порядок. В этом списке 1 стоит до и после 4. Если сделать его отдельным списком, упорядочение исчезнет.

@Rangoric - зависит от вашего определения порядка сохранения. Если мы пойдем с FoundFirst for Distinct - можно предположить, что элементы фильтруются, а не переупорядочиваются. Единственная причина, по которой я не выбрал этот вариант, - это то, что в документации указано «неупорядоченный».

@ Эми, и вот почему. «Сначала найдено» - это не то же самое, что и «Отличное». Если наступит время, когда у кого-то есть способ сделать отличное, не сохраняя порядок, который быстрее, то, конечно, я не хочу сдерживать их из-за предположений.

Возможно, документация (для метода Distinct) просто имела в виду «несортированный», а не «в непредсказуемом порядке». Я бы сказал, что Distinct относится к указанной выше категории фильтрации, как и Where.

Я не уверен насчет select many, так как кроме двух foreach нет никаких других конструкций. О каком побочном эффекте вы говорите?

@Johnny_D Я подумал об использовании термина "побочный эффект" и решил отредактировать, поскольку он имеет значение в нашей области. Кроме того, когда я говорю о «сохранении порядка», я говорю с точки зрения изоморфизма порядка. Distinct и SelectMany не изоморфны по порядку.

Aren't Except, Intersect Union и т. д. Устанавливают операции? Я бы не поверил, что они вернутся в порядок. Это задокументировано?

@nawfal Intersect (msdn.microsoft.com/en-us/library/vstudio/…): «Наконец, отмеченные элементы выводятся в том порядке, в котором они были собраны». Except не документирует это, но его реализация, вероятно, будет очень похожей. Союз (msdn.microsoft.com/en-us/library/vstudio/…): цитата уже есть в ответе. Хотя эти операции можно описать как операции с наборами, они работают с IEnumerable <T>, и для их реализации имеет смысл иметь задокументированный порядок, основанный на порядке исходного IEnumerable.

@nawfal также обратите внимание: этот вопрос и ответ касаются LinqToObjects (методов System.Linq.Enumerable). Если вы используете Linq для чего-то еще (System.Linq.Queryable) - ничего из этого не применимо.

@AmyB Для ILookup: Объекты IGrouping <TKey, TElement> выдаются в порядке, основанном на порядке элементов в источнике, которые создали первый ключ каждого IGrouping <TKey, TElement>. Элементы в группе отображаются в том порядке, в котором они появляются в исходном тексте., взято из документации GroupBy. Поскольку ILookup имеет IGrouping, это гарантирует сохранение порядка, верно?

Но поиск поддерживается простым словарем: _dict = new Dictionary <TKey, IGrouping <TKey, TElement >> (_ comparer); Значит ли это, что Словарь сохраняет порядок?

@Amy B Простой словарь сохраняет порядок (хотя и недокументированный) до тех пор, пока не удаляются элементы, но в Уважать используется нет. Его внутренний метод GetGrouping () содержит реализацию хеш-таблицы с вышеупомянутыми указателями .next, которые будут использоваться в GetEnumerator () (строка 3288).

@ robert4 похоже, что ToLookup меняет порядок ключей, но элементы сохраняют порядок перечисляемого источника.

@HuBeZa можешь показать пример на dotnetfiddle.net? Мне это кажется невозможным. Вы говорите о Linq.Parallel или обычном (последовательном)?

@ robert4 взгляните на ToLookup, который вызывает Lookup.Create. Он запускается последовательно для перечисляемого источника и вызывает Grouping.Add, инкапсулирующий простой буфер массива.

@HuBeZa Это доказывает, что порядок элементов сохраняется внутри групп, что я не подвергал сомнению. Я противоречил первой половине вашего утверждения: «ToLookup меняет порядок ключей». Lookup.Create вызывает lookup.GetGrouping () для каждого элемента источника, который создает группы таким образом, чтобы сохранить порядок ключей, как я подробно описал выше.

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

@ZachMierzejewski Aggregate был исключен, поскольку он не возвращает IEnumerable. Без перечислимого результата порядок результатов не существует и не может быть определен как сохраненный или нет. Важно знать, что Aggregate обрабатывает ввод по порядку, как и все методы с источником IEnumerable.

Я думаю, это забавно, что никто никогда не просил меня перевести Union на Preserving Order ... у него такое же поведение Found First, как и у Distinct.

Так почему же, например, Skip (и другие вещи в списке сохраненного порядка) не возвращает IOrderedEnumerable?

@ruffin Было бы полезно подумать о том, для чего нужен IOrderedEnumerable<T>. Без этого интерфейса мы не смогли бы вызвать ThenBy. Есть ли смысл называть customers.Skip(5).ThenBy(c => c.Name)? Skip не определяет порядок - его реализация не меняет порядок.

Спасибо за ответ! Обратной стороной этого является заказ IEnumerableне гарантирует, и я бы не подумал, что могу рассчитывать на то, что что-то вернет IEnumerable «не меняет порядок». Было бы неприятно говорить, что функция, возвращающая неупорядоченный тип, гарантирует сохранение порядка неупорядоченного типа. Чего ждать? ; ^) Если customers имеет внутреннее представление о том, как он упорядочен (то есть формула, по которой он упорядочен, что, я признаю, я не думаю, что это так), то ваше использование Skip, по сути, имело бы смысл. orderedByCountyCustomers.Skip(5).ThenBy(c => c.Name)

Интересное продолжение вашего пункта в этом ответе Эрика Липперта и обсуждения со Скитом. По-прежнему кажется странным притворяться, что IEnumerable имеет порядок, который нужно сохранить, когда он не гарантирует порядок (то есть неявно неупорядочен) ... Я думаю, что, вероятно, мне лучше подумать, что IEnumerable может будет заказан, но не , сам по себе, гарантия ордер. IOrderedEnumerable, вероятно, тоже не лучшее название для того, что он делает ... IInTheProcessOfBeingOrderedEnumerable? / пожимает плечами Еще раз спасибо.

@ruffin большинство IEnumerable<T> имеют порядок (например, порядок индекса массива). Когда они это делают, порядок сохраняется операциями. Когда они этого не делают, нет порядка, который нужно сохранять. Все IOrderedEnumerable<T> имеют определенный порядок. Этот определенный порядок соблюдается и изменяется при обращении к ThenBy.

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