algoritmo di ordinamento più efficiente per una vasta serie di numeri

Question

Sto lavorando su un grande progetto, non mi preoccupai di riassumere qui, ma questa sezione del progetto è quello di prendere un grande documento di testo (minimo circa 50.000 parole (non univoco)) e restituisce ciascuna parola univoca in ordine di più usato o meno usato (probabilmente i primi tre saranno "un" "un" e "il").

La mia domanda è, naturalmente, quale sarebbe il miglior algoritmo di ordinamento da utilizzare? Stavo leggendo il tipo di conteggio, e mi piace, ma la mia preoccupazione è che l'intervallo di valori sarà troppo grande rispetto al numero di parole uniche.

Qualche suggerimento?

Answer 1

In primo luogo, avrete bisogno di una mappa di word -> conteggio. 50.000 parole non sono molte - si adatteranno facilmente alla memoria, quindi non c'è nulla di cui preoccuparsi. In C++ puoi usare lo standard STL std :: map.

Quindi, una volta ottenuta la mappa, è possibile copiare tutti i tasti della mappa su un vettore.

Poi, specie questo vettore utilizzando un operatore di confronto personalizzato: invece di confrontare le parole, confrontare i conteggi dalla mappa. (Non preoccuparti dell'algoritmo di ordinamento specifico, l'array non è così grande, quindi qualsiasi ordinamento di libreria standard funzionerà per te.)

Answer 2

Vorrei iniziare con un quicksort e andare da lì.

Scopri i wiki page on sorting algorithms, però, per imparare le differenze.

Answer 3

Dai un'occhiata al link. Una rappresentazione pittorica su come funziona un algoritmo diverso. Questo ti darà un suggerimento!

Sorting Algorithms

Answer 4

Si dovrebbe cercare un MSD radix sorta. Ordinerà le voci in lexicographical order. . Qui è un google code project si potrebbe essere interessati a

Answer 5

Questo è un po 'complicato perché vuoi una mappa di parole -> frequenza, e vuoi ordinare il valore piuttosto che la chiave (che è comune). C'è un esempio Java here che mostra come farlo usando un comparatore personalizzato.

L'algoritmo particolare si utilizza non ha intenzione di avere molto effetto, così mi aveva appena bastone con l'implementazione della libreria standard.

Answer 6

È possibile ottenere prestazioni migliori rispetto Quicksort con questo particolare problema ipotizzando che se due parole si verificano lo stesso numero di volte, poi non importa in quale ordine di uscita di loro.

Primo passaggio: Creare una mappa hash con le parole come valori chiave e frequenza come valori associati. Compilerai questa mappa di hash mentre analizzi il file. Mentre stai facendo questo, assicurati di tenere traccia della frequenza più alta incontrata. Questo passaggio è O (n) complessità.

Secondo passaggio: Creare un elenco con il numero di voci uguale alla frequenza più alta del primo passaggio. L'indice di ogni slot in questo elenco contiene un elenco delle parole con il conteggio delle frequenze uguale all'indice. Quindi le parole che si presentano 3 volte nel documento andranno nella lista [3] per esempio. Scorrere la mappa di hash e inserire le parole negli appositi spazi nell'elenco. Questo passaggio è O (n) complessità.

Terzo passo: Scorrere l'elenco in ordine inverso ed emettere tutte le parole. Questo passaggio è O (n) complessità.

In generale, questo algoritmo eseguirà il task in O (n) tempo anziché O (nlogn) richiesto da quicksort.

Answer 7

penso che si vuole fare qualcosa, come spiegato nel post qui sotto:

http://karephul.blogspot.com/2008/12/groovy-closures.html

Lingue che sostengono la chiusura rendono la soluzione molto più facile, come LINQ come detto Eric.

Answer 8

In quasi tutti i casi che ho mai provato, Quicksort ha funzionato al meglio per me. Tuttavia, ho avuto due casi in cui Combsort era il migliore. Potrebbe essere stato che pettsort era meglio in quei casi perché il codice era così piccolo, o a causa di qualche stranezza nel modo in cui i dati erano ordinati.

In qualsiasi momento, l'ordinamento si presenta nel mio profilo, provo i tipi principali. Non ho mai avuto nulla che abbia superato sia Quicksort che Combsort.

Answer 9

per grandi insiemi è possibile utilizzare ciò che è noto come il "indicizzazione basata sorta" nel recupero delle informazioni, ma per 50.000 parole è possibile utilizzare il seguente:

• leggere l'intero file in un buffer.
• analizza il buffer e crea un vettore token con il token struct {char * term, int termlen; } term è un puntatore alla parola nel buffer.
• ordina la tabella per termine (ordine lessicografico).
• set entrynum = 0, un'iterazione il termine vettore, quando termine è nuovo, conservarlo in un vettore: struct {char * termine; frequenza int; } al numero indice, impostare la frequenza su 1 e incrementare il numero della voce, altrimenti incrementare la frequenza.
• ordina il vettore per frequenza in ordine decrescente.

Answer 10

Si può anche provare a implementare alberi digitali noti anche come Trie. Ecco lo link