PROBLEMA Algoritmo ricerca occorenze con lista concatenata - C

[FiloRp]

Ti aiuta perchè cosi ti basta scandire una sola volta la lista per trovare l'elemento più frequente.
Io la farei cosi: crei due strutture con dentro un contatore impostato inizialmente a 0 per entrambi e con una variabile per la chiave corrispondente.
Nel tuo ciclo, userai solo una delle due strutture. All'inizio modificherai la prima struttura mettendo la chiave e il contatore = 1, passi avanti e finchè è uguale incrementi il contatore. Appena la chiave è diversa, fai il confronto con l'altra struttura: se il contatore è maggiore lo sostituisci, sennò rimane invariata. E ricominci il procedimento con il nodo successivo ( la vecchia struttura verrà di nuovo impostata a 1 ed incrementata, per poi essere confrontata con quella che contiene la chiave con più frequenza).
Alla fine del ciclo avrai la struttura con la chiave con più elementi nella lista.

Ma non mi basterebbe scandire una sola volta la lista in ogni caso?
Se riordinassi con merge o quick spenderei del tempo con la loro esecuzione e solo O(n) quando devo fare i conti, ma se non riordino non so se il tempo sia di un ordine di grandezza molto superiore.

Anyway, vediamo se ho capito:
-procedo con merge dei numeri casuali
-ottengo una lista ordinata che duplico (?)
-imposto i contatori a 0
-modifico la prima struttura ponendo la chiave e il counter a 1, incrementandola
-la confronto con la chiave con più elementi nella lista (ma da dove la prendo?)
-se la chiave confrontata è diversa, confronto l'altra struttura
-se il counter è maggiore la sostituisco
-proseguo con il nodo successivo, la vecchia struttura viene reimpostata a 1 e incrementata per essere riconfrontata con quella che contiene la chiave con più elementi

Fatico a capire cosa dovrei fare con gli step, figuriamoci in codice... :suicidio:

 

[rodhellas]

Ma non mi basterebbe scandire una sola volta la lista in ogni caso?
Se riordinassi con merge o quick spenderei del tempo con la loro esecuzione e solo O(n) quando devo fare i conti, ma se non riordino non so se il tempo sia di un ordine di grandezza molto superiore.

Anyway, vediamo se ho capito:
-procedo con merge dei numeri casuali
-ottengo una lista ordinata che duplico (?)
-imposto i contatori a 0
-modifico la prima struttura ponendo la chiave e il counter a 1, incrementandola
-la confronto con la chiave con più elementi nella lista (ma da dove la prendo?)
-se la chiave confrontata è diversa, confronto l'altra struttura
-se il counter è maggiore la sostituisco
-proseguo con il nodo successivo, la vecchia struttura viene reimpostata a 1 e incrementata per essere riconfrontata con quella che contiene la chiave con più elementi

Fatico a capire cosa dovrei fare con gli step, figuriamoci in codice... :suicidio:

Scandire una sola volta ti è impossibile se l'array non è ordinato. Se non vuoi ordinare puoi comunque creare una tua lista dove ad ogni chiave corrisponde un contatore (era un metodo scritto sopra), ma ad ogni nodo devi poi andare a cercare il corrispondente nodo nell'altra lista. In questo modo non so quanto tu possa guadagnare rispetto al sort e confronto ( O(n*logn + n) -> O(n*logn)).
Comunque:
-Fai il merge e ottieni una lista sola
-Contatore della struct_MAX impostato a 0
-Inizi il ciclo e modifichi la struct_TEMP con i valori del primo nodo
-Per ogni nodo uguale incrementi il contatore di TEMP
-Appena cambia, se TEMP.count > MAX.count allora MAX = TEMP, sennò non fai nulla. Resetti il valore di TEMP.count e TEMP.key sarà la key del nodo successivo
-Avanti cosi fino alla fine.

 

[DispatchCode]

Un esempio banale basato sul tuo codice potrebbe essere l'aggiunta di queste due funzioni ora che ci penso:

int hash(int key, int size)
{
    return key%size;
}


int getMax(lista l)
{
    int map[MAX_CHIAVE] = {0};
   
    nodo *tempnodo = l.testa;
    while (tempnodo)
    {
        map[hash(tempnodo->chiave, MAX_CHIAVE)]++;
        tempnodo = tempnodo->next;
    }
   
    int i = 0;
    int max   = map[0];
    // sarebbe sensato ordinare la mappa in modo decrescente e leggere [0]
    while(++i < MAX_CHIAVE)
    {
        if(max < map[i])
            max = map[i];
    }
   
    return max;

}

In questo modo hai una mappa con un hash come chiave. In questo caso funziona bene perchè sai di non avere una chiave maggiore di MAX_CHIAVE. Se la chiave fosse qualsiasi numero N, avrebbe invece senso lasciare come dimensione di questo array MAX_ESERCIZIO.
E' decisamente banale come funzione di hash, e chiaramente in situazioni differenti con valori appunto casuali compresi nell'intervallo di un int, andrebbero gestite le collisioni.
In questo caso i valori sono pochi; dovrebbe funzionare, ma appunto... occhio alle collisioni.

Non ho tempo per ordinare la mappa, quindi effettuo un altro ciclo per cercare il massimo; ordinando l'array in maniera decrescente sarebbe meglio, così basterebbe prendere l'elemento in posizione [0].

Il vantaggio in questo caso, al netto di eventuali collisioni, è che effettui i dovuti calcoli in un tempo O(n) (dove n è la lunghezza della lista). A questo andrebbe sommato il tempo di ordinamento della mappa, che è grande comunque 1/3 dell'altro (almeno nel caso di esempio); diciamo quindi O(n/3).

 

[Andretti60]

Dal main() vedo che al momento usi solo il metodo NaiveMaxOccurrence() che è sbagliato, in quanto nel loop interno parte sempre dalla testa, invece che dal nodo successivo a quello corrente.

Il metodo che usa la tabella hash non è completo, ma di fatto non è una hash bensì una lookup ed è inusabile se il numero massimo delle chiavi è elevato. Vero che è veloce, ma ci impiegherebbe una vita ad allocare la memoria (così come è scritto darebbe errore in quanto allocheresti troppa memoria nello stack, con il tragico overflow).

Questo è il classico esempio che mostra come le liste concatenate non vadano bene per cercare direttamente i valori, in quanti traversare una lista non è efficiente.
Il metodo migliore è quello di ordinare la lista in precedenza, per poi creare una tabella lookup "sparsa" che acceda solo ad alcuni valori della lista, e quindi utilizzare una ricerca "dividi e conquista" tra gli elementi intermedi. I risultati sono inpressionanti, la ricerca è quasi immediata.

 

[DispatchCode]

Il metodo che usa la tabella hash non è completo, ma di fatto non è una hash bensì una lookup ed è inusabile se il numero massimo delle chiavi è elevato.

Ecco, concordo.
Proprio per questo motivo dicevo che va bene con questi valori e che al crescere ci sarebbero anche conflitti.

Comunque sempre ottimi interventi i tuoi Andretti, è un piacere leggerti. :)

 

[FiloRp]

Un esempio banale basato sul tuo codice potrebbe essere l'aggiunta di queste due funzioni ora che ci penso:

Spoiler

int hash(int key, int size)
{
    return key%size;
}


int getMax(lista l)
{
    int map[MAX_CHIAVE] = {0};
  
    nodo *tempnodo = l.testa;
    while (tempnodo)
    {
        map[hash(tempnodo->chiave, MAX_CHIAVE)]++;
        tempnodo = tempnodo->next;
    }
  
    int i = 0;
    int max   = map[0];
    // sarebbe sensato ordinare la mappa in modo decrescente e leggere [0]
    while(++i < MAX_CHIAVE)
    {
        if(max < map[i])
            max = map[i];
    }
  
    return max;

}

In questo modo hai una mappa con un hash come chiave. In questo caso funziona bene perchè sai di non avere una chiave maggiore di MAX_CHIAVE. Se la chiave fosse qualsiasi numero N, avrebbe invece senso lasciare come dimensione di questo array MAX_ESERCIZIO.
E' decisamente banale come funzione di hash, e chiaramente in situazioni differenti con valori appunto casuali compresi nell'intervallo di un int, andrebbero gestite le collisioni.
In questo caso i valori sono pochi; dovrebbe funzionare, ma appunto... occhio alle collisioni.

Non ho tempo per ordinare la mappa, quindi effettuo un altro ciclo per cercare il massimo; ordinando l'array in maniera decrescente sarebbe meglio, così basterebbe prendere l'elemento in posizione [0].

Il vantaggio in questo caso, al netto di eventuali collisioni, è che effettui i dovuti calcoli in un tempo O(n) (dove n è la lunghezza della lista). A questo andrebbe sommato il tempo di ordinamento della mappa, che è grande comunque 1/3 dell'altro (almeno nel caso di esempio); diciamo quindi O(n/3).

Tanto il fatto che programmare in C non fa per me è più che constatato, per cui vado con la domanda stupida.
Questa funzione hash sarebbe da utilizzare al posto della funzione ContaRipetizioni?
Considera che sia MAX_ESERCIZIO sia MAX_CHIAVE sono casuali...

Scusate ma sto facendo davvero fatica, sono arrugginito in maniera imbarazzante

Dal main() vedo che al momento usi solo il metodo NaiveMaxOccurrence() che è sbagliato, in quanto nel loop interno parte sempre dalla testa, invece che dal nodo successivo a quello corrente.

Il metodo che usa la tabella hash non è completo, ma di fatto non è una hash bensì una lookup ed è inusabile se il numero massimo delle chiavi è elevato. Vero che è veloce, ma ci impiegherebbe una vita ad allocare la memoria (così come è scritto darebbe errore in quanto allocheresti troppa memoria nello stack, con il tragico overflow).

Questo è il classico esempio che mostra come le liste concatenate non vadano bene per cercare direttamente i valori, in quanti traversare una lista non è efficiente.
Il metodo migliore è quello di ordinare la lista in precedenza, per poi creare una tabella lookup "sparsa" che acceda solo ad alcuni valori della lista, e quindi utilizzare una ricerca "dividi e conquista" tra gli elementi intermedi. I risultati sono inpressionanti, la ricerca è quasi immediata.

Il loop interno si corregge modificando il While esterno (nodo *tempnodo = l.testa;)?

 

[DispatchCode]

Chiedo venia ma non riesco a leggere ti post precedenti al momento. Appena mi sarà possibile, magari più tardi o domani, leggerò e risponderò a tutto.

 

[Andretti60]

...
Scusate ma sto facendo davvero fatica, sono arrugginito in maniera imbarazzante
...

Il loop interno si corregge modificando il While esterno (nodo *tempnodo = l.testa;)?

Esatto, quella e' l'istruzione da modificare.
Non sentirti imbarazzato, programmare non e' facile e le liste concanetanate sono ostiche.

 

[FiloRp]

Innanzitutto, buon anno a tutti.
Purtroppo la scadenza è a brevissimo e sono "indietro come le nespole", quindi anche oggi si programma!

Chiedo venia ma non riesco a leggere ti post precedenti al momento. Appena mi sarà possibile, magari più tardi o domani, leggerò e risponderò a tutto.

Non c'è problema, non capivo solo se il codice che hai condiviso sostituisca tipo_risultato ContaRipetizioni(lista l) oppure direttamente l'ordinamento con merge sort e i confronti successivi

Esatto, quella e' l'istruzione da modificare.
Non sentirti imbarazzato, programmare non e' facile e le liste concanetanate sono ostiche.

Seguendo i vostri suggerimenti ho implementato Merge Sort, ma rileggendo tutta la discussione mi sono accorto di essermi spiegato male sulla funzione tipo_risultato ContaRipetizioni(lista l). Non posso eliminarla, ma solo modificarla. Il problema è che non ho mai scritto niente con delle HashMap, non so neanche dove iniziare a modificarla

 

[DispatchCode]

Io sono ancora tramite telefono.

Comunque se non puoi usare una hash map già fatta, puoi scriverla. Bisogna vedere se ne vale la pena, e questo dipende dallo scopo di ciò che stai realizzando e da ciò che il docente vuole.

A livello teorico ti serve un array, il "mazzo", che contiene le tue coppie key/value. Ti serve pure un puntatore ad una lista o anche ad un'altra hash map per gestire le collisioni.

Forse la parte difficile è questa: trovare una funzione di hash, e qui puoi googolare per trovare qualcosa. La funzione torna un intero al quale farai il modulo (tipo nella mia funzione); questa è la chiave della tua mappa.

Più la funzione di hash è buona, meno collisioni avrai in linea di massima.

Ps. Buone feste a tutti!

 

[Andretti60]

Innanzitutto, buon anno a tutti.
Purtroppo la scadenza è a brevissimo e sono "indietro come le nespole", quindi anche oggi si programma!
...
Seguendo i vostri suggerimenti ho implementato Merge Sort, ma rileggendo tutta la discussione mi sono accorto di essermi spiegato male sulla funzione tipo_risultato ContaRipetizioni(lista l). Non posso eliminarla, ma solo modificarla. Il problema è che non ho mai scritto niente con delle HashMap, non so neanche dove iniziare a modificarla

Buon Anno anche a te.
A quanto ho capito il metodo ContaRipetizione e' stato scritto dal tuo insegnante, che ha confuso una tabella hash con una tabella lookup. Lascia quindi da parte la costruzione di una tabella hash (che e' cosa estremamente complicata e ha bisogno di tutta una serie di lezioni a parte) e concentrati nel metodo che ha scritto lui. In pratica ogni elemento del vettore hash contiene il numero di volte che la chiave corrispondente all'indirizzo di tale vettore e' presente nella lista. Quindi

• azzera tutti gli elementi del vettore hash
• traversa la lista, e per ogni elemento incrementa di uno l'elemento del vettore il cui indirizzo e' lo stesso della chiave, ossia

hash[tempnodo->chiave] += 1;

• attraversa il vettore hash e trova il valore massimo
• stampa tale valore
• finito

 

[Andretti60]

Tra l'altro la differenza tra hash e lookup e' molto semplice: la tabella lookup usa il valore della chiave come indirizzo del vettore, mentre la hash calcola tale indirizzo dalla chiave usando un algoritmo (che può essere estremamente complicato). Puoi quindi capire come la hash sia molto più potente e permetta anche di indirizzare valori che non siano numerici. Ma al momento lasciamola da parte.

 

[DispatchCode]

Un esempio banale basato sul tuo codice potrebbe essere l'aggiunta di queste due funzioni ora che ci penso:

int hash(int key, int size)
{
    return key%size;
}


int getMax(lista l)
{
    int map[MAX_CHIAVE] = {0};
   
    nodo *tempnodo = l.testa;
    while (tempnodo)
    {
        map[hash(tempnodo->chiave, MAX_CHIAVE)]++;
        tempnodo = tempnodo->next;
    }
   
    int i = 0;
    int max   = map[0];
    // sarebbe sensato ordinare la mappa in modo decrescente e leggere [0]
    while(++i < MAX_CHIAVE)
    {
        if(max < map[i])
            max = map[i];
    }
   
    return max;

}

In questo modo hai una mappa con un hash come chiave. In questo caso funziona bene perchè sai di non avere una chiave maggiore di MAX_CHIAVE. Se la chiave fosse qualsiasi numero N, avrebbe invece senso lasciare come dimensione di questo array MAX_ESERCIZIO.
E' decisamente banale come funzione di hash, e chiaramente in situazioni differenti con valori appunto casuali compresi nell'intervallo di un int, andrebbero gestite le collisioni.
In questo caso i valori sono pochi; dovrebbe funzionare, ma appunto... occhio alle collisioni.

Non ho tempo per ordinare la mappa, quindi effettuo un altro ciclo per cercare il massimo; ordinando l'array in maniera decrescente sarebbe meglio, così basterebbe prendere l'elemento in posizione [0].

Il vantaggio in questo caso, al netto di eventuali collisioni, è che effettui i dovuti calcoli in un tempo O(n) (dove n è la lunghezza della lista). A questo andrebbe sommato il tempo di ordinamento della mappa, che è grande comunque 1/3 dell'altro (almeno nel caso di esempio); diciamo quindi O(n/3).

In pratica il codice risultante sarà molto simile a questo, solo che non avrai il modulo.

 

[FiloRp]

Buon Anno anche a te.
A quanto ho capito il metodo ContaRipetizione e' stato scritto dal tuo insegnante, che ha confuso una tabella hash con una tabella lookup. Lascia quindi da parte la costruzione di una tabella hash (che e' cosa estremamente complicata e ha bisogno di tutta una serie di lezioni a parte) e concentrati nel metodo che ha scritto lui. In pratica ogni elemento del vettore hash contiene il numero di volte che la chiave corrispondente all'indirizzo di tale vettore e' presente nella lista. Quindi

• azzera tutti gli elementi del vettore hash
• traversa la lista, e per ogni elemento incrementa di uno l'elemento del vettore il cui indirizzo e' lo stesso della chiave, ossia

hash[tempnodo->chiave] += 1;

• attraversa il vettore hash e trova il valore massimo
• stampa tale valore
• finito

Spoiler: Codice:

tipo_risultato ContaRipetizioni(lista l) // guarda questa soluzione di esempio: se la completi, sarà abbastanza efficiente in tempo,
                                         // e tra le meno efficienti in spazio
{                                        // se presenti questa stessa soluzione sarà molto probabile che tu prenda un voto molto basso
    tipo_risultato risultato;
    int memoria = 0;
    int hash[MAX_CHIAVE];
    nodo *tempnodo = l.testa;
    int max=0;
    // usa hash come tabella HASH ad accesso diretto per contare quante volte si presenta una certa chiave

    for(i=0;i<MAX_CHIAVE;i++){
        hash[i] = 0; 
    }
    while (tempnodo){
        hash[tempnodo->chiave] += 1;
        tempnodo = tempnodo->next;
    }
    for (i=0; i<MAX_CHIAVE; i++) {
        if (max<hash[i]){
            max=hash[i];
        }
    }
    printf("%d\n", hash[i]);

    // esplora tutta la tabella alla fine per trovare il massimo numero di occorrenze di qualche chiave
    memoria = sizeof(hash) + sizeof(nodo) + sizeof(risultato) + sizeof(memoria);
    risultato.memoria = memoria;
    risultato.numero = max;
    return risultato;
    // osserva: non è necessario liberare spazio, qui. Se avessi utilizzato strutture dinamiche, avrei dovuto liberarle alla fine dell'esecuzione.
}

Può andare bene così?

 

[DispatchCode]

Sempre da telefono, spero di essere comunque chiaro...

int hash[MAX_CHIAVE] = {0};

Ti consente di inizializzare a 0 senza quel for esplicito.

Puoi usare hash[tempnodo->chiave]++ per incrementare.

Per il resto mi sembra corretto visto così.