Newsgroup: it.comp.lang.c++
Titolo: Matrici in memoria secondaria

Salve ragazzi,
sto lavorando alla mia tesi da un pò di mesi e da 1settimana sono
bloccato sul seguente quesito.
Trovare una rappresentazione delle matrici (o array bidimensionali) in
memoria secondaria. (sia matrici dense che matrici sparse) utilizzando
tecniche del c++.
L'argomento è abbastanza complesso e ovviamente il lavoro devo farlo
io, però se qualcuno di voi si è imbattuto in qualcosa del genere, o
conosce libri, siti, appunti,... me lo dica please!
Grazie Alex

 tecniche del c++.
Cos'è la memoria secondaria?
E.

 all'HD e simili. O no? ^_^
Ma ha senso, al giorno d'oggi, gestire direttamente lo swap della 
memoria su HD? Oppure si sta parlando semplicemente di serializzazione?
E.

macsw ha scritto:

ipotizzando che tu intenda il disco (e quindi un FILE, ad 
accesso diretto, binario) come memoria secondaria, posso 
darti una dritta sulla mappatura semplice (ma le cui 
performance sono IMPREVEDIBILI, dipendendo completamente dal 
buffering dell'OS e/o del runtime di libreria, anzi, di 
entrambi), ma relativa ad un array unidimensionale.
Il concetto in soldoni è creare una classe, es. DiskArray 
che implementi l'overload di OPERATOR [].
Il problema è distinguere quanto Matrix [3] è un RValue o un 
LValue (tipo nelle assegnazioni).
Un metodo è quello detto della generazione del temporaneo.
Definisci una classe (anche NESTED, invisibile da fuori) 
TempMatrixItem.
Operator [] in effetti ritornerà un TempMatrixItem, 
invocando il costruttore del temporaneo e passandogli le 
informazioni necessarie all'accesso a disco (le calcola 
dall'indice che riceve dal chiamante), come l'offset su 
file, l'indirizzo di memoria del valore da scrivere, e con 
sizeof anche la sua dimensione. Ciascuno di questi dati 
rilevanti sarà un membro della classe temporanea (che viene 
quindi istanziata aware del suo collegamento al disco, anche 
senza ancora sapere se sarà in lettura o scrittura
In TempMatrixItem fai l'overload sia di operator = 
(ASSIGNMENT), in varie versioni a seconda dei diversi RValue 
o meglio templatizzato, usato quando l'accesso al disco è in 
scrittura, sia di (vari, meglio ancora templatici) operator 
TYPENAME (), entro cui farai la lettura da file.
Ora non ho tempo di cercare e incollarti codice di esempio, 
lo trovai su computer programming di almeno una decina 
d'anni fa.
volendo estendere a 2 D (o  enne dimensioni invero), con un 
lieve mutamento della sintassi rispetto al tradizionale 
subscipt con le quadre, si può fare l'overload di OPERATOR 
() cioè della "function call". Rispetto a operator [] questo 
è molto più flessibile, potendo ricevere quanti e quali 
parametr vuoi (su delle stringhe lo usavo addirittura 
indicizzando con sottostringhe, per intenderci).
Devi però implementare tu l'aritmetica per il calcolo 
dell'offset fisico sul file, che è sempre unidimensionale, a 
partire dai tuoi indici, facendo quindi le varie 
moltiplicazioni e somme appropriate, esattamente come fa il 
compilatore per le matrici, ma a mano.
ciao
Soviet_Mario


Grazie ragazzi per le risposte.
Per rispondere alla domanda "perchè in memoria secondaria?", è
naturale che non è una cosa di tutti i giorni ma sperimentalmente nei
calcoli scientifici si usano matrici di grandissime dimensioni, anche
di 1 milione x 1milione di elementi.
-Ho sbagliato a non dirvi cosa intendo per memoria secondaria: un file
di testo (txt), oppure anche un database (di tipo spaziale). Potete
aiutarmi in questo secondo caso?
I consigli mi sono stati utili. Se qualcuno di voi ha anche del codice
da mostrarmi o una qualche guida mi farebbe un piacere enorme.
A presto, michele

 di testo (txt), 
il metodo che ti dissi lavora meno peggio per file binari, 
ma può essere esteso anche al caso del formato testo, purché 
tu stesso hai cura di
1) NON aggiungere nessun classico carattere di controllo 
flusso testo (newline, tab, carriage return)
2) formattare tu stesso il layout dei dati in modo che 
ciascuna voce abbia ampiezza costante (in byte, non solo in 
caratteri).
Se ti attieni, puoi comunque usare le primitive di I/O 
binario (conoscendo l'ampiezza di ciascuna voce puoi 
procedere al calcolo dell'offset assoluto su file a partire 
da una qualsiasi "tupla" di indici
.....
Se viceversa non vuoi rinunciare al testo formattato in modo 
classico, con righe di lunghezza variabile, dimentica ogni 
parvenza di accesso random a velocità accettabile (il che 
coi grandi file che dici, significa un enorme superlavoro di 
seeking sul file).
Capisco che formattare un testo a record di dimensione 
costante potrebbe comportare spreco di spazio su disco, ma è 
l'unico modo per localizzare a priori gli elementi, non ci 
sono scorciatoie rapide, specie se devi anche garantire 
dinamicità (molteplici accessi in lettura e scrittura, che 
ti renderebbero molto pesante, che so, tenere tabelle cache 
con puntatori alle righe, colonne e quant'altro).
ciao
Soviet_Mario



-- 
-riko

 LValue (tipo nelle assegnazioni).
Questo non è un problema. Basta usare per bene il C++ e se la cava. Ci
sono fior di articoli a riguardo.
Il punto è che non ho capito a cosa serve tutto l'anbaradan che hai
descritto e cosa farebbe più di un thin layer sopra uno stream su file.
Ricordo anche che mettersi a lottare con il sistema operativo per
gestire cache e swap (ovvero pensare di gestirle da se) è dannoso ed una
perdita di tempo. Comunque è proprio per questo che esiste la
programmazione ad oggetti: se uno vuole mettersi in lotta in un secondo
tempo (per esempio perchè il sistema operativo fa più danni che altro)
può.
-- 
-riko

 di 1 milione x 1milione di elementi.
Se lavori su un sistema macchina a 64-bit (e dovresti, visto il tipo
di applicazione), la soluzione piu' semplice mi sembra sia utilizzare
i memory mapped file (
http://en.wikipedia.org/wiki/
Memory_mapped_file ). Con questa tecnica puoi vedere un file come se
fosse memoria primaria, i.e. un array C. Il sistema operativo si
occupa di mantenere la sincronizzazione tra file e memoria in modo
trasparente al programmatore.
In pratica ti crei una classe Matrice che internamente crea un file
temporaneo su disco e lo mappa in memoria. Poi a questa classe fai
esporre i tipici metodi pubblici che ci si aspetta da una classe
matrice. Internamente invece lavori su un array di float o double (che
sono mappati su disco).
In questo modo le performance non saranno fantasmagoriche (si perdera'
molto tempo in I/O) ma almeno dovresti riuscire a fare i calcoli senza
che il programma vada in out of memory. Poi, a seconda del tipo di
operazioni piu' frequente che fai su queste matrici, esiste una
rappresentazione ottimizzata su disco (i.e. che minimizza il numero di
richieste I/O). Per ora ti consiglio di memorizzare le matrici dense
per righe o per colonne che e' semplice e va mediamente per la maggior
parte dei casi.
Per quanto riguarda le matrici sparse, di solito non rappresentano un
grosso problema per la memoria, ma questo ovviamente dipende appunto
da quanto sono sparse.
Considera che i memory mapped file sono OT in questo gruppo e i metodi
per utilizzarli dipendono dalla piattaforma che usi. Nel caso ti serva
aiuto a riguardo puoi chiedere su it.comp.programmare.win32 per
windows o it.comp.os.linux.development per linux.
Saluti,
The Librarian
PS: per piacere quota bene

 
Ripeto : suggerivo di fare come se il buffering fosse 
trasparente e non esistesse affatto. Al massimo non fa nulla 
credo. Anzi, se accedi in modo random su un file immenso, 
grossomodo non agevola manco tanto o niente, ma non penso 
che possa fare tali danni dal porsi il problema di 
disabilitarlo.
ciao
Soviet_Mario

 Soviet_Mario

 presente o meno.
Anche l'HD presumibilmente ha un buffer.
E.

 E.

 Soviet
Per 10€ o meno non predenderai anche la RAM nelle chiavi ?
(In effetti in qualche controller c'e', ma in alcuni non supera i 32K).
B.