[C/C++]Metodo alternativo per ordinamento alfabetico

[Marco1995]

Ciao ragazzi...io ho un file contenente una moltitudine di nomi....Questi nomi vanno ordinati in ordine alfabetico e sono strutturati nel seguente modo:

"nome1","nome2"...ecc...

Avevo pensato di inserirli in una lista dove ogni nodo contiene un nome...e successivamente riordinando la lista,la stampo su un file di testo cosicchè da ottenere un file di testo con i nomi ordinati.
Il problema è che il procedimento di creazione della lista (che ho già effettuato) è estremamente lungo dato che ci sono un casino di nomi.

Volevo sapere se esiste un modo per riordinare il file di testo in un modo "un pò più veloce".
Grazie delle risposte.

[MItaly]

Definisci "un casino di nomi", almeno come ordine di grandezza.
Poi non ho capito, su ogni riga c'è un set di nomi da ordinare? O tutti i nomi del file appartengono allo steso insieme da ordinare?

[Kaamos]

Originariamente inviato da Marco1995
Ciao ragazzi...io ho un file contenente una moltitudine di nomi....Questi nomi vanno ordinati in ordine alfabetico e sono strutturati nel seguente modo:

"nome1","nome2"...ecc...

Avevo pensato di inserirli in una lista dove ogni nodo contiene un nome...e successivamente riordinando la lista,la stampo su un file di testo cosicchè da ottenere un file di testo con i nomi ordinati.
Il problema è che il procedimento di creazione della lista (che ho già effettuato) è estremamente lungo dato che ci sono un casino di nomi.

Volevo sapere se esiste un modo per riordinare il file di testo in un modo "un pò più veloce".
Grazie delle risposte.

Per "lista" intendi una lista concatenata? In che modo inserisci i dati nella lista?

[Marco1995]

Ragazzi ho risolto...credevo che la lentezza fosse dovuta alla moltitudine di nomi,ma mi sbagliavo infatti avevo impostato male un ciclo while
Ad ogni modo:

Definisci "un casino di nomi", almeno come ordine di grandezza.

Mi sono fatto stampare proprio ora il numero di parole....per l'esattezza sono 5163

Poi non ho capito, su ogni riga c'è un set di nomi da ordinare? O tutti i nomi del file appartengono allo steso insieme da ordinare?

Tutti i nomi dei file appartengono allo stesso set da ordinare.

Per "lista" intendi una lista concatenata? In che modo inserisci i dati nella lista?

Sì...intendevo proprio una lista concatenata semplice...

Conclusione:
Grazie del vostro interessamento ma il problema,almeno per ora,è risolto...adesso non mi resta altro che riordinare la lista alfabeticamente..ma non credo sia un grosso problema.
Ciao.

P.s. Scusatemi veramente per la perdita di tempo

[MItaly]

5000 nomi sono pochissima roba poi in generale in questi casi non si usano le liste concatenate (che vanno bene se ti serve una struttura dati con inserimento random O(1)), ma dei banali vettori dinamici, in modo da rendere l'algoritmo di ordinamento più semplice ed efficiente ed evitare tutte le mini-allocazioni per i nodi della lista.

[Marco1995]

5000 nomi sono pochissima roba

Sarà che sono ancora un novellino..

ma dei banali vettori dinamici, in modo da rendere l'algoritmo di ordinamento più semplice ed efficiente ed evitare tutte le mini-allocazioni per i nodi della lista.

Avevo scelto di usare la lista perchè credevo che il "5000" fosse un numero di parole elevato,e dato che gli array hanno posizioni contigue avevo pensato (male) di scegliere proprio le liste .. .

Va bè in ogni caso sarà un valido esercizietto per riuscire a gestire meglio le liste.

[MItaly]

Originariamente inviato da Marco1995
Sarà che sono ancora un novellino..

Non è una questione di essere novellini, è questione di potenza di calcolo. 5000 nomi vuol dire una cosa nell'ordine dei 50 KB di memoria occupata, puoi farci quello che vuoi, ma è una quantità di dati risibile per i PC attuali.

Avevo scelto di usare la lista perchè credevo che il "5000" fosse un numero di parole elevato,e dato che gli array hanno posizioni contigue avevo pensato (male) di scegliere proprio le liste .. .

Perché l'avere posizioni contigue dovrebbe essere un male per gestire tanti elementi? Al contrario, in genere è un vantaggio (e tra l'altro rende la scrittura dell'algoritmo di ordinamento molto più semplice).

Va bè in ogni caso sarà un valido esercizietto per riuscire a gestire meglio le liste.

Sicuramente; d'altra parte "nella vita vera" in C++ con i container STL ci vogliono una decina di righe di codice in tutto.

[Marco1995]

Perché l'avere posizioni contigue dovrebbe essere un male per gestire tanti elementi?

Diamo per assurdo che ho un array che in memoria pesa 100megabyte...e io ho in ram 2Gb disponibili...solo che non riesco ad ottenere 100Mb contigui perchè sono tutti frammentati...in questo caso dovrei utilizzare una lista..l'esigenza delle liste non nasce anche per quel motivo?(Ovviamente non è il mio caso . .)

[MItaly]

Originariamente inviato da Marco1995
Diamo per assurdo che ho un array che in memoria pesa 100megabyte...e io ho in ram 2Gb disponibili...solo che non riesco ad ottenere 100Mb contigui perchè sono tutti frammentati...in questo caso dovrei utilizzare una lista..l'esigenza delle liste non nasce anche per quel motivo?(Ovviamente non è il mio caso . .)

Questo è vero, ma, se il tuo programma non fa altro, 100 MB di memoria contigui si trovano eccome ti direi che normalmente sotto il giga non si hanno mai problemi se non ci sono altre allocazioni grosse in ballo, visto che gli allocatori decenti evitano di sparpagliare le "piccole allocazioni" in giro per lo spazio di indirizzi. Poi ora con spazi di indirizzi a 64 bit il problema sostanzialmente non si pone più.

Da un punto di vista di memoria occupata "in assoluto", poi, una lista concatenata prende più spazio - per ogni elemento, oltre allo spazio per il payload, hai bisogno anche dello spazio per i due puntatori, più lo spazio usato dall'allocator per tenere traccia di tutte le allocazioni per i singoli nodi. Con un vettore invece ti limiti ad allocare un blocco di memoria e finita lì (e se non basta, riallochi raddoppiando le dimensioni, arrivando alle dimensioni definitive in tempo logaritmico nel numero degli elementi).

[Marco1995]

Questo è vero, ma, se il tuo programma non fa altro, 100 MB di memoria contigui si trovano eccome ti direi che normalmente sotto il giga non si hanno mai problemi se non ci sono altre allocazioni grosse in ballo, visto che gli allocatori decenti evitano di sparpagliare le "piccole allocazioni" in giro per lo spazio di indirizzi. Poi ora con spazi di indirizzi a 64 bit il problema sostanzialmente non si pone più.

Allora non riesco a capire l'utilità delle liste(concatenate semplici),in programmi che non fanno largo uso di risorse...

Mentre le liste "doppie" se non erro si usano vantaggiosamente per gli alberi binari . .