Preservando o pedido com o LINQ

361

Eu uso instruções LINQ to Objects em uma matriz ordenada. Quais operações não devo executar para garantir que a ordem da matriz não seja alterada?

Matthieu Durut
fonte

Respostas:

645

Examinei os métodos de System.Linq.Enumerable , descartando qualquer que retornasse resultados não IEnumerable. Verifiquei as observações de cada um para determinar como a ordem do resultado seria diferente da ordem da fonte.

Preserva a ordem absolutamente. Você pode mapear um elemento de origem por índice para um elemento de resultado

  • AsEnumerable
  • Fundida
  • Concat
  • Selecione
  • ToArray
  • Listar

Preserva a ordem. Os elementos são filtrados ou adicionados, mas não são reordenados.

  • Distinto
  • Exceto
  • Interseção
  • OfType
  • Anexar (novo no .net 4.7.1)
  • Pular
  • SkipWhile
  • Toma
  • TakeWhile
  • Onde
  • Zip (novo no .net 4)

Destrói a ordem - não sabemos em que ordem esperar resultados.

  • ToDictionary
  • Procurar

Redefine o pedido explicitamente - use-os para alterar a ordem do resultado

  • Ordenar por
  • OrderByDescending
  • Reverter
  • ThenBy
  • ThenByDescending

Redefine o pedido de acordo com algumas regras.

  • GroupBy - Os objetos IGrouping são produzidos em uma ordem com base na ordem dos elementos na origem que produziram a primeira chave de cada IGrouping. Os elementos de um agrupamento são gerados na ordem em que aparecem na fonte.
  • GroupJoin - GroupJoin preserva a ordem dos elementos de externo e, para cada elemento de externo, a ordem dos elementos correspondentes de interno.
  • Unir - preserva a ordem dos elementos de externo e, para cada um desses elementos, a ordem dos elementos correspondentes de interno.
  • SelectMany - para cada elemento da origem, o seletor é chamado e uma sequência de valores é retornada.
  • União - Quando o objeto retornado por esse método é enumerado, a União enumera primeiro e segundo nessa ordem e gera cada elemento que ainda não foi produzido.

Editar: movi a ordem Distinct para Preserving com base nessa implementação .

    private static IEnumerable<TSource> DistinctIterator<TSource>
      (IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
    {
        Set<TSource> set = new Set<TSource>(comparer);
        foreach (TSource element in source)
            if (set.Add(element)) yield return element;
    }
Amy B
fonte
2
Na verdade, acho que Distinct preserva a ordem original (encontrada pela primeira vez) - então {1,2,1,3,1,3,4,1,5} seria {1,2,3,4,5}
Marc Gravell
10
msdn.microsoft.com/en-us/library/bb348436.aspx O método Distinct <(Of <(TSource>)>) (IEnumerable <(Of <(TSource>)>))) retorna uma sequência não ordenada que não contém valores duplicados .
Amy B
12
Marc: o que você diz pode ser verdade, mas seria uma má idéia confiar nesse comportamento.
Amy B
4
@ Amy B sim, mas não se aplica ao Linq to Objects. No Linq to Sql, distinct () coloca a palavra-chave distinta no sql gerado e a ordenação do sql não é garantida. Eu estaria interessado em ver uma implementação distinta para o linq to objetos que não preserva a ordem e é mais eficiente que uma que preserva a ordem. Por exemplo, você pode consumir toda a entrada e colocá-la em um hashset e, em seguida, gerar valores enumerando o hashset (ordem de perda), mas isso é pior. Então, sim, eu não me importo documentação desafiando a cada momento e, em seguida, :)
dan
4
Talvez a documentação (para o Distinctmétodo) tenha apenas a intenção de dizer "não classificado", não "em ordem imprevisível". Eu diria que Distinctpertence à categoria de filtragem acima, assim como Where.
Jeppe Stig Nielsen
34

Você está realmente falando sobre SQL ou sobre matrizes? Em outras palavras, você está usando o LINQ to SQL ou o LINQ to Objects?

Na verdade, os operadores LINQ to Objects não alteram sua fonte de dados original - eles constroem sequências efetivamente apoiadas pela fonte de dados. As únicas operações que alteram a ordem são OrderBy / OrderByDescending / ThenBy / ThenByDescending - e, mesmo assim, são estáveis ​​para elementos igualmente ordenados. Obviamente, muitas operações filtrarão alguns elementos, mas os elementos retornados estarão na mesma ordem.

Se você converter para uma estrutura de dados diferente, por exemplo, com ToLookup ou ToDictionary, não acredito que a ordem seja preservada nesse momento - mas, de qualquer maneira, isso é um pouco diferente. (A ordem dos valores mapeados para a mesma chave é preservada para pesquisas, acredito.)

Jon Skeet
fonte
portanto, como OrderBy é uma classificação estável, seq.OrderBy (_ => _.Key) colocará os elementos exatamente na mesma ordem que seq.GroupBy (_ => _.Key) .SelectMany (_ => _ ) Isso está correto?
dmg 01/02
11
@ dmg: Não, não vai. Apenas GroupByseguido por SelectManyfornecerá os resultados agrupados por chave, mas não em ordem crescente de chave ... ele os fornecerá na ordem em que as chaves ocorreram originalmente.
Jon Skeet
você está dizendo que o LINQ to SQL não preserva a ordem?
simbionte
@symbiont: Em muitas operações SQL não é de ordem bem definida para começar. Basicamente, estou tentando fazer promessas apenas sobre coisas que posso garantir - como LINQ to Objects.
Jon Skeet
@JonSkeet Se eu usar OrderBy, isso garante que 'n' objetos com a mesma chave preservem sua sequência original, exceto que eles estejam todos juntos. ie.:in list<x> {a b c d e f g}se c, d, e tiverem a mesma chave, a sequência resultante conterá c, d, e próximos um do outro E na ordem c, d, e. Não consigo encontrar uma resposta categórica baseada em MS.
Paulustrious 10/10
7

Se você estiver trabalhando em uma matriz, parece que você está usando LINQ-to-Objects, não SQL; Você pode confirmar? A maioria das operações do LINQ não reordena nada (a saída será na mesma ordem que a entrada) - portanto, não aplique outra classificação (OrderBy [Descending] / ThenBy [Descending]).

[editar: como Jon colocou mais claramente; O LINQ geralmente cria uma nova sequência, deixando os dados originais em paz.

Observe que inserir os dados em um Dictionary<,>(ToDictionary) embaralha os dados, pois o dicionário não respeita nenhuma ordem de classificação específica.

Mas as coisas mais comuns (Selecionar, Onde, Pular, Tomar) devem ficar bem.

Marc Gravell
fonte
Se não me engano, ToDictionary()simplesmente não faz promessas sobre a ordem, mas, na prática, mantém a ordem de entrada (até você remover algo dela). Não estou dizendo para confiar nisso, mas 'embaralhar' parece impreciso.
Timo
4

Encontrei uma ótima resposta em uma pergunta semelhante que faz referência à documentação oficial. Para citar:

Para Enumerablemétodos (LINQ to Objects, que se aplica a List<T>), você pode contar com a ordem dos elementos retornados por Select, Whereou GroupBy. Este não é o caso de coisas que são inerentemente não ordenadas, como ToDictionaryou Distinct.

Da documentação Enumerable.GroupBy :

Os IGrouping<TKey, TElement>objetos são produzidos em uma ordem com base na ordem dos elementos na origem que produziram a primeira chave de cada um IGrouping<TKey, TElement>. Os elementos de um agrupamento são gerados na ordem em que aparecem source.

Isso não é necessariamente verdadeiro para IQueryablemétodos de extensão (outros provedores LINQ).

Fonte: Os métodos enumeráveis ​​do LINQ mantêm a ordem relativa dos elementos?

Curtis Yallop
fonte
2

Qualquer 'agrupar por' ou 'ordenar por' possivelmente mudará a ordem.

leppie
fonte
0

A questão aqui se refere especificamente a LINQ-to-Objects.

Se você estiver usando o LINQ-to-SQL, não há pedido, a menos que você imponha um com algo como:

mysqlresult.OrderBy(e=>e.SomeColumn)

Se você não fizer isso com o LINQ-to-SQL, a ordem dos resultados poderá variar entre as consultas subseqüentes, mesmo os mesmos dados, o que pode causar um erro intermitente.

andrew pate
fonte