Quale algoritmo di ordinamento viene utilizzato da LINQ "OrderBy"?

Evidentemente "OrderBy" di LINQ era stato originariamente specificato come instabile, ma al momento di Orca era specificato come stabile. Non tutta la documentazione è stata aggiornata di conseguenza - in considerazione tali link:Quale algoritmo di ordinamento viene utilizzato da LINQ "OrderBy"?

Ma se OrderBy di LINQ è ormai "stabile", allora vuol dire che non sta usando una quicksort (che è intrinsecamente instabile) anche se qualche documentazione (ad es. il libro di Troy) dice che lo è. Quindi la mia domanda è: se non Quicksort, qual è l'algoritmo che LINQ sta usando?

fonte

2010-05-07 Brent Arias

stictly, 'OrderBy' di Linq non è specificato per la stabilità. 'Enumerable.OrderBy' è specificato come stabile, altri provider sono liberi di offrire questa promessa ma potrebbero non farlo. Fare ciò potrebbe essere impossibile o molto costoso (considerare l'impatto che avrebbe sulla parallelizzazione in termini di p-linq per esempio) o relativamente economico, che è una grande influenza su ciò che i provider faranno. –

Un post molto correlato [qui] (https://stackoverflow.com/q/148074/465053). – RBT

Per LINQ to Objects, è un Quicksort stabile che viene utilizzato. Per qualsiasi altro tipo di LINQ, viene lasciato all'implementazione sottostante.

fonte

2010-05-07 22:57:55

Se ho un oggetto referenziato come solo "IEnumerable " come fa Linq a sapere se si tratta di Linq-to-Objects o qualcosa del genere altro? – Dai

IEnumerable è sempre Linq per gli oggetti (vs IQueryable che è Linq per qualsiasi altra cosa) – John

@Dai IEnumerable è un'interfaccia, quindi in realtà dipende dal tipo di raccolta sottostante (non sono d'accordo con @John). Ad esempio, l'elenco implementa IEnumerable e potresti avere un elenco dichiarato come IEnumerable . Se si esegue un ordine in questo elenco, viene utilizzato il provider Linq-to-Object. D'altra parte.DbSet implementa anche IEnumerable . Se si esegue un ordine da questo DbSet, anche se è dichiarato come IEnumerable, verrà utilizzato il provider Linq-to-sql. Se si desidera utilizzare linq-to-objects su un dbset, è possibile eseguire dbset.AsEnumerable(). OrderBy (lambda) –

Sono inteso che OrderBy viene tradotto in SQL che esegue l'ordinamento sul database. Almeno nel caso di LINQ to SQL

fonte

2010-05-07 22:32:56

Sì, ma è vero solo per Linq to SQL e altri provider Linq di database. Linq non è solo un ORM ... (Linq to Objects, Linq to XML ...) –

+1 Per considerare qualcosa di diverso da LINQ agli oggetti –

all'avviamento riflettore, aperto a System.Linq.EnumerableSorter rivela che Linq2Objects utilizza la pratica ordinamento

fonte

2010-05-07 22:41:06 LorenVS

+1 per cercarlo su –

+1 per cercarlo su – helios456

+1 per cercandolo. Ma un semplice test non mostra n^2 crescita nel consumo di tempo in quanto aumenta il numero di elementi dell'elenco inverso ordinato di int, come dovrebbe essere secondo en.wikipedia.org/wiki/Quicksort Ho provato elementi 1k e 1M worst-case - time il consumo è aumentato solo di circa 50 volte – EvAlex

Quicksort viene utilizzato, ma il motivo per cui è stabile è perché gli indici di ciascuna coppia di elementi vengono confrontati se tutti i tasti sono uguali.

In altre parole, è possibile rendere stabile qualsiasi quicksort includendo nella funzione di confronto un confronto degli indici originali dei due elementi come ripiego.

Fonte

: http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1395017e067e5a34

fonte

2015-05-07 04:49:20

cool. Non lo sapevo – AaronHS

Quale algoritmo di ordinamento viene utilizzato da LINQ "OrderBy"?

risposta

Problemi correlati