Perché java non usa un ordinamento digitale su primitive?

11

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) è implementato come un "quicksort sintonizzato" piuttosto che un ordinamento digitale.

Ho fatto un paragone di velocità qualche tempo fa, e con qualcosa come n > 10000, l'ordinamento radix era sempre più veloce. perché?

    
posta Jakob Weisblat 28.02.2012 - 05:53
fonte

2 risposte

17

Vorrei ipotizzare che:

  • Array.sort è implementato come quicksort, perché quicksort può ordinare qualsiasi cosa in un tempo decente dato un comparatore.
  • L'ordinamento di un elenco di 10000 voci non è così comune. L'accesso a una struttura dati di 10000 o più elementi è piuttosto comune. Se è necessario mantenere l'ordine, un albero di ricerca bilanciato è spesso un modo migliore per andare che ordinare l'intero array ogni volta che è necessario l'elemento più piccolo.
  • L'ordinamento delle primitive non è così comune, nonostante ciò che l'università può insegnare.

Il punto è, non è un caso d'uso comune, che l'ottimizzazione deve essere nella libreria standard. Se hai scritto un'applicazione, che ha problemi di prestazioni, in cui determini attraverso il profiling che l'ordinamento di un array di 10000+ ints è effettivamente il collo di bottiglia, allora potresti anche scrivere l'ordinamento a mano o riconsiderare il tuo scelta della struttura dei dati in primo luogo.

    
risposta data 28.02.2012 - 07:13
fonte
6

Back2dos ha detto tutto, cercherò solo di chiarire ulteriormente il punto che ritengo sia il più importante:

L'ordinamento radix può solo ordinare i valori primitivi effettivi contenuti nell'array, in base ai loro modelli di cifre binarie. In scenari reali di ingegneria del software nel mondo reale, questo caso si incontra quasi mai . Quello che tendiamo a fare molto più spesso è l'ordinamento di matrici di strutture dati più complesse (non primitive), e alcune volte ordiniamo matrici di indici ad altre entità.

Ora, una matrice di indici ad altre entità è in realtà una matrice di primitive, ma l'ordinamento è fornito dall'interfaccia di confronto (e / o delegato in C #) che non confronta gli indici, ma le entità indicizzate dal indici. Pertanto, l'ordinamento non ha assolutamente alcuna relazione con l'ordine dei valori delle primitive, e quindi l'ordinamento di radice è assolutamente inutile per questo scenario.

Un esempio:

Abbiamo una serie di stringhe: [0]="Mike", [1]="Albert", [2]="Zoro". Quindi dichiariamo una matrice di indici per tali stringhe: [0] = 0, [1] = 1, [2] = 2. Quindi, ordiniamo l'array di indici, passandogli un comparatore che non confronta gli stessi indici, ma le stringhe effettivamente riferite da questi indici. Dopo l'ordinamento, la matrice risultante di indici sarà simile a questa: [0] = 1, [1] = 0, [2] = 2. Come puoi vedere, questo ordinamento non ha nulla a che fare con i modelli binari dei valori contenuti nell'array, e tuttavia attraversando questa matrice di indici e recuperando ogni stringa corrispondente, visitiamo le stringhe in ordine ordinato.

    
risposta data 28.02.2012 - 15:47
fonte

Leggi altre domande sui tag