PROBLEMA Algoritmo ricerca occorenze con lista concatenata - C

Pubblicità

FiloRp

Utente Attivo
Messaggi
393
Reazioni
24
Punteggio
39
Ciao a tutti,
sto cercando un metodo per ridurre drasticamente i tempi di esecuzioni di un programma che deve riportare in output il numero di volte che compare la chiave che compare più volte.

L'input numerico è casuale e i numeri sono naturali.

C'è un algoritmo più indicato per questo genere di applicazioni?

Grazie in anticipo
 
Immagino tu stia facendo un semplice algoritmo O(n^2) (ovvero doppio ciclo for).
Se non ti interessa risparmiare spazio, puoi usare una lista di supporto o una qualche funzione di hash dove per ogni chiave aggiorni il numero di occorrenze (una sorta di hashmap). Dovrebbe ridurti sullo O(n) se fatto bene.
Quello più semplice sarebbe ordinare la lista e poi fare un ciclo solo per per contare il numero con più occorrenze. O(n*log n) se non erro
 
Immagino tu stia facendo un semplice algoritmo O(n^2) (ovvero doppio ciclo for).
Se non ti interessa risparmiare spazio, puoi usare una lista di supporto o una qualche funzione di hash dove per ogni chiave aggiorni il numero di occorrenze (una sorta di hashmap). Dovrebbe ridurti sullo O(n) se fatto bene.
Quello più semplice sarebbe ordinare la lista e poi fare un ciclo solo per per contare il numero con più occorrenze. O(n*log n) se non erro

In verità fa già utilizzo di una hashmap, ma è comunque una soluzione molto poco efficiente
 
Ah, ma se non metti del codice o non ci dici cosa utilizzi possiamo solo supporre :giudice:
Ecco qua, ci sono anche dei commenti superflui comunque

Codice:
// aggiunto l'algoritmo NaiveMaxOccurrence che conta le ripetizioni del numero piu' comune della lista data
// con complessita' di esecuzione molto sconveniente o(n^2) ma fornisce il risultato certamente corretto

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

#define MAX_ESERCIZIO 15 // prova diversi valori di queste due costanti
#define MAX_CHIAVE 5     // MAX_ESERCIZIO è la lunghezza della lista massima, MAX_CHIAVE è il valore massimo \
                          // non puoi fare ipotesi su questi valori. Non sai quali costanti useró io.

struct tipo_risultato
{
    int numero;
    int memoria;
};
typedef struct tipo_risultato tipo_risultato; // la tua funzione deve restituire un valore di questo tipo

struct tipo_nodo
{
    int chiave;
    struct tipo_nodo *next;
};
typedef struct tipo_nodo nodo; // la lista di input della tua funzione

struct tipo_lista
{
    int cardinalita;
    nodo *testa;
};
typedef struct tipo_lista lista;

/***************************************************************************************************************/

void CreaLista(lista *l)
{
    l->cardinalita = 0;
    l->testa = NULL;
}

nodo *CreaNodo(int chiave)
{
    nodo *nuovonodo = malloc(sizeof(nodo));
    nuovonodo->chiave = chiave;
    nuovonodo->next = NULL;
    return nuovonodo;
}

void Aggiungi(int chiave, lista *l)
{
    nodo *nuovonodo = CreaNodo(chiave);
    nuovonodo->next = l->testa;
    l->testa = nuovonodo;
    l->cardinalita++;
}

void StampaLista(lista l)
{
    nodo *tempnodo = l.testa;
    while (tempnodo)
    {
        printf("%d\n", tempnodo->chiave);
        tempnodo = tempnodo->next;
    }
}

void RiempiLista(lista *l) // questa è solo di prova. Non sai se useró una generazione diversa da questa
{
    for (int i = 0; i < MAX_ESERCIZIO; i++)
        Aggiungi(rand() % MAX_CHIAVE, l);
}

/***************************************************************************************************************/

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;

    // usa hash come tabella HASH ad accesso diretto per contare quante volte si presenta una certa chiave

    // 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.
}

int NaiveMaxOccurrence(lista l){
    int MaxCount = 0;

    nodo *tempnodo2 = l.testa;  //Crea testa del nodo2 su CreaLista l
    while (tempnodo2){          //Finchè esiste tempnodo2

        nodo *tempnodo = l.testa;   //Crea testa del nodo creato in StampaLista
        int count = 0;              //Inizializza Counter a 0
        while (tempnodo){           //Finchè esiste nodo
            if (tempnodo->chiave == tempnodo2->chiave){     //Se la chiave del nodo è uguale alla chiave del nodo2
                count++;                                    //aumento il counter
            }
            tempnodo = tempnodo->next;                      //Passo al numero successivo della lista per verificarlo
        }
        // printf("count of %d is %d\n", tempnodo2->chiave, count);

        if (count > MaxCount){                              //Se il counter è maggiore di MaxCount (originarimente a 0)
            MaxCount = count;                               //settiamo MaxCount uguale al nuovo Count
        }
        tempnodo2 = tempnodo2->next;
    }
    printf("maxcount is %d\n", MaxCount);
}

int main(){
    lista l;
    CreaLista(&l);
    RiempiLista(&l);
    StampaLista(l);
    NaiveMaxOccurrence(l);

    return 0;
}

/***************************************************************************************************************/

Ah, i due cicli comunque ci sono, ma sono while
 
Quindi, escluso ovviamente O(n^2), anche l'uso dell'hash non va bene per problemi di spazio.
Direi che o fai la soluzione intermedia ( quella di fare il sort e confrontare O(n*log n) ) oppure scandisci la lista in cerca di un certo valore, quando lo trovi incrementi il contatore e lo togli dalla lista. Dovrebbe essere comunque sull' O(n).
Volendo poi si potrebbe mettere dei casi in cui se il contatore è maggiore della metà della lista attuale + il conteggio delle altre liste, allora di sicuro quello sarà il più frequente e si ferma qui la ricerca. Ma non è una soluzione sempre vera
 
Quindi, escluso ovviamente O(n^2), anche l'uso dell'hash non va bene per problemi di spazio.
Direi che o fai la soluzione intermedia ( quella di fare il sort e confrontare O(n*log n) ) oppure scandisci la lista in cerca di un certo valore, quando lo trovi incrementi il contatore e lo togli dalla lista. Dovrebbe essere comunque sull' O(n).
Volendo poi si potrebbe mettere dei casi in cui se il contatore è maggiore della metà della lista attuale + il conteggio delle altre liste, allora di sicuro quello sarà il più frequente e si ferma qui la ricerca. Ma non è una soluzione sempre vera

Quale tipo di sorting consigli? Perchè quelli più basilari richiedono n^2, dovrei puntare su un merge o un counting (che non ho idea di come implementare)?
L'altro metodo richiede più tempo di O(n), bisogna confrontare (nel caso migliore) almeno un numero con tutti gli altri!
Inoltre vuoi usare delle euristiche, ci avevo pensato anche io, ma ha senso? Non conosco nè MAX_CHIAVE né MAX_ESERCIZIO
 
Quale tipo di sorting consigli? Perchè quelli più basilari richiedono n^2, dovrei puntare su un merge o un counting (che non ho idea di come implementare)?
L'altro metodo richiede più tempo di O(n), bisogna confrontare (nel caso migliore) almeno un numero con tutti gli altri!
Inoltre vuoi usare delle euristiche, ci avevo pensato anche io, ma ha senso? Non conosco nè MAX_CHIAVE né MAX_ESERCIZIO
Io andrei di merge sort O(n*log n), online trovi delle implementazioni in C. Poi ti basta confrontare una sola volta la lista, finchè è uguale al valore dopo incrementi il contatore, appena cambia confronti sul nuovo valore quelli successivi e incrementi un'altro contatore ( alla fine ti bastano solo due contatori (probabilmente saranno all'interno di una struttura per dire a quale chiave appartengono)).
Per la questione euristica, MAX_CHIAVE e MAX_ESERCIZIO le puoi ricavare scandendo la lista mentre ordini( max_chiave sarà l'ultimo elemento della lista ordinata, max_esercizio è un contatore per ogni nodo che passi).
 
Io andrei di merge sort O(n*log n), online trovi delle implementazioni in C. Poi ti basta confrontare una sola volta la lista, finchè è uguale al valore dopo incrementi il contatore, appena cambia confronti sul nuovo valore quelli successivi e incrementi un'altro contatore ( alla fine ti bastano solo due contatori (probabilmente saranno all'interno di una struttura per dire a quale chiave appartengono)).
Per la questione euristica, MAX_CHIAVE e MAX_ESERCIZIO le puoi ricavare scandendo la lista mentre ordini( max_chiave sarà l'ultimo elemento della lista ordinata, max_esercizio è un contatore per ogni nodo che passi).

Tutto tranne il main e la funzione Naive è stato scritto dal prof. La funzione tipo_risultato ContaRipetizioni(lista l) è da modificare?
 
Leggendo la richiesta iniziale ho pensato ad una chiave a cui è associato un contatore per le ripetizioni. In questo modo risulta anche semplice sapere quale chiave ha un maggior numero di occorrenze.

Quella funzione potresti eliminarla, come suggerisce rod.

Per l'ordinamento invece il discorso è un pò più complesso a causa della lista. Sicuramente farei ricadere la scelta su MergeSort, come già suggerito, oppure su QuickSort. Considerando che operi con dati nella heap, forse sceglierei QuickSort, anche se non si riuscirà ad ottimizzare molto a causa della difficoltà nello sfruttare la cache etc.
 
Leggendo la richiesta iniziale ho pensato ad una chiave a cui è associato un contatore per le ripetizioni. In questo modo risulta anche semplice sapere quale chiave ha un maggior numero di occorrenze.

Quella funzione potresti eliminarla, come suggerisce rod.

Per l'ordinamento invece il discorso è un pò più complesso a causa della lista. Sicuramente farei ricadere la scelta su MergeSort, come già suggerito, oppure su QuickSort. Considerando che operi con dati nella heap, forse sceglierei QuickSort, anche se non si riuscirà ad ottimizzare molto a causa della difficoltà nello sfruttare la cache etc.
Tralasciando il discorso cache (che non ho veramente idea di come ottimizzare o comunque modificare) mi rendo conto che non ho idea da dove iniziare.

Implemento il MergeSort (con le liste? da dove inizio?), poi ho tutti i numeri ordinati. E come mi aiuta per trovare l'elemento che appare più spesso?
 
Tralasciando il discorso cache (che non ho veramente idea di come ottimizzare o comunque modificare) mi rendo conto che non ho idea da dove iniziare.

Implemento il MergeSort (con le liste? da dove inizio?), poi ho tutti i numeri ordinati. E come mi aiuta per trovare l'elemento che appare più spesso?
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.
 
Pubblicità
Pubblicità
Indietro
Top