Ottimizzare risorse utilizzando le Array Multidimensionali (System.Arr...

mercoledì 09 febbraio 2011 - 00.56

Elenco Threads

Stanze Forum

Aggiungi ai Preferiti

Cerca nel forum

EnricoBSC Profilo | Newbie

12 messaggi | Data Invio: mer 9 feb 2011 - 00:56

Buon giorno.
Mi ritrovo ad avere un’ estrema necessità di risparmiare risorse nella gestione delle array multidimensionali che, se istanziate con un numero elevato di dimensioni e di elementi dimensione sono causa di frequenti eccezioni di tipo out of memory. (System.OutOfMemoryException).

Se per esempio istanzio la seguente array di tipo Int32 con il metodo Array.CreateInstance(GetType(int32), New Int32() {5, 12, 32, 4, 7, 54, 5, 9, 15}), creo una matrice il cui numero di combinazioni è pari a:

5* 12*32*4*7*54*5*9*15 = 1.567.641.600

Il metodo Array.CreateInstance() associato ad un tipo non Nullable quale è Int32 alloca automaticamente tutte e 1.567.641.600 le variabili Int32.

Se non vado errato l’oggetto istanziato verrebbe ad occupare come minimo fin da subito un totale di
1.567.641.600 * 4 = 6.270.566.400 Byte.

Per questo motivo se l’array possiede un numero di dimensioni e di elementi troppo elevato genera una OutOfMemoryException.

Ho provato ad istanziare l’array col relativo tipo Nullable<Int32>. Ma l’ OutOfMemoryException viene comunque generata anche se in quel caso, dopo l’invocazione del metodo Array.CreateInstance(), tutti gli elementi della matrice sono impostati a NULL (Nothing).

Le domande sono:
1) Ma un array di valori NULL (Nullable<Int32>) non dovrebbe essere meno capiente in termini di risorse occupate rispetto ad un’array Int32, Double o Short?
2) Utilizzare il tipo Object potrebbe consentire il risparmio di risorse.
3) E soprattutto: esiste un sistema (al di la dei virtual cube e di una razionale gestione delle gerarchie interdimensionali) per comprimere o tenere sotto controllo la dimensione di questi oggetti array?

Grazie per l’attenzione.
Enrico.

aiedail92 Profilo | Expert

993 messaggi | Data Invio: mer 9 feb 2011 - 13:35

Ciao Enrico,

Vedo che è il tuo primo post, quindi intanto benvenuto

Ma passiamo alle tue domande:

>1) Ma un array di valori NULL (Nullable<Int32>) non dovrebbe
>essere meno capiente in termini di risorse occupate rispetto
>ad un’array Int32, Double o Short?

No, anzi al contrario è probabile che occupi più spazio in memoria perché oltre al dato, deve conservarne anche un riferimento.

>2) Utilizzare il tipo Object potrebbe consentire il risparmio
>di risorse.

Stesso discorso. Se anche avessi un array di 1.567.641.600 byte (il tipo di dato più piccolo), occuperesti all'incirca 1.4 GiB (minimo)

>3) E soprattutto: esiste un sistema (al di la dei virtual cube
>e di una razionale gestione delle gerarchie interdimensionali)
>per comprimere o tenere sotto controllo la dimensione di questi
>oggetti array?

Ma la domanda più corretta da porsi è: ti serve davvero un array di queste dimensioni? Forse analizzando meglio il problema ti accorgi che non è necessario, magari affrontandolo con un approccio diverso.

Se ci esponi il problema che sta alla base saremo felici di darti una mano a risolverlo

Luca

EnricoBSC Profilo | Newbie

12 messaggi | Data Invio: mer 9 feb 2011 - 20:06

>Ciao Enrico,
>Vedo che è il tuo primo post, quindi intanto benvenuto

Grazie a voi per la disponibilità. Davvero molto apprezzata.

>>3) E soprattutto: esiste un sistema (al di la dei virtual cube
>>e di una razionale gestione delle gerarchie interdimensionali)
>>per comprimere o tenere sotto controllo la dimensione di questi
>>oggetti array?

>Ma la domanda più corretta da porsi è: ti serve davvero un array di queste dimensioni? Forse analizzando meglio il problema ti accorgi che non è necessario, >magari affrontandolo con un approccio diverso.
>Se ci esponi il problema che sta alla base saremo felici di darti una mano a risolverlo.

Premetto che la nostra scelta è stata quella di non utilizzare i Cubi OLAP per le analisi multidimensionali.
La risposta alla suddetta domanda è: molto probabilmente SI.
Ho implementato un sistema di analisi multidimensionale (simile a quello dei cubi OLAP) che sfrutta appunto le array multidimensionali.
Tramite un algoritmo particolare, assegno ad ogni elemento dell'array multidimensionale il risultato precomputato di aggregazioni calcolate su tabelle di dati (fonti esterne Oracle, SQLServer etc) contenenti milioni di record. In fase di importazione e di creazione dell'array il carico di lavoro è notevole, ma in seguito è possibile effetturare query basate su milioni di record ad una velocità super-sonica. Si tratta di recuperare il valore dell'array, passandogli una semplice matrice di tipo integer contenente gli indici degli elementi dimensione che fungono da attributi dell'elemento. (Per esempio voglio sapere il numero aggragato dei clienti della zona 2 e 3, ai quali viene fornito il servizio di tipo A della tecnologia Y o XY). Se i db venissero interrogati con query dirette sarebbe un bagno di sangue in termini di performance. La tecnica, abbiamo constatato che funziona bene. Il problema si pone su server poco potenti, quando le dimensioni e gli elementi dimensione diventano molto numerosi. In quel caso viene generata la classica System.OutOfMemory exception che limita parzialmente l'efficacia della suddetta tecnica. Per questo motivo la differenza tra 1GB (utilizzando il tipo di dato Byte) e 4 GB (riferito al tipo di dato Int32) diventa fondamentale.
La cosa che mi servirebbe è adottare tutti gli accorgimenti possibili per risparmiare risorse e rendere la suddetta tecnica accessibile anche ai server meno potenti.

>>1) Ma un array di valori NULL (Nullable<Int32>) non dovrebbe
>>essere meno capiente in termini di risorse occupate rispetto
>>a un’array Int32, Double o Short?

>No, anzi al contrario è probabile che occupi più spazio in memoria perché oltre al dato, deve conservarne anche un riferimento.

Era proprio il mio timore. Da debug, una volta creata l'array nullable, l'intellisense mostrava di default tutti gli elementi dell'array impostati a null (prima dell'assegnazione dei valori) invece che tutti zero come nel caso dell'array Int32. Per un'attimo mi sono illuso che in qualche modo venisse creato un riferimento ad una variabile nulla in ogni elemento delle dimensioni. In realtà Int32 non può essere nullo e dunque il riferimento punta comunque ad una variabile Int32 = 0 che occupa comunque sempre 4 Byte.

>>2) Utilizzare il tipo Object potrebbe consentire il risparmio
>>di risorse.

>Stesso discorso. Se anche avessi un array di 1.567.641.600 byte (il tipo di dato più piccolo), occuperesti all'incirca 1.4 GiB (minimo)

Come scritto in precedenza, appunto la differenza tra 1GB (utilizzando il tipo di dato Byte) e 4 GB (riferito al tipo di dato Int32) diventa fondamentale.

L'idea nasce dal fatto che una variabile di tipo object impostata a null, non viene allocata in memoria e mantiene solo un riferimento alla classe che ne definisce i membri. E dunque presumo, che un riferimento nullo, e quindi una variabile oggetto null, occupi meno spazio in memoria rispetto ai 4 byte di una variabile Int32 in quanto non ancora istanziata.
Considerando che una parte delle dimensioni dell'array non verranno valorizzate, o verranno valorizzate successivamente, nel tempo, (importazioni dopo importazioni) pensavo fosse possibile fin da subito risparmiare spazio in fase di creazione di un'array multidimensionale, in quanto molte coordinate della matrice stessa avranno riferimento nullo.
Immagino però, che creando un'array di tipo object tramite il metodo Array.CreateIstance(GetType(Object), ....), si ottenga nell'immediato una matrice di valori nulli e dunque meno campiente (forse), ma assegnandovi successivamente valori di tipo integer immagino anche che la cosa possa incidere sulle prestazioni per una questione di cast.

Una variabile Object impostata a Null, quanta memoria occupa?

Ci sono forse delle soluzioni alternative per implementare questo tipo di analisi multidimensionale (che non sia utilizzare i cubi OLAP) che consenta di allocare meno risorse?

Vi sono davvero molto grato dell'attenzione e del supporto che mi state offrendo.

Buona serata. Enrico.

aiedail92 Profilo | Expert

993 messaggi | Data Invio: mer 9 feb 2011 - 22:05

>Una variabile Object impostata a Null, quanta memoria occupa?

In teoria, un object è un reference type, quindi dovrebbe occupare la dimensione di un puntatore, IntPtr.Size, che sarà 32 o 64 bit (4 o 8 byte) a seconda dell'architettura.

>Considerando che una parte delle dimensioni dell'array non verranno
>valorizzate, o verranno valorizzate successivamente, nel tempo,
>(importazioni dopo importazioni) pensavo fosse possibile fin
>da subito risparmiare spazio in fase di creazione di un'array
>multidimensionale, in quanto molte coordinate della matrice stessa
>avranno riferimento nullo.

Considerato ciò, una soluzione potrebbe essere di simulare l'array multidimensionale con un Dictionary, in modo da poter istanziare solo i valori che ti interessano.

L'idea di fondo è questa, volendo puoi costruirci attorno una classe per gestire il tutto:

// Simula un array n-dimensionale
int n = 5;
int sizes[n] = { 10, 20, 30, 40, 50 };

Dictionary<long, int> array = new Dictionary<long, int>();

int indexes[n] = { 6, 16, 3, 27, 43 };

long mapped_index = indexes[0];
for(int i = 1; i < n; ++i) {
    mapped_index = mapped_index * sizes[i] + indexes[i];
}

array[mapped_index] = 1;

L'ho scritto al volo in C# (è possibile che non compili), se ti serve in VB o ci sono altri problemi facci sapere

Luca

EnricoBSC Profilo | Newbie

12 messaggi | Data Invio: gio 10 mar 2011 - 00:15

Buona sera.
Mi scuso per il ritardo notevole nella risposta, ma ho preferito adottare la soluzione proposta , implementarla e testarla accuratamente per avere più elementi e dettagli da riportare in una mia eventuale risposta.
Ringrazio innanzitutto per il suggerimento, che mi ha dato un notevole aiuto e si è rivelato preziosissimo nel farci risparmiare risorse simulando un array multidimensionale attraverso l’uso del dictionary. Ho implementato una classe che eredita da DictionaryBase, dichiarata Serializable e che implementa la serializzazione custom in quanto contenente proprietà aggiuntive rispetto alla classe base dictionary già serializzabile nativamente.
La chiave del dictionary è di tipo Long come suggerito, mentre il valore è di tipo Object, in quanto potrebbe essere necessario gestire valori di tipo diverso rispetto a Int32 come riportato nell’esempio, magari anche oggetti strutturati, come istanze di classi che portino con se proprietà e metodi necessari per calcoli più complessi come la media, il calcolo percentuale, Min, Max, Deviazione Standard etc.
Questa soluzione soddisfa di per se gran parte delle nostre esigenze in termini di gestione della multidimensionalità dei dati.
Tuttavia potremmo trovarci nella condizione di gestire un numero talmente elevato di combinazioni (con risorse di memoria limitate e magari utilizzando al posto di valori Int32, istanze di oggetti) tali da generare OutOfMemoryException anche con l’ausilio del simulatore di array.
In questa ipotesi si renderebbe necessaria la soluzione di spezzare in qualche modo il dictionary in fase di serializzazione.
Per visualizzare i dati memorizzati nel dictionary in una normale DataTable, eseguo un ciclo su tutte le combinazioni dell’array convertendo le stesse (per esempio {5, 3, 24, 12, 54}, {6, 2, 19, 2, 43} etc.) in altrettanti valori long che rappresentano la chiave del dictionary dal quale estrarre il valore e associando successivamente gli indici stessi ai valori parlanti degli elementi dimensione (generalmente codici o stringhe di testo in altrettante array monodimensionali associate, ognuna delle quali elenca tutti gli elementi delle varie dimensioni).
Quando l’array degli indici (indexes) punta ad un valore che non è stato impostato e quindi inesistente nel dictionary, il valore long ricavato dall’algoritmo che mi avete suggerito risulterà giustamente essere una chiave non valida e il metodo TryGetValue() del dictionary restituirà false. In tal modo non viene aggiunto alcun record alla tabella e questo è un altro indubbio vantaggio.
Tuttavia se per esempio le combinazioni fossero 2.000.000 e gli elementi valorizzati nel dictionary 2.000 occorrerebbe eseguire un ciclo di 2.000.000 di iterazioni per recuperare 2000 valori.
Questo secondo voi potrebbe inficiare in qualche modo le prestazioni?
Ad ogni modo, eseguendo il ciclo direttamente sui 2000 elementi del dictionary e non sui 2.000.000 di combinazioni si porrebbe però il problema di disporre di un’eventuale reversibilità dell’algoritmo di conversione degli indici di un’array multidimensionale simulata in chiavi di tipo Long monodimensionali. Oppure si potrebbe sostituire il Long con una chiave stringa splittabile contenente essa stessa direttamente gli indici dell’array multidimensionale separati da virgole senza bisogno di implementare l’algoritmo per ottenere il long, ma con il probabile inconveniente di aumentare le risorse occupate visto che un Long occupa 8 Byte mentre la seguente stringa degli indici di esempio (“12,3,44,21,43,2,54,7”) ne occupa decisamente di più.
Caricando un dictionary troppo grande in memoria potrebbero verificarsi come dicevo delle out of memory exception. Supponiamo che il dictionary simuli 8 miliardi di combinazioni.
Spezzando il caricamento del dictionary in 8 riprese si potrebbe evitare il problema.
Preservando in questo caso l’utilizzo del Long come chiave, a fronte di uno spezzettamento del dictionary in 8 parti serializzate e salvate a DB, occorrerebbe implementare un ciclo su ogni troncone di 8 miliardi di iterazioni.
8 Miliardi di iterazioni * 8 fanno 64.000.000.000 di cicli.
Sostanzialmente su ogni spezzone del dictionary vengono calcolati ogni volta tutti gli 8 miliardi di combinazioni convertite poi tramite il solito algoritmo in valori long invocando successivamente il metodo TryGetValue del dictionary per verificare che il valore esista. Optando per la stringa come chiave del dictionary e supponendo che ogni troncone di array simulata serializzata contenga mediamente per esempio 5 milioni di elementi, si passerebbe da un ciclo di 64 miliardi di iterazioni (moltiplicate per il numero di iterazioni dell’algoritmo di conversione degli indici di array in chiavi di tipo long) a 5 * 8 = 40 milioni di iterazioni con l’uso della stringa come chiave del dictionary.
In sostanza usare la stringa come chiave del simulatore di array (dictionary) al posto del long nei casi in cui si debba gestire un numero elevatissimo di combinazioni tale da spezzare il dictionary stesso, potrebbe essere una soluzione accettabile? Oppure sarebbe meglio comunque utilizzare il long? Naturalmente se qualcuno avesse idee anche diverse in proposito sarebbero sicuramente molto gradite. Grazie per l’attenzione e mi scuso per essermi forse un po’ troppo dilungato.
Grazie. Enrico.

aiedail92 Profilo | Expert

993 messaggi | Data Invio: dom 13 mar 2011 - 01:30

Forse mi sono perso qualcosa, ma puoi iterare direttamente il contenuto del Dictionary anziché provare tutte le possibili combinazioni. Risalire agli indici che hanno generato la chiave è un'operazione abbastanza semplice:

// Simula un array n-dimensionale
int n = 5; int sizes[n] = { 10, 20, 30, 40, 50 };

Dictionary<long, int> array = ...; // Il tuo Dictionary

int indexes[n];
// Cicla tutti gli elementi nell'array simulato dal Dictionary
foreach(KeyValuePair<long, int> kv in array) {
    // Riconverte la chiave, long, all'insieme di indici che mappa
    int key = kv.Key;
    for(int i = n - 1; i >= 0; --i) {
        indexes[n] = key % sizes[n];
        key /= sizes[n];
    }
    // indexes contiene gli indici che generano la chiave corrente
}

(Di nuovo, l'ho scritto al volo senza provarlo, se ci sono problemi fammi sapere)

Luca

EnricoBSC Profilo | Newbie

12 messaggi | Data Invio: lun 14 mar 2011 - 11:14

Ciao.
Hai ragione.
Il reversing dell'algoritmo è molto più facile di quanto pensassi. Pensavo potesse essere anche più o in termini di cicli eseguiti.
Ho guradato il tuo codice.
Sicuro che non si debba aggiungere a

indexes[n] = key % sizes[n];
key /= sizes[n];

il seguente codice:

indexes[n] = key % sizes[n];
key -= indexes[n];
key /= sizes[n];

Comunque, a prescindere da quale dei due stralci di codice sia giusto il tuo aiuto è stato di nuovo davvero apprezzato.
Ti ringrazio ancora.
Enrico.

Ecco come potrebbe essere l'algoritmo di reversing con alcune modifiche:

int n = 5; int sizes[n] = { 10, 20, 30, 40, 50 };

Dictionary<long, int> array = ...; // Il tuo Dictionary

int indexes[n];
// Cicla tutti gli elementi nell'array simulato dal Dictionary
foreach(KeyValuePair<long, int> kv in array) {
// Riconverte la chiave, long, all'insieme di indici che mappa
int key = kv.Key;
for(int i = n - 1; i > 0; --i) {
indexes[i] = key % sizes[i];
key -= indexes[i];
key /= sizes[i];
}
indexes[0] = key;
// indexes contiene gli indici che generano la chiave corrente
}
Grazie.
Enrico.

aiedail92 Profilo | Expert

993 messaggi | Data Invio: lun 14 mar 2011 - 13:06

Anche il tuo codice è giusto, ma la sottrazione non è necessaria, in quanto la divisione fra numeri interi viene fatta arrotondando verso lo zero.

Esempio:

17 % 7 = 3
17 - 3 = 14
14 / 7 = 2  (resto 0)

Però:

17 % 7 = 3
17 / 7 = 2  (resto 3, va "perso")

Luca

EnricoBSC Profilo | Newbie

12 messaggi | Data Invio: lun 14 mar 2011 - 14:28

Ok. E' vero. Essendo l'indice della dimensione corrente sicuramente minore della dimensione stessa, toglierlo o meno, non cambia il risultato finale della divisione, che tronca le cifre decimali.
Allora tolgo la sottrazione key -= indexes[i] che appesantisce inutilmente il ciclo, anche se manterrei l'altra modifica, vale a dire quella di fermare il ciclo a "i > 0" e impostando dopo il ciclo stesso indexes[0] = key.
Quello di cui sotto dovrebbe essere il codice ottimizzato.
Di nuovo grazie, Enrico.

int n = 5; int sizes[n] = { 10, 20, 30, 40, 50 };

Dictionary<long, int> array = ...; // Il tuo Dictionary

int indexes[n];
// Cicla tutti gli elementi nell'array simulato dal Dictionary
foreach(KeyValuePair<long, int> kv in array) {
// Riconverte la chiave, long, all'insieme di indici che mappa
int key = kv.Key;
for(int i = n - 1; i > 0; --i) {
indexes[i] = key % sizes[i];
key /= sizes[i];
}
indexes[0] = key;
// indexes contiene gli indici che generano la chiave corrente
}

Torna su

Stanze Forum

Elenco Threads

Partecipa anche tu! Registrati!

Hai bisogno di aiuto ?
Perchè non ti registri subito?

Dopo esserti registrato potrai chiedere
aiuto sul nostro Forum oppure aiutare gli altri

Consulta le Stanze disponibili.

Registrati ora !