Articles

Che cosè lordinamento?


Migliore risposta

In informatica, un algoritmo di ordinamento è un algoritmo che mette gli elementi di una lista in un certo ordine. Gli ordini utilizzati più di frequente sono lordine numerico e lordine lessicografico. Un ordinamento efficiente è importante per ottimizzare lefficienza di altri algoritmi (come algoritmi di ricerca e unione) che richiedono che i dati di input siano in elenchi ordinati. Lordinamento è spesso utile anche per canonizzare i dati e per produrre output leggibile dalluomo. Più formalmente, loutput di qualsiasi algoritmo di ordinamento deve soddisfare due condizioni:

  • Loutput è in ordine non decrescente (ogni elemento non è più piccolo dellelemento precedente secondo lordine totale desiderato);
  • Loutput è una permutazione (un riordino, pur mantenendo tutti gli elementi originali) dellinput.

Inoltre, i dati di input sono spesso memorizzati in un array, che consente laccesso casuale, piuttosto che un elenco, che consente solo laccesso sequenziale; sebbene molti algoritmi possano essere applicati a entrambi i tipi di dati dopo unadeguata modifica.

Gli algoritmi di ordinamento sono spesso indicati come una parola seguita dalla parola “sort” e grammaticalmente sono usati in inglese come frasi nominali, per esempio nella frase, “è inefficiente usare lordinamento per inserzione su elenchi di grandi dimensioni”, la frase lordinamento per inserzione si riferisce allalgoritmo di ordinamento dellordinamento per inserzione.

Risposta

Ordinare un miliardo di oggetti è sicuramente a portata di mano se riesci a tenerli nella memoria. Hai bisogno di un confronto tra O (n log n), giusto? Se non puoi, puoi ordinare ciò che sta nella memoria del tuo computer (o computer se hai un sistema distribuito) e raggruppare i risultati. A un certo punto negli anni 90 un merge sort modificato aveva il record mondiale di velocità e un super lineare per velocità della CPU.

Unaltra cosa che fai è quando N diventa grande (o effettivamente ogni volta che qualcosa diventa lento per input ragionevoli) dai unocchiata più da vicino a ciò di cui hai veramente bisogno.

Perché hai bisogno di ordinare gli oggetti? Se stai solo cercando duplicati ci sono modi molto più veloci! Se vuoi elaborare il 5\% inferiore (o superiore) ci sono algoritmi O (n) che possono partizionare in base al post posizione di ordinamento!

Quando le cose diventano lente guardi cosa sta facendo, e prima di capire se questo è lalgoritmo più veloce fai qualunque cosa sia, capisci se è effettivamente la cosa giusta da fare (Eccezione: se la “qualunque cosa” più veloce è un thin già sottoposto a debug che puoi semplicemente inserire, allora potrebbe essere meglio farlo … come se ti trovassi e testando se un array contiene qualche elemento molte volte può essere più semplice sostituire larray con un set e vedere se ora è abbastanza veloce da non preoccuparti che se facessi altre sei ore di ricerca potresti eliminarne la metà gli assegni o altro).

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *