Newsgroup: it.comp.lang.c++
Titolo: generazione completa di valori tratti da un insieme (spazio ?) senza ripetizione e senza buchi

Ho un problema teorico, che magari per voi è una 
sciocchezza, ma vorrei una conferma o una spiegazione.
Premessa : non sono ammissibili strutture sparse di sorta 
(ove si intendano liste, alberi binari e derivati, mappe 
dizionari etc)
Ammettiamo di avere un insieme fitto (forse meglio dire 
continuo, nel senso che lo spazio di tutti i valori 
ammissibili non ha buchi in origine, e che devono essere 
enumerati una e una sola volta), ma nel quale siano stati 
praticati dei "buchi" man mano che l'uso dei dati stessi 
procede (utilizzi e cancellazioni) : alcuni valori sono 
stati usati, altri sono liberi. Bisogna generare valori in 
modo da garantire di poter individuare (in modo efficiente) 
qualsiasi buco creato.
Un qualsiasi algoritmo che generi valori, in modo da 
garantire di trovare il primo valore non usato (un buco), ad 
eccezione del caso di una potenzialmente lunghissima 
scansione lineare (generando quindi i valori con incrementi 
o decrementi di 1 risp. dal minimo o massimo teorico, e 
ricerca della presenza o assenza dei medesimi nel 
"database"), mi sembra di intuire che non possa fare a meno 
di non memorizzare una matrice di bit che sia almeno grande, 
(in bit non in byte) 2^n, dove n è la profondità di bit che 
rappresenta l'insieme numerico dato.
Cioè, se ho bisogno di generare e verificare se già usati, 
tutti i possibili valori interi a 16 bit (65536 valori), non 
volendo fare ricerche con scansione lineare, mi pare che non 
possa allocare una mappa di consultazione immediata più 
piccola di 655536 bit.
Mi sbaglio ? Ammetto di non conoscere la tecnica chiamata di 
hashing, e quindi non so valutare se potrebbe essere 
pertinente al problema o meno.
Aggiungo che non sono ammissibili strutture sparse di sorta 
(ove si intendano liste, alberi binari e derivati, mappe 
dizionari etc)
grazie in anticipo di ogni dritta
ciao
Soviet_Mario

 intendano liste, alberi binari e derivati, mappe dizionari etc)
Gia' detto.
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 Gia' detto.
Bon, ti ringrazio intanto per l'attenzione.
Qualora la prima esposizione fosse stata nebulosa, e questo 
secondo esempio un po' più dettagliato ti facesse frullare 
qualche altra idea per evitare possibili situazioni di forte 
rallentamento come quella limite che ho esposto, i pareri 
sono graditi.
Per inciso, ho ripreso in mano alcuni abbozzi di scrivere 
una specie di gestore di un mini file system interamente 
contenuto in un unico file su disco, ad uso di altri 
programmi che vogliano loggare, tenere i propri dati salvati 
in un ordine apparente ma con basso uso di risorse handle 
vere e proprie dell'OS e avantaggiandosi del suo caching su 
un unico file grande invece di tanti files piccoli sparsi 
ovunque.
So che esistono già peraltro, ma non ho trovato alcun codice 
sorgente.
ciao
Soviet

 Vedi: 
http://en.wikipedia.org/wiki/Free_list
CUT
peraltro in questa pagina ho visto due chicche che mi sono 
piaciute a prescindere e che ignoravo : la BUDDY allocation 
e la SLAB allocation .... che geni sti tipi !
ciao
Soviet

P.S. sto anche prendendo in considerazione di abbassare le mire.
Specialmente nel caso di interi a 32 bit, dato che il 
piccolo FS che ho in mente non si troverà mai 
realisticamente a usare 2^32 files diversi (ma volendo 
magari estendere il limite di 65536 files magari a 100'000), 
stavo pensando di predeterminare un numero X di files 
massimi tollerabili dal FS, e allocare una matrice statica 
della medesima dimensione, inizialmente vuota, dove 
registrare ciascun valore di handle usato, aggiungendocelo 
come una specie di stack di dimensione massima prefissata.
Ogni volta che cancello un dato file, cerco il suo handle in 
testa alla matrice, dall'indice 0 al Top of Stack, quando lo 
trovo prendo il valore al Top of Stack e ce lo sovrascrivo, 
(e al suo posto metto zero).
La ricerca diventa O(n), dato che lo stack non è ordinato, 
ma rapida perché è in un array massiccio, e non richiede di 
esaminare l'intera FAT per ciascun valore.
Mah.
In effetti mi piacerebbe implementare un albero, ma sono 
scettico di avere la capacità di mapparlo interamente dentro 
una risorsa flat, contigua e di dimensione predeterminata, e 
senza sprecare spazio.
Vabbè, mo' passo e chiudo
riciao
Soviet

 è libero)
La descrizione che fai non è chiarissima. Ma mi pare che la soluzione 
sia proprio quella indicata da Carlo Milanesi. Sei sicuro di aver capito 
esattamente come funziona? La lista dei blocchi liberi, infatti, non è 
una struttura esterna, ma si trova all'interno dei blocchi della FAT. 
Dunque quando salvi la FAT, hai già salvato anche la lista.
E.

 una struttura esterna, ma si trova all'interno dei blocchi della FAT. 
siccome fai quest'osservazione, presumo di non aver capito 
quel che C. Milanesi aveva suggerito anche se inizialmente 
mi era parso di si .... curiosamente, anche per quel che 
scrivi circa la mia FAT, ho la sensazione che, come hai 
anche detto, non sono riuscito manco io a farmi capire. La 
FAT è quel che è e funge, ho bisogno di una struttura 
separata (l'archivio indici usati) e monolitica. Se la 
free-list è questo, allora non ho capito come funge (anche 
se la pagina di wiki mi pareva chiara).
Ho letto varie volte la risposta di C. Milanesi, ma non 
riesco a capire cosa potrei avere capito male ... Mistero, 
eh he he !
ciao
Soviet


 pareva chiara).
Allora tu hai una FAT. Nella quale ci possono essere dei blocchi liberi. 
L'idea della free-list è la seguente: siccome i blocchi liberi sono 
inutilizzati (per definizione) utilizzo essi stessi per memorizzare la 
posizione dei blocchi liberi. Questo, a parte l'implementazione, 
dovrebbe chiarirti qual è il concetto, e se si applica al tuo caso.
E.