View Full Version : [C] Ordinamento e accesso random
Ho 1 problema e una domanda da porre,
come si può accedere a dati in modo random in un file per porli in una lista,ho un txt contenente
es
111
aaa
bbb
222
ccc
ddd
333
ttt
hhhh
555
yyy
iiii
ad esempio si vuole che il random prenda valori a caso ,come si fa a "mandarlo a capo" nella ricerca ,nel senso,come si fa a fargli capire di prendere i valori (sono in terzine,codice,nome e cognome)
domanda,miglior algoritmo ordinamento per lista linkata?
Grazie in ancitipo
lupoxxx87
13-04-2010, 15:38
ad esempio si vuole che il random prenda valori a caso ,come si fa a "mandarlo a capo" nella ricerca ,nel senso,come si fa a fargli capire di prendere i valori (sono in terzine,codice,nome e cognome)
EEEEH ?!:eek:
per l'ordinamento di algoritmi ce n'è a bizzeffe
si,ok,ma per creare un archivio qual' è il miglior tipo di lista ,linkata,doppiamente linkata ,circolare.....?e su questo tipo di lista qual' è il miglior ordinamento ?
Bisogna vedere bene cosa vuoi fare, cmq in genere un'ottima struttura dati è un albero binario di ricerca, consente la ricerca in O(log N).
In pratica ogni nodo X dell'albero ha un figlio sinistro e uno destro, nel figlio sinistro in genere si pone l'elemento minore di X, mentre nel figlio destro l'elemento maggiore o uguale a X (se vuoi memorizzare doppioni).
Uno dei problemi con questa struttura è che l'albero può essere sbilanciato tutto da un lato e degenerare nel caso pessimo in una lista collegata (ricerca in O(N) in tal caso), per ovviare a questo si adotta il bilanciamento automatico, che non è immediato da implementare (vedi alberi AVL).
grazie,avrei però bisogno di ordinare in loco e come lista per un piccolo archivio,va bene la linkata?
grazie,avrei però bisogno di ordinare in loco e come lista per un piccolo archivio,va bene la linkata?
Se spieghi meglio cosa vorresti fare forse riusciamo a darti un aiuto più mirato.
In ogni caso l'ordinamento in genere è finalizzato alla ricerca, e una struttura come un albero binario se mantenuta opportunamente bilanciata ti garantisce prestazioni superiori senza ricorrere ad un continuo ordinamento dei dati (l'ordinamento viene imposto direttamente all'inserimento dei dati).
Se il fine è la ricerca dei dati allora ti consiglio di usare un albero binario.
Tanto per la cronaca i principali DBMS fanno uso di strutture ad albero.
grazie! ok,ma io devo (per esercizio) creare in una lista (come voglio) ,ed effettuare ricerche e l' ordinamento (con quello che voglio),non posso usare db
Da qui le domande per entrambe le cose,andrei su linkata e quicksort,confermate?
Per l' altra domanda come posso fare a posizionarmi su una riga i-esima di un file txt (accedendo con read) ,dove questa riga sia multipla di 3? (seek?)
Grazie in anticipo!
grazie! ok,ma io devo (per esercizio) creare in una lista (come voglio) ,ed effettuare ricerche e l' ordinamento (con quello che voglio),non posso usare db
Da qui le domande per entrambe le cose,andrei su linkata e quicksort,confermate?
Per l' altra domanda come posso fare a posizionarmi su una riga i-esima di un file txt (accedendo con read) ,dove questa riga sia multipla di 3? (seek?)
Grazie in anticipo!
Ah ecco se era un'esercizio potevi dirlo prima :),cmq non ho mai detto che devi usare un DB, ho detto che le strutture ad albero proprio per la loro efficienza sono usate nei DB.
Detto ciò una lista doppiamente linkata (che quindi ha anche riferimento al predecessore) la vedo meglio.
Puoi andare di quicksort, però non ho mai implementato algoritmi di ordinamento su strutture diverse dagli array, ci potrebbero essere delle difficoltà dovute al fatto che non puoi accedere in maniera diretta agli elementi della lista ma devi usare un iteratore.
clockover
13-04-2010, 23:14
Con lsesk puoi posizionarti in un punto qualsiasi del file! Dai uno sguardo qui http://www.manpagez.com/man/2/lseek/
Comunque per un algoritmo di ordinamento devi sempre definire un (non ricordo bene il nome ma te lo chiamo così) comparatore!
Ad esempio per i numeri un comparatore ti dice che 1 è minore di 2 oppure che 1 è uguale a 1! Per elementi diversi dai numeri devi definirlo tu! Ad esempio per un ordinamento lessicografico "pippa" viene prima di "pippo" (che esempiaccio gagliardo eh)!
Comunque come Java anche il C ha già la funzione di quick sort e anche di merge sort, e addirittura anche di heap sort .... http://www.manpagez.com/man/3/qsort/
devi solo implementare il comparatore...
Se non erro quelle funzioni vanno bene solo per gli array, e non ad esempio per le liste collegate.
clockover
14-04-2010, 08:33
Se non erro quelle funzioni vanno bene solo per gli array, e non ad esempio per le liste collegate.
A non ne ho idea :D :D però se c'era una cavia che voleva ammazzarsi un po per provare :D :D
grazie ragazzi,allora ,al momento però penso partirò con una linkata semplice e quicksort,eventualmente poi approfondirò con la doppiamente linkata
per lseek come faccio a portarmi ad esempio alla quarta riga?
lseek(file, 4, SEEK_SET); ?
Grazie!
clockover
14-04-2010, 09:34
grazie ragazzi,allora ,al momento però penso partirò con una linkata semplice e quicksort,eventualmente poi approfondirò con la doppiamente linkata
per lseek come faccio a portarmi ad esempio alla quarta riga?
lseek(file, 4, SEEK_SET); ?
Grazie!
tutto dipende dal terzo parametro... comunque ricorda che l'offset parte da zero quindi se sei all'inizio la quarta è 3
grazie,ma allora cosa devo scrivere per andare alla terza riga?
E' probabile che ti convenga leggere prima tutta le righe, e poi sceglierle a caso
ad esempio vorrei generare un numero es 6 e andare al sesto record,come posso fare?
Carichi tutte le stringhe in una lista o un array, e poi vai a prendere il sesto elemento...
Possibile pseudocodice per il C
1. conto quante righe ci sono
2. Creo un array di tante righe
3. rileggo il file, memorizzando ciascuna riga nel posto giusto
4. inizio a tirare i valori a caso e restituisco ogni volta il record corrispondente.
In C#, che mi piace tanto ma tanto ma tanto di piu', sarebbe
string[] data = File.ReadAllLines(@"C:\temp\mioFile.dat");
Random rnd=new Random();
string primoDato = data[rnd.Next(data.Length)];
Non ho invece capito a cosa ti servirebbe l'ordinamento.
grazie,è l' idea che avevo avuto io,ma devo assolutamente andare sul file come ho scritto (è il testo del problema),come posso fare?Penso si possa accedere a un iesima riga
DanieleC88
14-04-2010, 20:53
Puoi andare di quicksort, però non ho mai implementato algoritmi di ordinamento su strutture diverse dagli array, ci potrebbero essere delle difficoltà dovute al fatto che non puoi accedere in maniera diretta agli elementi della lista ma devi usare un iteratore.
In realtà (in particolare per il quicksort) non comporta grosse difficoltà. Tempo fa aveva implementato proprio il quicksort su una lista doppiamente collegata, magari lo ripesco e lo posto qua.
DanieleC88
14-04-2010, 20:55
grazie,è l' idea che avevo avuto io,ma devo assolutamente andare sul file come ho scritto (è il testo del problema),come posso fare?Penso si possa accedere a un iesima riga
Un file è un insieme di dati (volutamente) non strutturato, dal momento che può contenere qualsiasi cosa: tanto dati binari quanto righe di testo, et cetera.
Leggi il file, trova l'offset dell'inizio delle varie righe, e poi fai una seek() come necessario.
grazie,come si trova l' offset?
DanieleC88
14-04-2010, 21:11
Secondo te? Leggendo il file. :p
Dove trovi un newline, quella è la posizione che precede l'inizio di una nuova riga.
In realtà (in particolare per il quicksort) non comporta grosse difficoltà. Tempo fa aveva implementato proprio il quicksort su una lista doppiamente collegata, magari lo ripesco e lo posto qua.
Non lo so non ho mai provato :Prrr:, ultimamente mi era presa la fissa cercando di implementare un mio algoritmo per il bilanciamento degli alberi :D.
grazie,è l' idea che avevo avuto io,ma devo assolutamente andare sul file come ho scritto (è il testo del problema),come posso fare?Penso si possa accedere a un iesima riga
Non si può accedere direttamente all'i-esima riga. Non si può nemmeno in altri linguaggi. L'unico modo per farlo è leggerti prima tutto il file, memorizzarti la posizione di inizio delle righe e poi estrarre un numero casuale che ti va a recuperare la posizione della riga estratta. A quel punto puoi usare fseek.
banryu79
15-04-2010, 09:13
Non si può accedere direttamente all'i-esima riga. Non si può nemmeno in altri linguaggi. L'unico modo per farlo è leggerti prima tutto il file, memorizzarti la posizione di inizio delle righe e poi estrarre un numero casuale che ti va a recuperare la posizione della riga estratta. A quel punto puoi usare fseek.
Conoscendo il carattere di 'newline' e di 'end of file' un'alternativa potrebbe essere quella di leggere, per ogni richiesta di accesso ad una riga casuale N, in modo sequenziale N-1 'newline': in quel momento il puntatore è posizionato all'inizio della riga corretta, da prelevare fino al prossimo 'newline' o 'end of file'.
Naturalmente se N è maggiore delle righe presenti nel file si incontrerà il carattere di 'end of file' prima del tempo e l'accesso non sarà valido.
Ovviamente è una soluzione peggiore di quella che hai proposto tu :D
ok grazie,è proprio l' idea che ho io,ma non so come implementare la gestione delle linee,come posso "memorizzare" le posizioni quando va in una nuova riga?
ok grazie,è proprio l' idea che ho io,ma non so come implementare la gestione delle linee,come posso "memorizzare" le posizioni quando va in una nuova riga?
http://www.cplusplus.com/reference/clibrary/cstdio/ftell/
Questo è lo stesso valore che devi passare nuovamente a fseek (con SEEK_SET) per riposizionarti sull'inizio della nuova riga.
ti ringrazio,però quello che mi blocca è il fatto su come creare il meccanismo ,io scorro tutta una lista fino a una riga,es 12 e passo 12 alla fseek?
DanieleC88
15-04-2010, 15:30
ti ringrazio,però quello che mi blocca è il fatto su come creare il meccanismo ,io scorro tutta una lista fino a una riga,es 12 e passo 12 alla fseek?
http://linux.die.net/man/3/fseek
ti ringrazio,però quello che mi blocca è il fatto su come creare il meccanismo ,io scorro tutta una lista fino a una riga,es 12 e passo 12 alla fseek?
Tu scorri tutto il file carattere per carattere fino a quando trovi \n, a quel punto ottieni con ftell la posizione della nuova linea e te la metti in una lista.
Estrai un numero random e scorri la lista di tanti elementi quanto è il numero random estratto (ovviamente opera in modulo della dimensione della lista), a quel punto prendi il valore e lo passi ad ftell e leggi la riga fino alla fine.
clockover
15-04-2010, 15:41
ti ringrazio,però quello che mi blocca è il fatto su come creare il meccanismo ,io scorro tutta una lista fino a una riga,es 12 e passo 12 alla fseek?
Ma scusami ancora non capisco... tu la lista la intendi come "struttura dati", oppure come dei caratteri in un file, dove ogni record termina con /n??
allora,mi scuso se la discussione sta diventando un pò confusa,
allora ho un txt che ha 3 "voci" per ogni record,
devo costruire una lista e tutto ok,però l' ho creata con tutti gli elementi,dovrei crearla con solo alcuni record presi a random
while(!(feof)){
if("//Come metto per indicare// =='/n')
a[i]=ftell; // mi basta un array per archiviare le posizioni
//fseek(file,a[i],SEEK_CUR);
Una cosa del genere?
Grazie ancora
Se conosci il C sei tu a sapere cosa devi mettere qui:
if("//Come metto per indicare// =='/n')
Inoltre fseek non serve lì, ma una volta che hai estratto il numero casuale ed hai recuperato l'indice della riga sulla quale spostarti.
si,ma non so cosa mettere come parametro di eguaglianza,fscanf?
si,ma non so cosa mettere come parametro di eguaglianza,fscanf?
Non sai come si legge un solo carattere da un file ? Hai mille modi. Lo puoi fare non direttamente (fscanf) e direttamente (ad esempio fgetc).
clockover
16-04-2010, 00:48
O anche con una read...
Perchè non con una read...
Perché la read non è una funzione standard ANSI. Semmai uan fread, ma è più adatta per dati binari.
clockover
16-04-2010, 00:51
Perché la read non è una funzione standard ANSI. Semmai uan fread, ma è più adatta per dati binari.
A ok... sono abituato con Linux, penso sempre che ci sia solo lui :D :D
A ok... sono abituato con Linux, penso sempre che ci sia solo lui :D :D
La read c'è anche su Windows, ma è meglio restare sulle funzioni standard in una esercitazione. Comunque sulla read si possono fare le stesse considerazione che si possono fare sulla fread ;)
clockover
16-04-2010, 00:53
Perché la read non è una funzione standard ANSI. Semmai uan fread, ma è più adatta per dati binari.
Potrebbe essere che il mio problema in questo post http://www.hwupgrade.it/forum/showthread.php?t=2168424 sia dovuto alla read??
così?
int contatore=0;
char c;
while (c=fgetc(stream_dati)!=EOF){
if (c=='\n')
contatore++;
}
DanieleC88
16-04-2010, 11:17
così?
int contatore=0;
char c;
while (c=fgetc(stream_dati)!=EOF){
if (c=='\n')
contatore++;
}
Sempre le parentesi. A prescindere dalla correttezza di questo codice.
così?
int contatore=0;
char c;
while (c=fgetc(stream_dati)!=EOF){
if (c=='\n')
contatore++;
}
Così conti le linee.
int a[N];
char c;Lista i=0;
while (c=fgetc(stream_dati)!=EOF){
if (c=='\n') nodolista=c;
lista=lista->next;
}
in pseudocodice è corretto?
No, mi sembra che tu abbia un bel po' di confusione... Prima metti un vettore, poi metti una lista. Inoltre nella lista ci metti sempre \n, quando invece ci devi mettere il valore ritornato da ftell. Prima la lista la chiami i e poi la chiami lista...
si,nella velocità ho sbagliato a scrivere
char c;Lista i=NULL;
while (c=fgetc(stream_dati)!=EOF){
if (c=='\n') nodolista=ftell(file);
lista=lista->next;
}
nessuno?
Ma quale sarebbe l'output di questo pseudocodice?
Fa quello che hai chiesto?
Metti le parentesi qui
(c=fgetc(stream_dati))
Sì, per creare la lista va bene.
int c=0;int t=0;
int righe[N];
while ((c=fgetc(fp))!=EOF){
if (c=='\n') righe[t]=ftell(fp);t++;
Ho provato a costruire questo codice,ma mi da dei puntatori stranamente,cosa dimentico?
Grazie in anticipo
wingman87
18-04-2010, 00:57
int c=0;int t=0;
int righe[N];
while ((c=fgetc(fp))!=EOF){
if (c=='\n') righe[t]=ftell(fp);t++;
Ho provato a costruire questo codice,ma mi da dei puntatori stranamente,cosa dimentico?
Grazie in anticipo
Cosa vuol dire che ti "da dei puntatori stranamente"? Comunque attento che t++; non fa parte del corpo dell'if e quindi viene eseguito ad ogni ciclo.
while ((c=fgetc(fp))!=EOF){
if (c=='\n') righe[t]=ftell(fp);t++;
}
è corretto come codice? t non deve avanzare nella posizione dell' array?
Grazie
Così è corretto:
if (c=='\n')
{
righe[t]=ftell(fp);
t++;
}
main(){
FILE *fp;char c;int righe[N];int t=0;
fp = fopen ("file.txt", "r");
while ((c=fgetc(fp))!=EOF){
if (c=='\n')
{
righe[t]=ftell(fp);
printf("\n %d",righe[t]);
t++;
}
}
fclose (fp);
}
Se si adesso passo alla fseek giusto ? (dopo una generazione random ovviamente,poniamo il caso restituisca il valore memorizzato in pos 25 dell' array,passo 25?)
fseek(fp,?????,SEEK_SET);
Sarebbe così? Grazie ancora
No, tu devi randomizzare gli indice dell'array e dare il valore memorizzato a quell'indice ad fseek.
mettiamo che nell' array ci siano x valori ,
genero un rand%x e vado alla posizione dell' array corrispondente a questa operazione e guardo cosa c' è memorizzato a quell' iesima posizione e accedo con fseek alla riga corrispondente
quindi fseek(fp,righe[i],SEEK_SET);
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.