PROBLEMA Algoritmo ricerca occorenze con lista concatenata - C

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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
 

rodhellas

Utente Èlite
1,521
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
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
 
  • Like
Reactions: FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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
 

rodhellas

Utente Èlite
1,521
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
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:
 
  • Like
Reactions: FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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
 

rodhellas

Utente Èlite
1,521
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
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
 
  • Like
Reactions: FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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
 

rodhellas

Utente Èlite
1,521
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
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).
 
  • Like
Reactions: FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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?
 

rodhellas

Utente Èlite
1,521
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
Tutto tranne il main e la funzione Naive è stato scritto dal prof. La funzione tipo_risultato ContaRipetizioni(lista l) è da modificare?
Non direi, se ordini e poi confronti non la dovresti usare perchè complicheresti qualcosa di semplice.
Comunque io sentirei che ha da dire @DispatchCode
 
Ultima modifica:
  • Like
Reactions: FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10

rodhellas

Utente Èlite
1,521
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit

DispatchCode

Utente Attivo
1,151
754
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
HDD
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
GPU
Nvidia Geforce GTX 960M, 4GB
Audio
Realtek
Net
30Mbps/3Mbps con Eolo
OS
Windows 10 64bit
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.
 
  • Like
Reactions: rodhellas e FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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?
 

rodhellas

Utente Èlite
1,521
427
CPU
Ryzen 5 3600
Dissipatore
GELID Phantom
Scheda Madre
MSI B450 Gaming Plus Max
HDD
500GB m.2 + 2TB HDD
RAM
16GB Corsair LPX 3000mhz
GPU
Gigabyte GTX 960 OC
Audio
Integrata
Monitor
SyncMaster 223BW
PSU
Antec HCG-520M
Case
Meshify C
Net
Gigabit Fastweb
OS
Windows 10 64bit
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.
 

Entra

oppure Accedi utilizzando

Hot: E3 2021, chi ti è piaciuto di più?

  • Ubisoft

    Voti: 28 21.5%
  • Gearbox

    Voti: 2 1.5%
  • Xbox & Bethesda

    Voti: 84 64.6%
  • Square Enix

    Voti: 10 7.7%
  • Capcom

    Voti: 6 4.6%
  • Nintendo

    Voti: 18 13.8%
  • Altro (Specificare)

    Voti: 11 8.5%