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

[Andrea Simonassi]

Esempio banale:

#include <stdio.h>
#include <stdlib.h>
int compare_int(const void * a, const void * b){   
   return (*(int*)a) - (*(int*)b);
}

int main (int argc, char **argv)
{   /*Dichiarazioni*/   
   struct _record
   {
      int id;
      char nome[30];
   } record [] =
   {
       {1, "pippo"}
      ,{5, "topolino"}
      ,{2, "pluto"}
      ,{0, "minnie"}      
   };                                              /*array di record di esempio da trovare*/
   
   size_t elem_size = sizeof(struct _record);      /* dimensione di un record */   
   size_t elem_count = sizeof(record) / elem_size; /* quanti record nell'array */   
   int * indice;                                   /* indice */   
   int i;                                          /* contatore */   
   int find;                                       /* elemento da trovare */
   int *trovato;                                   /* elemento trovato */

   /* Implementazione */      
   
   indice = (int*)malloc(sizeof(int)*elem_count);  /*1) Allocazione memoria */   
   if(indice==NULL) return 1;

   for(i=0;i<elem_count;++i)                       /*2) riempimento indice */
      indice[i] = record[i].id;   
   
   qsort(indice, elem_count, sizeof(int), compare_int); /*3) Ordinamento indice*/   
   
   find = 2;                                       /*4) cerco il record con id = 2 */    
   trovato = (int*)bsearch(&find, indice, elem_count, sizeof(int), compare_int);
      
   if(trovato != NULL)                             /*5) stampa risultato */
      printf("Record trovato:nID: %d nNome: %sn", record[*trovato].id, record[*trovato].nome);
   else
      printf("Non trovaton");
   
   free(indice);                                   /*6) liberazione memoria allocata */
}

[robe92]

Ti ringrazio per questo esempio che, ahimè, è ancora fuori dalla portata della mia comprensione. Ad ogni modo sarebbe bastato anche un altro esempio come quello precedente che mi illustri il funzionamento di questo benedetto index file. Fin ora ho capito che è un vettore di puntatori (indici) ai record di un vettore detto "file storico" e permette l'ordinamento virtuale di questo. Ciò che non mi è chiaro ancora è come fa ad ordinare il vettore puntato

[Andrea Simonassi]

il vettore puntato non è ordinato, è ordinato l'indice.

Peraltro il mio esempio è pure sbagliato...

[Who am I]

Serve una coppia (indice, chiave), così se si cerca una chiave si fa una ricerca binaria su tutte le coppie, quando si trova la coppia giusta si guarda nel file (simbolicamente rappresentato dall' array record) l' indice che corrisponde alla chiave cercata.
Il problema era che prima di ordinare l' array dovevi tenere traccia di quelli che erano gli indici originali delle chiavi.
Ho rivisionato il tuo codice e la struttura l' ho chiamata index (mi accorgo ora che il nome non è molto significativo perché in realtà è una coppia), facendo la bsearch su tutte le coppie e andando a guardare il risultato nell' array record avente come indice il campo "indice" della coppia trovata.

#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    int valore_chiave;
    int indice;
}index;


int compare_index (const void* a, const void* b)
{
    return ((index*)a)->valore_chiave - ((index*)b)->valore_chiave;
}


int main (int argc, char **argv)
{   /*Dichiarazioni*/   
    struct _record
    {
        int id;
        char nome[30];
    } record [] =
    {
        {1, "pippo"}
        ,{5, "topolino"}
        ,{2, "pluto"}
        ,{0, "minnie"}      
    };                                              /*array di record di esempio da trovare*/
    
    size_t elem_size = sizeof(struct _record);      /* dimensione di un record */   
    size_t elem_count = sizeof(record) / elem_size; /* quanti record nell'array */ 
    index* indice;
    int i;                                          /* contatore */   
    index find;                                       /* elemento da trovare */
    index *trovato;                                   /* elemento trovato */
    
    /* Implementazione */      
    
    indice = (index*)malloc(sizeof(index)*elem_count);  /*1) Allocazione memoria */  
    if(indice==NULL) return 1;
    
    for(i=0;i<elem_count;++i)                       /*2) riempimento indice */
    {
        indice[i].valore_chiave = record[i].id;  
        indice[i].indice=i;
    }
    
    qsort(indice, elem_count, sizeof(index), compare_index); /*3) Ordinamento indice*/   
    
    find.valore_chiave=5;                                          
    trovato = bsearch(&find, indice, elem_count, sizeof(index), compare_index);
    
    if(trovato != NULL)                             /*5) stampa risultato */
        printf("Record trovato:nID: %d nNome: %s", record[trovato->indice].id,record[trovato->indice].nome);
    else
        printf("Non trovato");
    
    free(indice);                                   /*6) liberazione memoria allocata */
}

[Andrea Simonassi]

Grazie , sapevo che l'errore era li e sapevo come correggere, il fatto è che ho copiato del mio vecchio codice e l'ho adattato alla bellemmeglio per semplificarlo al massimo, il mio indice era una coppia di puntatori void, uno che puntava alla chiave e l'altro al record e utilizzava un puntatore a funzione per selezionare l'elemento chiave dato un puntatore ad un record, ma metterlo giu cosi mi pareva complesso da spiegare.

#include <stdlib.h>
#include "indice.h"
/* IMPLEMENTAZIONE INDICE */

struct _indice
{
   void* chiave;
   void* puntatore;
};


struct _indice * creaindice(void * v, size_t element_size, size_t l, void*(*key_selector)(void*), int(*comparer)(const void*, const void*))
{
   size_t i;
   struct _indice * pindex = (struct _indice *)malloc(sizeof(struct _indice)*l);

   if(pindex==NULL)return NULL;

   for(i = 0; i<l;++i)
   {
      pindex[i].chiave = (void*)key_selector(v);
      pindex[i].puntatore = v;
      v = (void*)((char*)v + element_size);
   }
   qsort (pindex, l, sizeof(struct _indice), comparer);

   return pindex;
}

void * sfogliaindice(struct _indice * indice, size_t len, void * key, int(*comparer)(const void*, const void*))
{
   struct _indice elem;   /*elemento da cercare nell'indice*/
   struct _indice * pItem;

   elem.chiave = key;
   elem.puntatore = NULL;
   
   pItem = (struct _indice *) bsearch (&elem, indice, len, sizeof (struct _indice), comparer);

   if(pItem == NULL) return NULL;
   return pItem->puntatore;
}

[robe92]

non mi sto riferendo al tuo esempio, ti sto chiedendo cortesemente di farne uno più semplice e intuitivo, per favore

[robe92]

Scusami se non mi sono spiegato, ma sfortunatamente il tuo esempio va oltre le mie conoscenze (non ho ancora studiato struct e funzioni malloc). Piuttosto mi andrebbe bene un esempio anche "terra-terra", intuitivo che mi faccia capire il funzionamento di questo index file perché fino ad ora ho capito solo quello che ho scritto nel messaggio precedente.

[Andrea Simonassi]

Proverò.

Se hai un file con questi dati

posizione | valore (quel che è valore per il vettore è chiave per l'indice)
0               3
1               4
2               7
3               1

possiamo dire, in linguaggio C che

v[0] = 3
v[1] = 4
v[2] = 7
v[3] = 1

un indice non è altro che la funzione inversa

chiave | posizione nel vettore
1        |  3
3        |  0
4        |  1
7        |  2

quindi in c

i(3) restituisce 0
i(7) restituisce 2

la funzione i(x) sarà ovviamente piu veloce se le chiavi sono ordinate, perchè possiamo fare ricerca in tempo o(log n)

quindi siccome v[i(x)] = x, accoppiando le funzioni otteniamo la funzione identità

v[i(1)] = 1
v[i(3)] = 3
v[i(4)] = 4
eccetera.

ovviamente trattandosi di vettori di int non ha senso una funzione che mi dica che f(1)=1 o f(3)=3, la cosa acquista senso solo se parliamo di struct o di grossi files, dove c'è un effettivo vantaggio ad ordinare "solo" una chiave invece che ordinare una struttura di record enormi.

[Who am I]

Originariamente inviato da robe92

Quando parliamo di chiave sai esattamente cosa significa?

[robe92]

dovrebbe essere il contenuto del record