[ALGORITMO] Uso di file "index" per ricerca in un vettore

[robe92]

Salve a tutti, vorrei cortesemente porvi questa mia domanda riguardo un metodo di ricerca in un vettore di n elementi: in cosa consiste l'utilizzo del file index?

A quanto ho capito leggendo dal mio libro di programmazione (un po' datato a dir la verità) il file index è un vettore di indici (puntatori) che contengono l'indirizzo del record aggiunto al vettore in cui bisogna effettuare la ricerca e permette di superare l'inconveniente dell'algoritmo di ricerca binario che presuppone l'ordinamento del vettore prima della ricerca vera e propria. Qualcuno di voi potrebbe gentilmente spiegarmi, anche in breve, qual è il funzionamento di questo file index?

Vi ringrazio

[Andrea Simonassi]

Esempio in brevissimo:

Ho questo file (facciamo finta che invece che 4 siano 4 milioni di records).

file:
1 pippo
5 topolino
2 pluto
0 minnie

Ho questo indice .

indice:
0 3
1 0
2 2
5 1

Problema: Devo caricare il record con chiave 5 ([5, topolino]) dal file ma il file non è ordinato:

Apro l'indice ( in questo esempio l'indice deve essere ordinato, in realtà si usano strutture come BTREE perchè mantenere in ordine un indice costa troppo a meno che le modifiche al file siano molto rare).

Faccio una ricerca binaria sull'indice per trovare la posizione numero 5 con complessita o(log n)

Apro il file e leggo il record numero 1 in tempo costante.

[Andrea Simonassi]

Esempio in brevissimo:

Ho questo file (facciamo finta che invece che 4 siano 4 milioni di records).

file:
1 pippo
5 topolino
2 pluto
0 minnie

Ho questo indice .

indice:
0 3
1 0
2 2
5 1

Problema: Devo caricare il record con chiave 5 ([5, topolino]) dal file ma il file non è ordinato:

Apro l'indice ( in questo esempio l'indice deve essere ordinato, in realtà si usano strutture come BTREE perchè mantenere in ordine un indice costa troppo a meno che le modifiche al file siano molto rare).

Faccio una ricerca binaria sull'indice per trovare la posizione numero 5 con complessita o(log n)

Apro il file e leggo il record numero 1 in tempo costante.

[robe92]

come si ordina il file index? si ordina a seconda degli indici oppure a seconda di quello che puntano?

e cosa cambia dall'ordinamento diretto sul vettore con conseguente ricerca binaria? Conviene l'uso del file index o no?

[Andrea Simonassi]

conviene l'uso del file index: lo devi decidere tu sulla base della comprensione di cosa fa un indice, se hai un vettore di int non ha senso, di solito, creare un indice di accesso, tanto vale ordinare il vettore, ma se hai un file dati con milioni di records ha senso avere un indice.

Solo per semplicità inizialmente si studiano indici su vettori di interi, dove non ha senso avere indici.

[robe92]

Originariamente inviato da robe92
come si ordina il file index? si ordina a seconda degli indici oppure a seconda di quello che puntano?

Non hai risposto a questa domanda, grazie comunque

[Andrea Simonassi]

Non c'entra nulla l'ordinamento con gli indici, l'ordinamento è solo una delle possibilità.

Se usi l'ordinamento devi ordinare l'indice in base ai valori contenuti nel vettore.

Serve esempio?

Ciao

[Who am I]

Nell' esempio che ha fatto sono ordinati secondo l' indice, infatti la sequenza {0,1,2,5} è crescente.

[robe92]

Non capisco come si possa ordinare mediante l'indice, non lo capisco proprio
Sì, mi servirebbe un altro esempio se non ti dispiace

[robe92]

up