Pagina 1 di 3 1 2 3 ultimoultimo
Visualizzazione dei risultati da 1 a 10 su 23
  1. #1

    Index file

    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

  2. #2
    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.

  3. #3
    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.

  4. #4
    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?
    http://premiatinavigando.weebly.com/

  5. #5
    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.

  6. #6
    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
    http://premiatinavigando.weebly.com/

  7. #7
    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

  8. #8
    Utente bannato
    Registrato dal
    Apr 2012
    Messaggi
    518
    Nell' esempio che ha fatto sono ordinati secondo l' indice, infatti la sequenza {0,1,2,5} è crescente.

  9. #9
    Non capisco come si possa ordinare mediante l'indice, non lo capisco proprio
    Sì, mi servirebbe un altro esempio se non ti dispiace
    http://premiatinavigando.weebly.com/

  10. #10
    up
    http://premiatinavigando.weebly.com/

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2019 vBulletin Solutions, Inc. All rights reserved.