C: metodi di ordinamento Analisi

voti
7

Ho un sacco di diversi algoritmi di ordinamento che tutti hanno la seguente firma:

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);

Ci sono le suite di test per l'ordinamento che ho potuto utilizzare con lo scopo di fare confronti empirici?

È pubblicato 27/08/2009 alle 04:52
fonte dall'utente
In altre lingue...                            


4 risposte

voti
10

Questa discussione dettagliata , così come il collegamento a un gran numero di pagine web correlati che si possono trovare utili, descrive anche un utile set di dati di input per testare algoritmi di ordinamento (si veda la pagina collegata per ragioni). riassumendo:

  1. matrice completamente rimescolato casuale
  2. Matrice già ordinato
  3. Già ordinati in ordine ordine inverso
  4. matrice motosega
  5. Array di elementi identici
  6. Già filtrate array con permutazioni N (con N da 0,1 a 10% della dimensione)
  7. Matrice già ordinati in ordine di sequenza inversa con N permutazioni
  8. I dati che hanno distribuzione normale con chiavi duplicate (o chiudi) (per l'ordinamento stabile solo)
  9. Dati pseudocasuali (valori giornalieri del S & P500 o altro indice per un decennio potrebbe essere un buon test qui impostato, sono disponibili da Yahoo.com)
Risposto il 02/09/2009 a 11:10
fonte dall'utente

voti
7

Lo studio definitivo di ordinamento è Bob Sedgewick tesi di dottorato 's. Ma ci sono un sacco di buone informazioni nei suoi algoritmi libri di testo, e questi sono i primi due posti vorrei cercare suite di test e la metodologia. Se hai avuto un corso di recente saprete più di me; ultima volta avevo un corso, il metodo migliore era usare Quicksort giù a partizioni di dimensione 12, quindi eseguire inserzione sull'intera matrice. Ma le risposte cambiano più rapidamente l'hardware.

Programmazione Perls libri di Jon Bentley hanno qualche altra informazione su di ordinamento.

È possibile montare rapidamente una suite di test che contiene

  • interi casuali

  • interi ordinati

  • Reverse numeri interi ordinati

  • interi ordinati, leggermente perturbata

Se la memoria non serve, questi sono i casi più importanti per un algoritmo di ordinamento.

Se stai cercando di ordinare le matrici che non si adatta nella cache, è necessario misurare gli effetti della cache. valgrindè efficace se lento.

Risposto il 27/08/2009 a 05:22
fonte dall'utente

voti
3

sortperf.py dispone di una suite ben selezionato di casi di test di benchmark ed è stato utilizzato per sostenere il saggio trovato qui e fare timsort il tipo in Python lo che molti anni fa. Si noti che, finalmente, Java può essere in movimento a timsort troppo, grazie a Josh Block (vedi qui ), quindi immagino che hanno scritto la propria versione dei casi di test di benchmark - tuttavia, non riesco a trovare facilmente un riferimento ad esso. (timsort, una stalla, adattativo, iterativo variante Mergesort naturale, è particolarmente adatto alle lingue con la semantica di riferimento-a-oggetto come Python e Java, dove "lo spostamento dei dati" è relativamente a buon mercato [[dal momento che tutto ciò che sia mai essere spostato è riferimenti aka puntatori , non gocce di dimensione illimitata ;-)]], ma i confronti possono essere relativamente costosi `in quanto non v'è alcun limite superiore alla complessità di una funzione di confronto - ma allora questo vale per tutte le lingue in cui l'ordinamento può essere personalizzato tramite un confronto personalizzato o function` chiave di estrazione).

Risposto il 06/09/2009 a 02:15
fonte dall'utente

voti
3

Questo sito mostra i vari algoritmi di ordinamento utilizzando quattro gruppi: http://www.sorting-algorithms.com/

Oltre ai quattro gruppi di risposta di Norman si desidera controllare gli algoritmi di ordinamento con la raccolta di numeri che hanno alcune somiglianze nei numeri:

  • Tutti i numeri interi sono unici
  • Lo stesso numero intero in tutta la collezione
  • Poche chiavi univoche

Cambiando il numero di elementi della collezione è anche verificare una buona pratica ogni algoritmo con 1K, 1M, 1G ecc per vedere quali sono le implicazioni di memoria di tale algoritmo.

Risposto il 02/09/2009 a 10:51
fonte dall'utente

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more