Index file

[robe921]

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

[hamming_burst]

Ciao,
al primo colpo direi che si tratta tipo di un pettine che mantiene in memoria, in modo ordinato, invece che i dati veri e propri solo il puntatore ad esso. Ma questo presuppone che un ordinamento deve esserci stato.

es. sia A[] un vettore di 4 interi (non ordinato), ed B[] il vettore index che mantiene in memoria l'indirizzo (mettiamo per semplificare sia l'indice.
A[]={3,44,11,20}

B[] attravero un algoritmo di ordinamento ordina gli elementi ma senza toccare A[] direttamente.

B[]: 0->A[0] , 1->A[2] , 2->A[3] , 3->A[1]

questo poi si può applicare ad un algoritmo di ricerca che guarda B senza toccare A non-ordinato.

Però te parli di

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

se non è ciò che ho scritto, potresti riportare questo algoritmo, testo, immagine, ....

[robe921]

Dovrebbe essere questo perché so che l'index file rende più semplice l'ordinamento di grandi masse di dati, che quindi possono essere ordinate solo tramite l'indice evitando lo spostamento di tutti i dati nella memoria. Lo step successivo all'ordinamento sarebbe la ricerca dicotomica di un record (che, appunto, presuppone che il vettore o la lista siano ordinati).

Ciò che vorrei capire è: ma come si fa ad ordinare il file index in modo tale da avere una corrispondenza con gli elementi dell'altro vettore ordinati? Mi spiego meglio, abbiamo:

A[0]=3 con B[0]=0
A[1]=44 con B[1]=1
A[2]=11 con B[2]=2
A[3]=20 con B[3]=3

Da qui come posso ottenere

B[0]=0
B[1]=2
B[2]=3
B[3]=1

Per ordinare il vettore di partenza? Che algoritmo dovrei usare per ordinare il file index in questo modo?

[hamming_burst]

prendiamo insertion_sort e modifichiamolo per ordinare un array di puntatori B[]. Lo scriviamo in simil-C così è più comprensibile, essendoci anche i puntatori.
Prima di tutto, devi creati le strutture dati ed inizializzarle B con gli indirizzi di A che solo in seguito ordinerai.

int i=0
while(i<n){
      B[i]=&A[i];
i++;
}

ora modichiamo insertion_sort passandogli il puntatore a B dove modificherà solo gli indirizza, ma valuterà A essendo puntato dagli elementi di B:

void insertion_sort(int** B){

       int i,j;
       int* value;

       i=1;
       while(i<n){
          value = B[i];

          j=i;
	//valuto gli elementi di A[] passandogli il valore puntato da B[] 
	//in pratica *B[i] = A[i] perchè B[i]=&A[i]
          while(j>0 && *B[i] > *value){
             B[j] = B[j-1];
          j--;
          }

          B[j] = value;
       i++;
       }   
    }
}

vediti se ti è chiaro, è semplicemente insertion_sort adattato, nulla di complicato. Se no ne discutiamo

[robe921]

Potresti adattare questo discorso dell'index file all'ordinamento di un vettore? Vorrei capire nella pratica cosa significa ordinare un vettore tramite indici. Mi faresti un favore enorme
Scusami se insisto ma il mio professore di Informatica è molto interessato a questo argomento e vorrei conoscerlo fino in fondo, e non solo nella teoria

[hamming_burst]

Ciao,

"robe92":Potresti adattare questo discorso dell'index file all'ordinamento di un vettore?

e cosa pensi che faccia quel codice che ho descritto sopra??

l'index file forse non lo hai capito ma è quello che è passato ad insertion_sort(), cioè int** B sta per int* B[], cioè un array di puntatori.

Scusami se insisto ma il mio professore di Informatica è molto interessato a questo argomento e vorrei conoscerlo fino in fondo, e non solo nella teoria

no problema, prova a rivederti l'insertion_sort banale con quello che ho descritto e nota le differenze.

ho preso insertion_sort() solo perchè è semplice ed lungo poche linee...

[robe921]

sì scusami mi sono spiegato male, volevo in verità che me lo spiegassi con un altro algoritmo di ordinamento, tipo il bubble sort (non conosco l'insertion sort)

void bubble_sort(int v[], int dim) {
int i, flag;
do
  {
     flag=0;
     for(i=0;i<dim-1;i++) 
     {
           if(v[i]>v[i+1]) swap(&v[i], &v[i+1]);
           flag=1;
     }
  }
while(flag==1);
}

Preferirei concentrarmi solo sull'implementazione dell'index che sulla comprensione del programma in sé
Ti ringrazio

[hamming_burst]

"robe92":sì scusami mi sono spiegato male, volevo in verità che me lo spiegassi con un altro algoritmo di ordinamento, tipo il bubble sort (non conosco l'insertion sort)

il bubble_sort è uno dei peggiori algoritmi di ordinamento. L'insertion_sort per certi valori è ottimo, in altri no ma fa cmq sempre il suo dovere. Se è solo questione di comprensione tant'è... vediamo di modificare bubble...

Prima cosa devi inizializzare il vettore index chiamiamolo sempre B. E' un array di puntatori (ci siamo?).
perciò un ciclo while e copi gli indirizzi così sequenzialmente il codice è identico a sopra:

int** B = malloc(sizeof(int*)*dim);
if(!B){
  return -1;
}
int i=0
while(i<dim){
      B[i]=&v[i];
i++;
}

modifichiamo il codice passando SOLO e ripeto SOLO il vettore B, perchè non serve v essendo che è puntato da B.

void bubble_sort(int* B[], int dim) {
int i, flag;
do
  {
     flag=0;
     for(i=0;i<dim-1;i++) 
     {
           if(*B[i]>*B[i+1]){//confrontiamo i valori puntati
               swap(&B[i], &B[i+1]); //swap di contenuti perciò uguale al normale algoritmo. (*)
            }
           flag=1;
     }
  }
while(flag==1);
}

(*) potresti mostrarmi la funzione

swap(int* a,int*b)

vorrei vedere come la hai implementata per sicurezza.

Hai compreso come funziona un array di puntatori?

[robe921]

Ciao, innanzitutto ti ringrazio per la pazienza, ad ogni modo adesso penso di aver appreso come funziona nella pratica. Purtroppo ho ancora qualche dubbio riguardo la tua implementazione del codice. Mi spiegheresti cosa fa l'istruzione

int **B = malloc(sizeof(int*)*dim)

e poi, perché hai inserito

if(!B)

A cosa serve porre questa condizione in quel punto?

nel bubble poi hai detto che passi int *B[], ovvero l'array di puntatori, quindi quando fai lo swap &B e &B[i+1] sono gli indirizzi delle due allocazioni del vettore di puntatori che puntano a due rispettive celle di V no?

Ecco la procedura per lo swap:

void swap(int *x, int *y) {
int temp;
temp=*x;
*x=*y;
y*=temp;
}

[hamming_burst]

"robe92": Mi spiegheresti cosa fa l'istruzione

int **B = malloc(sizeof(int*)*dim)

allocazione dinamica mai sentita? allocca dim celle di memoria di puntatori ad interi (index file).
Forse sei ad all'inizio di un corso di programmazione, e certi argomeni devi ancora affrontarli.
la controparte statica dovrebbe esser:

int* B[dim]

e poi, perché hai inserito

if(!B)

A cosa serve porre questa condizione in quel punto?

questo è un controllo sul valore di ritorno se

B==NULL

cioè punta al puntatore ad indirizzo $000000...$ vuol dire che ci son stati problemi di memoria, se non ci fosse il controllo ci potrebbero essere errori di seg-fault.
Se devi ancora vedere l'allocazione dinamica allora lascia stare...

nel bubble poi hai detto che passi int *B[], ovvero l'array di puntatori, quindi quando fai lo swap &B e &B[i+1] sono gli indirizzi delle due allocazioni del vettore di puntatori che puntano a due rispettive celle di V no?

esatto ed è ciò che fa l'index file. Ma sottolineo che si swappa solo l'indirizzo contenuto in B[] ad essere cambiato e non V[] che rimane uguale.

Ecco la procedura per lo swap:

void swap(int *x, int *y) {
int temp;
temp=*x;
*x=*y;
y*=temp;
}

infatti questa non è adatta per lo swap su puntatori, ma solo su interi che passi per riferimento.
lo swap su puntatori è circa questo dove fa lo stessa cosa di un normale swap, solo che lavori con indirizzi:

void swap_P(int *x, int *y) {
int* temp;
temp=x;
x=y;
y=temp;
}

[robe921]

cosa sarebbe il seg-fault? è possibile creare un index file senza l'uso dell'allocazione dinamica della memoria?

se creo una variabile di tipo "int" non dovrebbe allocare lo stesso la memoria per un numero intero? (2 byte) Perché conviene allocare la memoria in modo dinamico?

[hamming_burst]

"robe92":cosa sarebbe il seg-fault?

in parole semplici, un esempio è quando accedi ad un indirizzo fuori dalla memoria che hai a disposizione.
Es. int a[dim] e te accedi alla zona di memoria a[dim+1]

è possibile creare un index file senza l'uso dell'allocazione dinamica della memoria?

certo! e se mi chiedi questo non sai la differenza dei tipi di allocazione, ma se come penso tu fai un corso di programmazione base, lo vedrai

cmq se leggi il post precedente lo ho ben scritto, allocchi staticamente con:

int* B[dim]

se creo una variabile di tipo "int" non dovrebbe allocare lo stesso la memoria per un numero intero? (2 byte) Perché conviene allocare la memoria in modo dinamico?

no bhe c'è differenza.

int a

vuol dire allocare staticamente un valore di tipo intero.

int* b

vuol dire allocare un puntatore di tipo intero, che poi dovrai far puntare ad un intero (tipo primitivo) o staticamente o dinamicamente:

int* b = &a

oppure

int* b = malloc(sizeof(int));

poi non è vero che son 2Byte dipende dall'architettura!!