Newsgroup: it.comp.lang.c++
Titolo: [importante] aritmetica di interi "a minore precisione"

Ciao a tutti,
scusate l'aggiunta "importante" ma la domanda che vi faccio e' in effetti
molto importante per il miglioramento del programma che ho scritto 
e ci terrei molto a implementarlo.
Essenzialmente ho un reticolo di interi (dell'ordine di 100^3)
dove pero' ogni intero ha un range effettivo molto piccolo : [0,32].
Siccome reticoli di queste dimensioni o piu' grandi (vorrei arrivare a
gestire reticoli 200^3) richiedono molta memoria, poter diminuire il numero
di bit necessari per definire un intero (o meglio lasciare gli interi come
seno e creare un usare un nuovo tipo) , significherebbe ridurre
drasticamente la memoria richiesta a parita' di griglia.
Grazie
Massimo

 drasticamente la memoria richiesta a parita' di griglia.
0..32 significa che bastano 5 bit a numero... per ogni int di un 
computer moderno significa poter gestire 6 numeri, ovvero risparmi 6x di 
memoria. Intanto valuta: ti basta? se sě implementi, se no cerchi 
un'altra soluzione... Ad esempio, un array di 32 contatori non va bene?
-- 
"Siamo una generazione di uomini cresciuti dalle donne, mi chiedo se 
un'altra donna č veramente la risposta che ci serve"

 drasticamente la memoria richiesta a parita' di griglia.
Io ho pensato ad una cosa e probabilmente ci sono modi notevolmente migliori
comunque questo puo` essere un inizio.
Supponiamo che i numeri che vuoi rappresentare siano >=0 e supponiamo di non
volere andare a lavorare esplicitamente con i bit e di voler tenere distinto
ogni singolo numero, la mia idea e` questa:
visto che un int occupa 4 byte e a te ne bastano 3 (infatti: 2^24 - 1 =
16777215) ti allochi per ogni numero 3 byte di memoria e invece di fare
delle assegnazioni con l'uguale usi delle memcpy().
Vedi l'esempio seguente
unsigned int uNum = 16777215;
unsigned char bLittleInt[ 3 ];
memcpy( bLittleInt, &uNum, 3 );
uNum = 0;
memcpy( &uNum, bLittleInt, 3 );

 un'altra soluzione... Ad esempio, un array di 32 contatori non va bene?
Cosa intendi con array di contatori? non ti seguo. ma ti voglio seguire :)
spiegati meglio.
Massimo 

 spiegati meglio.
semplice semplice: ti fai un'array di 32 interi (diciamo counter[32]), 
per ogni 0 contenuto nella tua griglia incrementi l'intero in 
counter[0], per ogni 1 incrementi il counter[1] e così via... in questo 
modo però perdi l'informazione riguardante la posizione del valore 
all'interno della griglia.
-- 
"Siamo una generazione di uomini cresciuti dalle donne, mi chiedo se 
un'altra donna è veramente la risposta che ci serve"

 
Ah, ho capito, no purtroppo l'informazione sulla posizione e' fondamentale.
Vado un filo piu' sul dettaglio, magari trovo qualcuno che si occupa di cose
simili alle mia e ci possiamo dare una mano a vicenda.
//
Mi occupo di simulazioni Monte Carlo, in pratica la griglia cui faccio
riferimento altro non e' che una rappresentazione al computer di un
reticolo cristallino, i vari siti della griglia sono gli "atomi" che
interaggiscono tra loro, nel mio caso ogni atomo interaggisce (per
fortuna!!) solo con quelli vicini.
Attraverso una tabella di lookup sono in grado di corvertire l'informazione
su ogni singolo atomo (e quindi la sua interazione con quelli vicini) in un
semplice intero tra [0,32].
Per ogni sito, estraggo un numero tra [0,32] e vedo se la modifica aumenta o
diminuisce l'energia del sistema e cosi' via per un infinita' di volte....
//
Detto questo, se riuscissi semplicemente a definire un "intero
personalizzato" a 5 bit
(considerato poi che NON FACCIO OPERAZIONI MATEMATICHE SU DI ESSO ma
semplici riferimenti alla tabella di loopup) per ogni sito reticolare
sarebbe perfetto.
Grazie Massimo 

Da quel che ho capito tu vuoi una sorta di vettore (o matrice, ma il
concetto e' lo stesso) di dimensione fissa, che sia in grado di "impaccare
il piu' possibile dei valori interi a pochi bit ciascuno.
Si potrebbe definire una classe puo' o meno cosi':
template < unsigned int SIZE, unsigned int BITS >
class packed_vect
  {
  };
da utilizzare ad esempio cosi':
packed_vect<100,5> v;  // 100 valori in a 5 bit di precisione
All'interno della classe servira' calcolare quanti unsigned int effettivi ci
servono per memorizzare i bit totali e riservare lo spazio necessario in un
array privato:
template < unsigned int SIZE, unsigned int BITS >
class packed_vect
  {
  private:
    // valori in un "unsigned int"
    const unsigned int PACKED_VALUES = 32 / BITS;  
    // dimensione dell'array "fisico"
    const unsigned int PACKED_SIZE = SIZE / PACKED_VALUES + 1;
    unsigned int packed[PACKED_SIZE];
  };
A questo punto ci sono due possibilita': una semplice e una elegante...
Quella semplice: si fanno due metodi get e set che consentono di leggere
scrivere un valore in una posizione. Per farlo, dentro i metodi di dovra'
giocare un po' con delle maschere di bit, esempio:
int packed_vect::get( unsigned int i )
  {
  unsigned int pkd_major_pos = i / PACKED_VALUES;
  unsigned int pkd_minor_pos = i % PACKED_VALUES;
  unsigned int tmp_val = packed[pkd_major_pos] >> ( pkd_minor_pos * BITS );
  return tmp_val & MASK;
  }
(MASK e' 2^BITS - 1, e si puo' anche calcolare a compile-time, con un po' di
metaprogrammazione)
La soluzione elegante invece definirebbe un operatore [] nella classe che
ritorna una specie di oggetto-modificatore. Questo, conoscendo
pkd_major_pos, pkd_minor_pos e packed, e' in grado di leggere/scrivere il
singolo valore mediante un operatore di assegnazione e uno di cast verso un
valore unsigned int. Detto a parole forse si capisce poco, se ti interessa
lo spiego un po' meglio :-)
Ciao!
PS: Ho scritto il codice molto velocemente perche' a parole mi spiegavo
peggio, pero' potrebbero esserci degli errori, quindi e' meglio che non ti
fidi, specialmente delle operazioni sui bit!
-- 
Qual'e' il colmo per uno studente-lavoratore?
Avere un quadrato che si crede un rettangolo.

Io ho adottato una soluzione piu` "stl", reimplementando un vector<bool>
o bit_vector, infilandoci due metodi per leggere/scrivere nel cubo un
valore di n bit.
ATTENZIONE: l'ho scritto al volo, non ci sono controlli, sicuramente ci
saranno errori, insomma e` solo uno spunto.
#include<iostream>
#include<vector>
using namespace std;
struct nbit_cube : vector<bool> {
    typedef unsigned const uc;
    uc bits;
    uc edge;
    nbit_cube(uc bits, uc edge)
	: vector<bool>(bits * edge * edge * edge)
	, bits(bits), edge(edge) { }
    uc at(uc x, uc y, uc z) const {
	unsigned v = 0;
	int i = bits;
	do v |= (*this)[address(x,y,z) + i] << i;
	while (i--);
	return v;
    }
    void set(uc x, uc y, uc z, uc v) {
	int i = bits;
	do (*this)[address(x,y,z) + i] = (v >> i) & 1;
	while (i--);
    }
private:
    size_type const address(uc x, uc y, uc z) const {
	return x * edge * edge * bits + y * edge * bits + z * bits;
    }
};
int main()
{
    nbit_cube v(5, 200); // 5 bits e 200 elementi per lato
    v.set(1,2,3, 32);
    cout << 
v.at
(1,2,3) << endl;
}
Saluti
-- 
alef

...

Perche' non cominci con l'usare i char al posto degli interi?
Presumibilmente diminuisci del 75% l'occupazione di memoria senza
quasi modificare il codice.
Ciao,
Nicola

alef wrote:

Grazie! :)
Se funziona proprio come deve, vi cito nell'articolo (ve lo faccio poi avere
in pdf) che scrivero'.
promesso :)
Massimo
Massimo

 valore di n bit.
Si, l'idea di realizzare la classe come contenitore stl-like e' una buona
idea, pero' derivare direttamente da un vector non e' (quasi) mai una buona
cosa, perche' la classe che si ottiene E' ancora un std::vector, quindi si
puo' scrivere v.set(1,2,3, 32) ma anche, ad esempio, v.push_back(1) o
v[100] = 0.
Sarebbe meglio usare il contenimento.

 Sarebbe meglio usare il contenimento.
centro pieno :)
tra l'altro i container non hanno un distruttore virtuale.
-- 
sbi

 
L'efficienza e' un fattore fondamentale del discorso.
Guadagnare in memoria ma perdere in efficienza non e' quello che cerco.
io vorrei tutto :), cmq penso che una buona implementazione, riducendo la
memoria richiesta, dovrebbe anche ridurre i chache miss e quindi anche
l'efficienza.
Potresti essere un po piu' chiaro per quanto riguarda il tuo suggerimento,
in particolare nell'utilizzo delle maschere (non ho mai utilizzato prima
confronti bit a bit, ma penso che in questo caso sara' necessario...)
Massimo

 Sarebbe meglio usare il contenimento.
Suggerimento accolto:
#include<iostream>
#include<vector>
using namespace std;
struct nbit_cube {
    typedef unsigned const uc;
    nbit_cube(uc bits, uc edge)
	: _v( bits * edge * edge * edge)
	, bits(bits), edge(edge) { }
    uc at(uc x, uc y, uc z) const {
	unsigned v = 0;
	int i = bits-1;
	int a = address(x,y,z);
	do v |= _v[a+i] << i;
	while (i--);
	return v;
    }
    void set(uc x, uc y, uc z, uc v) {
	int i = bits-1;
	int a = address(x,y,z);
	do _v[a+i] = (v >> i) & 1;
	while (i--);
    }
private:
    uc bits;
    uc edge;
    vector<bool> _v;
    uc const address(uc x, uc y, uc z) const {
	return x * edge * edge * bits + y * edge * bits + z * bits;
    }
};
ATTENZIONE: c'era un errore, corretto qui con bits-1. Aggiunto "a".
-- 
alef

non ho potuto seguire tutto il thread, ma mi sembra
di capire che vuoi memorizzare una matrice tridimensionale
di interi molto piccoli, tipo 0..31.
Gli elementi che devi memorizzare (200^3) non sono
tanti. A meno che tu di queste matrici non ne
debba utilizzare svariate.
Io, prima degli impaccamenti spinti, proverei
anche con un banale array di char senza troppi inscatolamenti, e classi
intermedie e che ti andrebbe ad occupare esattamente
200*200*200 = circa 8 Mbyte che al giorno d'oggi
sono insignificanti.
Cosi' su due piedi non sono in grado
di valutare se guadagni di piu' in termini di utilizzo di cache
riducendo la memoria impiegata a
200*200*200*(5/8) = 4882 Kb circa impaccando al massimo i valori,
o se perdi per effetto delle varie operazioni binarie
che saresti costretto a fare.
ciao,
g.

 tra l'altro i container non hanno un distruttore virtuale.
Quindi facendo
    vector<bool>* p = new nbit_cube(5,200);
    delete p;
avrò dei problemi. ( "undefined behaviour" ? )
-- 
alef


si
-- 
sbi

 Massimo
In questo caso, il miglior compromesso fra efficienza e riduzione dello
spazio in memoria credo proprio che sia quello che ti hanno proposto Nicola
e Giovanni: creare il vettore di "unsigned char" anziche' di "unsigned
int". Su tutte le architetture che conosco sizeof char = 1 byte, percio'
hai uno spreco di soli 3 bit per ogni valore, ed al tempo stesso "il byte"
viene gestito direttamente dall'hardware di indirizzamento senza bisogno di
maschere di bit o quant'altro...
Ti cosiglio quindi di provare prima questa strada, e valutare attentamente
se valga la pena cercare un'ottimizzazione spaziale piu' spinta a scapito
di un'efficienza sicuramente un po' ridotta.
Nulla vieta comunque di creare una classe che esponga un'interfaccia
standard, che internamente puo' essere implementata con un semplice
unsigned char[] o con qualcosa di piu' raffinato...
Per quanto riguarda le maschere di bit, l'idea in sintesi e' questa:
Un unsigned int, in un'architettura a 32 bit, e' pari appunto a 32 bit di
"spazio utile", quindi e' sufficiente per memorizzare 6 numeri a 5 bit, con
uno spreco abbastanza basso (6.25%). I sei numeri li mettiamo
rispettivamente nei bit da 0 a 4, da 5 a 9, da 10 a 14, ecc.
Se i sei valori sono memorizzati in una variabile "unsigned int packed", per
"recuperare" il valore i-esimo (i=0..5) devi shiftare i bit di packed verso
destra in modo che il numero finisca in posizione 0, poi estrai solo gli
ultimi 5 bit, azzerando gli altri:
unsigned int value = ( packed >> ( i * 5 ) ) & MASK;
Dove sara' definito: 
const unsigned int MASK = 0x1F; // In binario: 11111
Scrivere un nuovo valore di 5 bit in packed e' un po' piu' complicato, per
farlo definiamo:
unsigned int clear_mask = ~( MASK << ( i * 5 ) ); // Diventa: 1..1000001..1
Poi vuotiamo la posizione i di packed e ci "scriviamo" dentro il nuovo
valore:
packed = ( packed & clear_mask ) | ( ( value & MASK ) << ( i * 5 ) );
L'and tra value e MASK in realta' si potrebbe omettere, ma evita di
modificare i numeri adiacenti se, per errore, value contiene piu' di 5 bit
di informazione.
Se pensi che non dovrai mai cambiare il numero di bit per ogni numero (5) lo
puoi cablare direttamante nel codice, ma con un po' di sforzo in piu' e'
possibile renderlo custom...
Buon lavoro!
Ciao,
Francesco.


alef wrote:

Ciao Alef,
ti seccerebbe essere un po piu' chiaro?
Alla fine qual'e' il metodo piu' efficiente e "robusto" di implementazione?
Io sono un fisico non informatico, autodidatta in c++ quindi conosco "bene"
solo le cose che ho gia' affrontato e risolto, e l'operazioni bit a bit
sono del tutto nuove per me, come la metaprogrammazione (programmazione a
compiletime).
Se mi dai qualche chiarimento o qualche riferimento utilie in rete...
Grazie

 Se mi dai qualche chiarimento o qualche riferimento utilie in rete...
Non so, normalmente cerco con google.
L'altro giorno ho dato questo link
ftp://download.intel.com/design/Pentium4/manuals/25366514.pdf
per far vedere come in una CPU 386 sono messi i bit nella memoria.
Pero` qui saremmo OT, a meno che lo Standard non dica qualcosa sui bit.
-- 
alef