devo implementare, anzi, ho implementato un banale algoritmo per il confronto di dati duplicati ma è troppo lento. Si tratta di confrontare più di 800000 stringhe e il metodo che uso io, prendi la prima stringa e confrontala con le altre n+1, poi la seconda con n+2 etc... impiega almeno 8 ore di elaborazione: che algoritmi esistono più performanti?
grazie
Metti i dati in ordine, con un algoritmo veloce.
No MP tecnici (non rispondo nemmeno!), usa il forum.
grazie
mi era venuto in mente di riordinare con quick sort ma poi?
Mi devo posizionare velocemente sulle prime due uguali: un while? credo, quindi confrontare le successive e quando diverse fare qualcosa d'altro, magari tornare al while?
Ordini con il quicksort (O(n log n)), quindi per individuare gli elementi duplicati ti basta scorrere l'array una sola volta, visto che nell'array ordinato tutti i duplicati dello stesso elemento sono consecutivi.
Amaro C++, il gusto pieno dell'undefined behavior.
quindi in luogo di due cicli nidificati ne hai uno solo che confronta l'elemento n e n+1 giusto?Originariamente inviata da MItaly
Esattamente.
Amaro C++, il gusto pieno dell'undefined behavior.
grazie ad entrambi
implementato, 8 ore di elaborazione contro qualche manciata di secondi
È un classico esempio di come scalano i tempi in maniera diversa a seconda degli algoritmi utilizzati: nel tuo primo caso avevi un algoritmo O(n^2), mentre il nuovo algoritmo è O(n log n) + O(n) = O(n log n), la differenza è molto evidente...
Amaro C++, il gusto pieno dell'undefined behavior.
grazie per avermi rinfrescato la memoria
Dove O(n log n) è relativo al quick sort e O(n) al ciclo, ricordo giusto?
Permessi di invio
Rispondi quotando