Salve, sono nuovo del forum e vi ringrazio in anticipo per l'aiuto.
Volevo un vostro parere sull'implementazione di una specie di filesystem che risiede in memoria e ha delle funzioni che devono avere una determinata complessità. È un progetto universitario che porto avanti da fine agosto ma ancora oggi a poche settimane dalla pubblicazione non sono riuscito a giungere ad una conclusione corretta. Vi allego delle immagini che descrivono il progetto perché è abbastanza specifico. Qui viene spiegato
Ora, io ne ho provate di tutti i colori.
Inizialmente ho implementato un albero (come nel disegno, non binario) che è costituito da nodi di questo tipo
struct node {
node* padre;
node* figlio;
node* destro;
node* sinistro;
}
Ogni volta che si crea un figlio lo si fa puntare da child, i figli seguenti dello stesso padre sono identificati dal puntatore destro o sinistro del figlio e dal figlio stesso che quando verrà creato avrà come padre il nodo che effettivamente l'ha creato.
Chiaramente solo l'albero non avrebbe la complessità richiesta dato che dovrei scorrere ogni volta un bel po' di nodi per trovare il giusto posizionamento di quello nuovo, quindi creo una hashmap che mappa stringhe, cercando in internet trovo che la funzione hash djb2
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
funziona piuttosto bene e decido di usarla, il problema è che restituisce valori troppo elevati come index dell'array e dovrei creare una hashmap troppo grande che mi creerebbe problemi per eccesso di memoria. Decido quindi che l'albero così non funziona per l'impossibilità di avere le complessità spaziali palesemente eccessive.
Provo a controllare se un albero binario potrebbe funzionare in questo caso, ragionando però mi viene da pensare che quest ultimo aggiunge in basso i nuovi nodi, qualora dovessi creare tantissimi nodi l'albero sarebbe molto profondo, e se a quel punto dovessi creare una cartella con lunghezza di percorso pari a 1, la funzione create() e find() e tutte le altre non sarebbero della complessità richiesta.
A questo punto mi rimane poco da fare, mi viene in mente un'ultima struttura di cui già dubitavo, si tratta di un nodo con già 1024 puntatori a figli salvati in un array della struttura del nodo. Il problema è, anche qui, che nel momento in cui io debba accedere a una specifica cartella nella complessità specificata dovrei passarmi tutti gli array dei padri e anche dei figli che portano a quella directory. Sorge quindi ancora il bisogno di una funzione hash che mi restituisca in qualche nano secondo l'index dell'array a cui devo accedere in sequenza per raggiungere la path. In questo caso però dovrei avere una funzione hash che lavora su 1024 caselle dell'array, e ogni figlio ha sempre la stessa funzione che calcola l'index per il suo array di figli. La mia paura è che il programma ecceda ancora nell'utilizzo della memoria. Dopo queste ipotesi fallimentari ammetto di trovarmi in difficoltà e non essendomi mai successo inizio ad essere abbastanza demoralizzato.
Posso avere un vostro parere sul giusto metodo di implementazione e di algoritmi che mi permetterebbe di avere delle complessità del genere?
Non riesco proprio a farmi venire in mente altre strutture dati efficienti che possano funzionare.