Java e .NET: perché vengono utilizzati diversi algoritmi di ordinamento per impostazione predefinita?

Question

Java e .NET: perché vengono utilizzati diversi algoritmi di ordinamento per impostazione predefinita?

#1 da (17 voti)
#2 da (12 voti)
#3 da (10 voti)

19

Ti stai chiedendo perché Java e .NET Framework utilizzano per impostazione predefinita un diverso algoritmo di ordinamento.

In Java Array.Sort() utilizza l'algoritmo Unisci ordinamento per impostazione predefinita e come Wikipedia.com dice:

In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted

In .NET Framework Array.Sort/List.Sort() utilizza Ordinamento rapido come algoritmo di ordinamento predefinito (< a href="http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx"> MSDN ):

List.Sort() uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

Osservando la grande tabella "Confronto degli algoritmi" possiamo vedere che entrambi gli algoritmi hanno un comportamento abbastanza diverso dal peggiore caso e utilizzo della memoria:

Sia Java che .NET sono ottimi framework per lo sviluppo di soluzioni Enterprise, entrambi hanno piattaforme per lo sviluppo embedded. Quindi, perché utilizzano di solito un algoritmo di ordinamento diverso, qualsiasi idea?

java language-design .net algorithms sorting

posta sll 15.09.2011 - 22:07

fonte

3 risposte

17

Diversi team di sviluppo in due diverse società hanno tratto conclusioni diverse riguardo al solito caso d'uso per i loro quadri e componenti e hanno deciso di implementarlo di conseguenza.

Essenzialmente, ciascuna società ha fatto la propria analisi, ha esaminato la propria base di clienti e preso decisioni diverse di conseguenza.

Non puoi aspettarti analisi da parte di aziende e team diversi, utilizzando ipotesi e dati grezzi per giungere alla stessa conclusione.

risposta data 15.09.2011 - 22:09

fonte

12

Questa domanda è un po 'obsoleta, dal momento che Java ora utilizza Timsort (come di Java 7)

Degli specifici algoritmi citati:

Quicksort ha prestazioni peggiori in O (n ^ 2), ma è un po 'più leggero / richiede meno memoria, quindi offre prestazioni migliori in un caso tipico.
Mergesort ha garantito le prestazioni nel caso peggiore con O (n log n), ma comporta un sovraccarico e requisiti di memoria un po 'più alti. È anche automaticamente stabile (cioè mantiene gli elementi uguali nello stesso ordine).

I designer Java sembrano in generale essere un po 'più conservatori / concentrati sulla "cosa giusta", quindi non sorprende che abbiano scelto Mergesort tra i due in quanto offre migliori garanzie.

Non sei sicuro del motivo per cui Microsoft ha scelto Quicksort, forse anche se avrebbe potuto farli apparire migliori in alcuni micro-benchmark?

risposta data 29.09.2011 - 11:14

fonte

Leggi altre domande sui tag java language-design .net algorithms sorting

Cosa significa fare un "controllo nullo" in C o C ++? Noda Time vs Joda Time?

score 10 · Accepted Answer

Per quanto deterministici siano i computer stessi, l'ingegneria informatica non è una scienza esatta. Due persone, dato lo stesso dominio del problema, eseguiranno un'analisi e svilupperanno due diverse soluzioni che soddisfano tutti i vincoli del problema. Potrebbe essere difficile o impossibile determinare empiricamente quale di questi è "migliore" nel caso generale.

La mia ipotesi è che .NET QuickSort sia sovrapposto a qualcosa negli MFC o nelle API di Windows, ed è probabilmente ereditato da versioni molto vecchie di Windows in cui il vantaggio multi-threadable di MergeSort non sarebbe stato nemmeno preso in considerazione per i computer del giorno. ( EDIT: non lo è, sebbene gli sviluppatori Microsoft siano stati fan di QuickSort da molto tempo, come evidenziato da questa scelta di implementazione di ordinamento da MS-DOS).

Java, che non può utilizzare alcuna implementazione specifica della piattaforma perché Java è stato progettato da zero per essere completamente indipendente dalla piattaforma, è andato in un modo diverso. Chissà perché MergeSort è uscito in cima; la mia ipotesi è che l'implementazione abbia vinto una sorta di competizione per le prestazioni rispetto ad altri tipi creati dagli sviluppatori, oppure che un MergeSort di tipo O (n) è apparso migliore sulla carta in termini di prestazioni best-case e worst-case (MergeSort non ha tallone d'Achille relativo alla selezione di elementi come QuickSort, e il suo best-case è un elenco quasi ordinato mentre quello è spesso il peggiore di QuickSort). Dubito che i benefici di multithreading siano stati inizialmente considerati, ma l'implementazione attuale potrebbe essere multithreading.