[c++] Suggerimento su disegno struttura dati

[sottovento]

Carissimi
il problema e' abbastanza semplice: mi arrivano dei dati identificati da un numero progressivo (il quale non parte da 1 ma da un numero arbitrario piuttosto grande). Per semplificare si puo' pensare ad una cosa del genere.

insert (3322551, dato1);
insert (3322552, dato2);
insert (3322553, dato3);
...

(ovviamente noi siamo "dentro" la insert )
I dati sono parecchi e vengono collezionati durante il processo di lavorazione di un prodotto.
Ogni tanto, verra' chiamata una funzione del tipo:

remove (332253);

che intimera' di rimuovere il dato.

Siccome queste funzioni sono all'interno del processo di lavorazione, devono essere scritte con cura, prestando attenzione alla loro velocita' di esecuzione ed ad un consumo ragionevole della memoria.

Al termine delle operazioni (dopo qualche giorno), si dovra' stampare la lista dei dati inseriti e non rimossi. Questa operazione non e' assolutamente critica essendo off-line e puo' essere fatta in tutta calma.

- La prima versione di questo software (in c++ sotto Visual Studio) era fatta usando una hash_map stl. Un mattone! Lentissima ed inutilizzabile

- La seconda versione ha visto la rimozione della hash_map con una semplicissima tabella hash fatta a mano, costruita come un vettore di puntatori ad elementi contenenti id+dato. L'indice del vettore e' calcolato semplicemente come id % MAX (MAX = dimensione vettore). A sua volta, il puntatore era una lista linkata UNIDIREZIONALE nella quale si inserivano gli elementi aventi lo stesso indice.
Questa nuova versione era decisamente un passo avanti ed e' risultata utilizzabile (ed e' utilizzata, in effetti).

- La terza versione la sto chiedendo a voi

Ritengo che si possano migliorare le prestazioni (velocita' in primis): visto il gran numero di inserimenti ho un sacco di collisioni e questo ovviamente incide parecchio sulle performance. Inoltre la soluzione in uso non trae vantaggio dal fatto che gli id sono progressivi, ed ho l'impressione che si possa usare questa caratteristica per incrementare le prestazioni.

Purtroppo le rimozioni dalla struttura non sembrano seguire una logica del genere, e necessitano di essere altrettanto veloci.

Domanda: si puo' pensare ad una struttura simile, che sia piu' veloce e non abbia un consumo eccessivo di memoria? (diciamo, paragonabile alla soluzione in uso?)

NOTA - non ci sono problemi legati al multithreading. Fortunatamente un solo thread si occupera' dell'intera gestione (dump finale a parte)

[shinya]

Non so se ti può aiutare, ma c'è un progettino di google che contiene diverse implementazioni di hash-map ottimizzate per spazio occupato oppure per velocità.

Lo trovi qui: http://code.google.com/p/google-sparsehash/

[sottovento]

Originariamente inviato da shinya

Non so se ti può aiutare, ma c'è un progettino di google che contiene diverse implementazioni di hash-map ottimizzate per spazio occupato oppure per velocità.

Lo trovi qui: http://code.google.com/p/google-sparsehash/

Un sacco di roba da leggere! Beh, ci provo. Cmq il nome mi fa arricciare il naso: "sparse". Io ho dei progressivi ed una "classica" funzione hash (i.e. id % MAX) che mi produrra' sicuramente una hash NON sparsa.
Ovviamente la colpa e' del sottoscritto, nel senso che per forza di cose le hash table, per dare buoni risultati, devono essere sparse.
Non posso dire nulla sulla funzione di rimozione, solo che si suppose che rimuova uniformemente. Ad ogni modo, la hash e' sempre piuttosto piena...

[shinya]

"The Google sparsehash package consists of two hashtable implementations: sparse, which is designed to be very space efficient, and dense, which is designed to be very time efficient. For each one, the package provides both a hash-map and a hash-set, to mirror the classes in the common STL implementation."

Probabilmente a te serve più la versione "densa"... quindi dense_hash_map/dense_hash_set.

EDIT: qui trovi un po' di test sulle performance per spazio/velocità tra le varie implementazioni: http://google-sparsehash.googlecode....rformance.html

[WarDuck]

Partiamo dal presupposto che le strutture dati hash sono le strutture aventi prestazioni in ordine di tempo pari a O(1), quindi molto veloci...

Non credo che in termini di velocità tu possa migliorare... nel senso che al massimo puoi fare O(1).

Eventuali problemi di degrado ce l'hai per via delle collisioni, ma questo dipende dal tuo insieme delle chiavi e dalla memoria che vuoi sacrificare.

Un miglioramento ce l'avresti usando al posto di liste, alberi binari (magari auto-bilancianti), così alla peggio andresti come O(log n) anziché O(n).

Comunque, il tuo insieme delle chiavi hai detto che parte da un numero grande...

Se questo numero è fissato in qualche modo e non varia (ad esempio un prefisso che è sempre lo stesso), si potrebbe pensare banalmente di fare una trasformazione lineare in maniera da mappare in questa maniera:

Y = X - OFFSET

ad esempio:

Y = 3322551 - OFFSET

Supponendo che l'offset sia 3322550 avresti:

Y = 3322551 - 3322550 = 1
Y = 3322552 - 3322550 = 2
Y = 3322553 - 3322550 = 3

Se il tuo offset è 3322000 ad esempio:

Y = 3322551 - 3322000 = 551
Y = 3322552 - 3322000 = 552
Y = 3322553 - 3322000 = 553

Quindi bisogna capire meglio come è fatto veramente il tuo insieme di chiavi.

[sottovento]

Originariamente inviato da shinya

"The Google sparsehash package consists of two hashtable implementations: sparse, which is designed to be very space efficient, and dense, which is designed to be very time efficient. For each one, the package provides both a hash-map and a hash-set, to mirror the classes in the common STL implementation."

Probabilmente a te serve più la versione "densa"... quindi dense_hash_map/dense_hash_set.

EDIT: qui trovi un po' di test sulle performance per spazio/velocità tra le varie implementazioni: http://google-sparsehash.googlecode....rformance.html

Faro' ovviamente le prove, ma saranno piuttosto difficili e c'e' il rischio che il risultato sia deludente. Non ci crederai, ma c'e' il rischio che la mia versione attuale sia piu' performante

Il motivo e' la mia stupida implementazione che va in accoppiata con l'implementazione di Microsoft CRT non troppo intelligente:
1 - l'ottimo software che hai proposto e' scritto per essere general purpose ed accetta chiavi di tutti i tipi, incluso le stringhe. Il software attuale e' molto piu' triviale ed accetta solo le chiavi intere, del tipo che servono;

2 - Il codice che hai proposto gira su piu' piattaforme. Quando serve della memoria, la richiede con una new(). Purtroppo la CRT (i.e. C run time) di Visual Studio la implementa chiamando una malloc() che chiama a catena varie funzioni, fino ad arrivare, alla fine, ad un codice del genere (puoi verificare, MS fornisce i sorgenti):

EnterCriticalSection(&cs);
<qui c'e' l'allocazione nella heap corrent>
LeaveCriticalSection(&cs);

Ne consegue che tutte le allocazioni sono sincronizzate!! Questo perche' VS tiene una lista delle allocazioni e ha bisogno che sia cosi'. Mi aspetto quindi che le prestazioni che sono state riportate siano quindi destinate a crollare miseramente durante la fase di produzione, soprattutto con tanti thread the creano un inferno di oggetti moscerini, secondo la "prassi" che la progettazione a oggetti incoraggia
Inoltre, per problemi legati ai processori Intel, EnterCriticalSection() triggerera' ovviamente lo switch del processore dalla modalita' user. (MSDN riporta questo problema con parole piu' belle in caso si voglia approfondire )
Ne e' testimone il Performance Monitor, che vede il numero di context switches salire alle stelle

Per questo motivo, nella mia implementazione stupida, ho preferito creare una heap separata (tramite le banali funzioni di win32) tutta mia, la quale non ha bisogno di nessuna sincronizzazione perche' vi fa accesso solo il mio thread.

A peggiorare le cose, nel processo di produzione i vari processi sono compilati in modalita' Debug a causa di alcuni tool di diagnostica.


Insomma: grazie del suggerimento, prometto che perdero' qualche ora a fare una prova sensata e non un benchmark generico... ma non di piu' di qualche ora

[sottovento]

Originariamente inviato da WarDuck

Partiamo dal presupposto che le strutture dati hash sono le strutture aventi prestazioni in ordine di tempo pari a O(1), quindi molto veloci...

Non credo che in termini di velocità tu possa migliorare... nel senso che al massimo puoi fare O(1).

Beh si, la teoria dice questo. Ma sono alla ricerca di un risultato pratico
Le hash sono strutture molto "pratiche" per inciso: in effetti sono O(1) in presenza di un numero trascurabile di collisioni, cioe' quando sono sparse, prendendo in prestito un termine dal calcolo matriciale.

Originariamente inviato da WarDuck

Eventuali problemi di degrado ce l'hai per via delle collisioni, ma questo dipende dal tuo insieme delle chiavi e dalla memoria che vuoi sacrificare.

Grossi problemi di degrado. La versione 2, come dicevo, e' utilizzabili ma sono pienamente convinto che si possa fare di meglio, e non solo perche' il cliente mi pagherebbe per questo

Originariamente inviato da WarDuck

Un miglioramento ce l'avresti usando al posto di liste, alberi binari (magari auto-bilancianti), così alla peggio andresti come O(log n) anziché O(n).

Well, l'id e' un numero che si incrementa continuamente ed e' accettabile pensare che non si arrivi al massimo intero disponibile. Quindi per il nostro problema lo possiamo pensare monotono crescente.
Per questo motivo, nel momento che ho una collisione, sono sicuro che il nuovo elemento ha un ID maggiore di tutti quelli gia' contenuti. Questo mi farebbe scartare la soluzione degli alberi binari, appenderei sempre a destra. A meno che di non fermarmi e bilanciare, ma... gosh! dovrei continuamente bilanciare!

Non si riesce, invece, a sfruttare questa caratteristica di monotonicita'? Sono convinto che ci sia una soluzione ma sono troppo stupido per arrivarci.

Originariamente inviato da WarDuck

Comunque, il tuo insieme delle chiavi hai detto che parte da un numero grande...

Se questo numero è fissato in qualche modo e non varia (ad esempio un prefisso che è sempre lo stesso), si potrebbe pensare banalmente di fare una trasformazione lineare in maniera da mappare in questa maniera:

Y = X - OFFSET

ad esempio:

Y = 3322551 - OFFSET

Supponendo che l'offset sia 3322550 avresti:

Y = 3322551 - 3322550 = 1
Y = 3322552 - 3322550 = 2
Y = 3322553 - 3322550 = 3

Se il tuo offset è 3322000 ad esempio:

Y = 3322551 - 3322000 = 551
Y = 3322552 - 3322000 = 552
Y = 3322553 - 3322000 = 553

Quindi bisogna capire meglio come è fatto veramente il tuo insieme di chiavi.

Mmmm, non sono d'accordo un'altra volta. Dopo questa operazione dovresti comunque ricorrere al modulo per poter esser sicuro di stare nell'intervallo dato. L'operazione di modulo rende automaticamente vano l'effetto di somma/sottrazione di un offset.

Domanda: nel sai qualcosa su tabelle hash che si espandono automaticamente?


Dimenticavo: grazie a te e a shinya. Sto lavorando da solo da un bel po' e mi serviva proprio un confronto per chiarire le idee, indipendentemente dal fatto che si possa arrivare davvero ad una soluzione piu' performante o meno....

[WarDuck]

Originariamente inviato da sottovento

Well, l'id e' un numero che si incrementa continuamente ed e' accettabile pensare che non si arrivi al massimo intero disponibile. Quindi per il nostro problema lo possiamo pensare monotono crescente.
Per questo motivo, nel momento che ho una collisione, sono sicuro che il nuovo elemento ha un ID maggiore di tutti quelli gia' contenuti. Questo mi farebbe scartare la soluzione degli alberi binari, appenderei sempre a destra. A meno che di non fermarmi e bilanciare, ma... gosh! dovrei continuamente bilanciare!

Non si riesce, invece, a sfruttare questa caratteristica di monotonicita'? Sono convinto che ci sia una soluzione ma sono troppo stupido per arrivarci.

Mmm hai ragione non avevo capito bene la situazione... quindi se ne può dedurre che i numeri nella lista saranno comunque ordinati, giusto? A questo punto ti basterebbe usare una ricerca binaria sulla lista (con un array ridimensionabile credo venga più comodo), piuttosto che una ricerca lineare (non so, adesso come fai?).

Non so se meglio di così si possa fare, ci devo pensare a fondo, queste sono le prime cose che mi sono venute in mente .

Originariamente inviato da sottovento

Mmmm, non sono d'accordo un'altra volta. Dopo questa operazione dovresti comunque ricorrere al modulo per poter esser sicuro di stare nell'intervallo dato. L'operazione di modulo rende automaticamente vano l'effetto di somma/sottrazione di un offset.

Domanda: nel sai qualcosa su tabelle hash che si espandono automaticamente?

Bisogna vedere quanto vuoi fare grande la tabella...

Ad esempio mettiamo tu voglia mappare i caratteri ASCII da 97 a 126, dovresti creare un array di 127 posti per fare l'accesso diretto, sprecando i primi 96 slot.

Usando l'offset e sapendo che il minimo è 97, puoi sottrarre a tutti i numeri 97, ottenendo così un intervallo da 0 a 30.

Così facendo puoi creare un array di 31 posti (quelli che realmente ti servono), anziché 127.

Il vantaggio è che puoi così facendo mettere molte più cose nello stesso spazio, riducendo il numero di collisioni.

Sulle tabelle hash che si espandono in automatico non ne so molto (anche se immagino che lo scopo sia sempre lo stesso, ridurre il quantitativo di memoria usata).

Originariamente inviato da sottovento

Dimenticavo: grazie a te e a shinya. Sto lavorando da solo da un bel po' e mi serviva proprio un confronto per chiarire le idee, indipendentemente dal fatto che si possa arrivare davvero ad una soluzione piu' performante o meno....

De nada, è sempre piacevole trovarsi davanti a "sfide", piccole o grandi che siano .

[sottovento]

Ciao, Warduck

Originariamente inviato da WarDuck

Mmm hai ragione non avevo capito bene la situazione... quindi se ne può dedurre che i numeri nella lista saranno comunque ordinati, giusto? A questo punto ti basterebbe usare una ricerca binaria sulla lista (con un array ridimensionabile credo venga più comodo), piuttosto che una ricerca lineare (non so, adesso come fai?).

Non so se meglio di così si possa fare, ci devo pensare a fondo, queste sono le prime cose che mi sono venute in mente .

Attualmente faccio cosi (molto semplificato): mi arriva la coppia <id, dato>, quindi calcolo l'indice nella hash come
index = id % DIMENSIONE_HASH;
e vado a vedere se nella mia hash (che e' un vettore di puntatori) la casella puntata e' vuota (cioe' NULL).
Se e' vuota, inserisco l'elemento. L'elemento e' inserito tramite una struttura del genere:

struct Elemento
{
    int id;
    int dato; // Nella realta' non e' un int ma mi piace semplificare :D
    Elemento *next;
    Elemento *prev;   // mi sono sbagliato, qualche post sopra: la lista e' bidirezionale
};

Inserisco quindi un Elemento in hash.
Se c'e' gia' un elemento, faccio buon uso della lista linkata.


Ora che ti scrivo... mi e' venuta un'idea. Cosa ne pensi se modificassi la struttura cosi:

struct Elemento
{
    int id;
    int dato; // Nella realta' non e' un int ma mi piace semplificare :D
    Elemento **extended_hash;
};

Si puo' benissimo supporre che gli id siano Naturali (i.e. numeri interi maggiori di zero).

L'idea e' questa: arriva il primo elemento e, calcolando
index = id % DIMENSIONE_HASH;
vada a finire nella casella 3, ovviamente vuota. Alloco Elemento ed inserisco il tutto all'indice 3, con extended_hash pari a NULL.

Arriva il secondo elemento, che guarda caso finisce ancora in 3. Ora 3 e' != NULL, sono in collisione. Pertanto controllo extended_hash e, trovandolo == NULL decido di allocarlo in modo che possa contenere EXTENDED_HASH elementi. Questa e' la mia estensione della tabella hash

A questo punto, calcolo
secondo_indice = (id / DIMENSIONE_HASH) % EXTENDED_HASH
e troverei l'indice in cui inserire l'elemento.

Naturalmente sarebbe piuttosto semplice fare ricerche su questa hash "estesa". La cosa e' ovviamente reiterabile (sulla falsariga degli i-node del file system di Unix). Nel livello successivo
terzo_indice = ((id/DIMENSIONE_HASH)/EXTENDED_HASH) % EXTENDED_HASH
e cosi' via

Resta la cancellazione: potrei evitare di deallocare la memoria, semplicemente potrei porre id=-1, cosi' saprei che posso riutilizzare la casella rimasta libera. Ovviamente il fatto di mettere -1 nell'id non deve invalidare il contenuto dell'estensione.

Cosa ne pensi? Non mi sembra male, ma non sfrutto ancora la monotonicita', che in questa soluzione potrebbe addirittura peggiorarmi l'occupazione di memoria. A livello di velocita' pero' mi sembra migliore della soluzione attuale...

[WarDuck]

La tua soluzione non è male, ma vorrei capire come scegli DIMENSIONE_HASH e EXTENDED_HASH, rispetto al tuo insieme di chiavi.

Però è effettivamente una complicazione IMHO.

Infatti per come la vedo io arriverai sempre ad un punto in cui ci saranno collisioni.

Io farei così, risparmiando un po' di memoria sul singolo elemento (non memorizzando la key nello stesso) e sfruttando il fatto che i record siano ordinati per poter aggiungerli all'infinito* così:

* infinito = fino a quando la RAM lo consente.

Elem** array = new Elem*[DIM];

OFFSET = key_minima

unsigned count = key_minima - OFFSET; 

void Add(Elem** array, const Elem* el)
{
    assert (array && *array && el);

    if (count == DIM)
        // espandi array e imposta nuovamente DIM
    
    array[count] = el;

    count++;
}

Elem* Search(unsigned key)
{
    // manipola key
    key -= OFFSET;

    assert (key < DIM);
    return array[key];
}

Ovviamente è un ipotesi che da per scontato una serie di cose:

a) parti da una key_minima fissata
b) ogni volta che aggiungi un elemento è un nuovo elemento (quindi la key deve incrementare di 1)
c) Elem è una struttura non molto grande in bytes

Supponendo che Elem sia di 32 bytes e che vuoi memorizzare 4 milioni di elementi, a spanne:

Memoria costante = 4 milioni per 4 bytes dei puntatori (supponendo i 32bit) = 8 MB solo per la struttura

Memoria per k elementi = 32*k bytes

TOTALE = 8MB + 32k
A struttura piena, quindi k = 4 milioni avresti 128M, quindi:

128M + 8M = 136M

Con 10 milioni di record avresti:

40M (struttura) + 320M (se piena)

Con 100 milioni di record:

400M (struttura) + 3200M (se piena)

Questo ti fa capire due cose:

1) si può fare una stima accurata di prestazioni e ram solo se conosci il caso specifico
2) ai database piace tanto la RAM .

Con questo sistema puoi memorizzare a dire tanto 100 milioni di record da 32bytes ciascuno in un PC moderno (con 4gb di ram).

I vantaggi di questo sistema sono:
a) semplice da implementare
b) veloce in fase di esecuzione (a parte le reallocation, ma puoi anche fissare una struttura bella grossa dall'inizio)
c) assenza totale di collisioni (cosa IMHO da non sottovalutare)

Sta a te capire quale sia il compromesso ideale, per questo all'inizio ti ho chiesto: quanta ram sei disposto a sacrificare? .

Notare che la risposta a questa domanda è DIMENSIONE_HASH .

[marco.r]

Se le rimozioni sono molto minori delle inserzioni sono anche io convinto che la soluzione piu' semplice e performante sia quella dell'array su cui effettuare ricerca binaria.
E' vero che una ricerca in una tabella hash e' O(1), ma la costante sottostante non e' banale. La ricerca binaria sara' log(n), ma quel n e' alla fine limitato per cui alla fine, quando si tratta di problemi pratici, bisogna sempre valutare... non tutti hanno a che fare con svalangate di dati come google.

Nel caso dell'array hai il problema che devi riservare del posto per "marcare" una certa entri come cancellata, ma in generale l'array e' una struttura dati molto compatta per cui la differenza potrebbe non farsi sentire.
Inoltre, se tu hai a priori un bound sul numero massimo di elementi potresti allocare la dimensione massima a priori ed evitare ulteriori allocazioni.
O in alternativa mappi della memoria da disco, e lasci al sistema operativo il compito di smazzarsi la cosa

[marco.r]

Altra questione: il problema e' il tempo complessivo di esecuzione, o quello delle singole chiamate che non deve essere maggiore di un certo valore ?

[sottovento]

Originariamente inviato da marco.r

Se le rimozioni sono molto minori delle inserzioni sono anche io convinto che la soluzione piu' semplice e performante sia quella dell'array su cui effettuare ricerca binaria.
E' vero che una ricerca in una tabella hash e' O(1), ma la costante sottostante non e' banale. La ricerca binaria sara' log(n), ma quel n e' alla fine limitato per cui alla fine, quando si tratta di problemi pratici, bisogna sempre valutare... non tutti hanno a che fare con svalangate di dati come google.

Nel caso dell'array hai il problema che devi riservare del posto per "marcare" una certa entri come cancellata, ma in generale l'array e' una struttura dati molto compatta per cui la differenza potrebbe non farsi sentire.
Inoltre, se tu hai a priori un bound sul numero massimo di elementi potresti allocare la dimensione massima a priori ed evitare ulteriori allocazioni.
O in alternativa mappi della memoria da disco, e lasci al sistema operativo il compito di smazzarsi la cosa

Purtroppo le rimozioni sono frequenti. Diciamo che le varie lavorazioni producono un sacco di dati, che devono essere memorizzati. Dopo di che, se le lavorazioni sono andate a buon fine, viene richiesta la rimozione.
Dunque, quando tutto va bene la struttura dovrebbe riempirsi parecchio e poi svuotarsi completamente. Non e' proprio cosi' per via del grande parallelismo delle lavorazioni, ma in linea di principio e' cosi'.

Per questo motivo ho un po' paura ad usare una soluzione "array"....

[sottovento]

Originariamente inviato da marco.r

Altra questione: il problema e' il tempo complessivo di esecuzione, o quello delle singole chiamate che non deve essere maggiore di un certo valore ?

Questa e' una domanda intelligente: si parla di tempo sulle singole chiamate

[sottovento]

Originariamente inviato da WarDuck

La tua soluzione non è male, ma vorrei capire come scegli DIMENSIONE_HASH e EXTENDED_HASH, rispetto al tuo insieme di chiavi.

Si, lo farei in base all' "esperienza", facendo girare il sistema in un ambiente di simulazione

Originariamente inviato da WarDuck

Però è effettivamente una complicazione IMHO.

Hai ragione, ma sarebbe solo una complicazione per lo sviluppatore (i.e. mi servirebbe piu' tempo per mettere a punto il codice). Runtime dovrebbe funzionare.
C'ho pensato, e questo "coincide" con la soluzione che avevi proposto prima: tutto sommato, non sto creando un albero? Certamente non un albero binario, ma un albero con diversi rami, i quali sono selezionati tramite una "chiave" hash. Un albero HASH!
Ora mi manca di creare il "perseghin" (un albero mitico che invece delle foglie ha banconote - l'espressione e' dialettale) e poi mi posso ritirare

Originariamente inviato da WarDuck

Infatti per come la vedo io arriverai sempre ad un punto in cui ci saranno collisioni.

Eh, purtroppo si. Quello che conto e' di creare questo "hash tree". Sto ripensando alla tua soluzione dell'albero binario, e mi rendo conto di essere tardo. Scusa se arrivo sempre con parecchie ore di ritardo....

Originariamente inviato da WarDuck

Elem** array = new Elem*[DIM];

OFFSET = key_minima

unsigned count = key_minima - OFFSET; 

void Add(Elem** array, const Elem* el)
{
    assert (array && *array && el);

    if (count == DIM)
        // espandi array e imposta nuovamente DIM
    
    array[count] = el;

    count++;
}

Elem* Search(unsigned key)
{
    // manipola key
    key -= OFFSET;

    assert (key < DIM);
    return array[key];
}

Ovviamente è un ipotesi che da per scontato una serie di cose:

a) parti da una key_minima fissata
b) ogni volta che aggiungi un elemento è un nuovo elemento (quindi la key deve incrementare di 1)
c) Elem è una struttura non molto grande in bytes

Supponendo che Elem sia di 32 bytes e che vuoi memorizzare 4 milioni di elementi, a spanne:

Memoria costante = 4 milioni per 4 bytes dei puntatori (supponendo i 32bit) = 8 MB solo per la struttura

Memoria per k elementi = 32*k bytes

TOTALE = 8MB + 32k
A struttura piena, quindi k = 4 milioni avresti 128M, quindi:

128M + 8M = 136M

Con 10 milioni di record avresti:

40M (struttura) + 320M (se piena)

Con 100 milioni di record:

400M (struttura) + 3200M (se piena)

Questo ti fa capire due cose:

1) si può fare una stima accurata di prestazioni e ram solo se conosci il caso specifico
2) ai database piace tanto la RAM .

Con questo sistema puoi memorizzare a dire tanto 100 milioni di record da 32bytes ciascuno in un PC moderno (con 4gb di ram).

I vantaggi di questo sistema sono:
a) semplice da implementare
b) veloce in fase di esecuzione (a parte le reallocation, ma puoi anche fissare una struttura bella grossa dall'inizio)
c) assenza totale di collisioni (cosa IMHO da non sottovalutare)

Sta a te capire quale sia il compromesso ideale, per questo all'inizio ti ho chiesto: quanta ram sei disposto a sacrificare? .

Notare che la risposta a questa domanda è DIMENSIONE_HASH .

Capisco la tua soluzione. Per quanto riguarda la chiave minima potrei trovarla facilmente (semplicemente memorizzo la prima chiamata).
La prima obiezione che mi viene in mente e' quella delle cancellazioni. Fammici pensare


Grazie ancora a tutti

[marco.r]

Originariamente inviato da sottovento

Questa e' una domanda intelligente: si parla di tempo sulle singole chiamate

Allora intanto come prima cosa, tieni presente che alcune inserzioni o cancellazioni occuperanno piu' tempo di altre (vuoi perche' devono allocare memoria, vuoi perche' alcune operazioni hanno costo ammortizzato).
Puo' avere senso spezzare l'elaborazione in due thread. Quello principale spedisce tramite una coda di messaggi i "comandi" al worker, che effettua gli inserimenti man mano. In questo modo una operazione piu' costosa ogni tanto non va ad inficiare la durata delle singole chiamate. Ovviamente questo comporta un piccolo costo in termini di prestazioni (sotto linux abbastanza trascurabile, non so sotto windows), e comunque il tempo complessivo di elaborazione deve essere sufficiente, altrimenti non fai altro che riempire la coda.

[marco.r]

Originariamente inviato da sottovento

Purtroppo le rimozioni sono frequenti. Diciamo che le varie lavorazioni producono un sacco di dati, che devono essere memorizzati. Dopo di che, se le lavorazioni sono andate a buon fine, viene richiesta la rimozione.
Dunque, quando tutto va bene la struttura dovrebbe riempirsi parecchio e poi svuotarsi completamente. Non e' proprio cosi' per via del grande parallelismo delle lavorazioni, ma in linea di principio e' cosi'.

Per questo motivo ho un po' paura ad usare una soluzione "array"....

Ho capito, in tal caso sarebbe un problema.
Tieni presente pero' che e' un "peccato" utilizzare una funzione di hash quando hai un indice che cresce monotonicamente.

Si potrebbe forse fare una cosa che sia una via di mezzo tra le due soluzioni.

Tu immagina invece che usare

index = id % DIMENSIONE_HASH

usi

index = (id - first_id)/BUCKET_SIZE; // BUCKET_SIZE potrebbe essere 1000

In altri termini vado a salvare i dati in "buckets" su un vettore che man mano incremento

Quindi (per comodita' suppondo che il primo indice sia zero, ma e' una questione di offset, come diceva warduck), tu potresti tenere una struttura tipo

vector< vector< pair<int,Data> > > storage;

void insert( int id, Data value )
{
    index = (id - first_id)/BUCKET_SIZE; // BUCKET_SIZE potrebbe essere 1000
    if (storage.size() <= index )
    {
        storage.push_back( vector<pair<int,Data> >() );
        storage.back().reserve(BUCKET_SIZE);

    }
    storage[i].push_back(make_pair(index,value)); 
}

bool cmp( const pair<int,Data>& x, const pair<int,Data>& y)
{
    return x.first < y.first;
}



void delete_value( int id )
{
    index = (id - first_id)/BUCKET_SIZE;
    vector<pair<int,Data> >::iterator i = binary_search( storage[i].begin(), storage[i].end(), cmp );
    storage[i].erase(i);

}

L'idea e' che l'inserimento in questo modo costa veramente poco (in pratica la copia del dato), a parte l'espansione dell'array principale (ammortizzabile) e puoi sfruttare il tempo risparmiato per le operazioni piu' complesse (la cancellazione).
La dimensione dei bucket dovresti tararla in base alle tue esigenze. In pratica bucket piu' grande vuol dire inserimento piu' veloce (devi espandere meno il vettore principale) e meno memoria consumata. Bucket piu' piccolo invece rimozioni piu' veloci.
Nell'esempio ho implementato il singolo bucket come vettore ordinato, dove quindi la cancellazione richiede lo shift dei dati. Piu' piccola la dimensione, meno costoso e' questo. Puoi pensare ad implementazioni alternative che non siano vettori.
tieni presente pero' che questa soluzione ha il vantaggio che effettua un numero veramente limitato di chiamate di sistema (una per ridimensionare ogni tanto il vettore principale, e una per impostare la dimensione massima del bucket) per cui in realta' non dovrebbe essere malvagia rispetto alle alternative.

Certo dipende dai numeri del problema, dal numero totale di inserimenti, dal numero totale di rimozioni e quindi in definitiva quanti elementi ti aspetti che restino nella coda.

[marco.r]

ops, il codice che ho scritto non compilera' mai... buttato giu' troppo a getto, comunque e' abbastanza vicino a quel che avevo in mente

[sottovento]

Originariamente inviato da marco.r

ops, il codice che ho scritto non compilera' mai... buttato giu' troppo a getto, comunque e' abbastanza vicino a quel che avevo in mente

Non ha importanza, l'importante e' aver capito la tua soluzione.
Ad ogni modo mi sembra che stiamo "convergendo" verso un certo tipo di soluzioni. Tutto sommato l'idea del Bucket mi ricorda qualcosa simile ad una hash

Penso che tutte queste soluzioni siano sicuramente migliori di quella attualmente implementata, e che si possa avere un deciso miglioramento delle prestazioni. Ad esser sincero, eviterei l'uso di ulteriori thread perche' ritengo che non ci sia un vero beneficio (gli inserimenti e le cancellazioni, in realta', sono ben poco lavoro. E' la loro quantita' che li fa diventare critici).

Avro' bisogno di un bel po' di tempo per fare le prove come si deve. Vi terro' aggiornati e grazie ancora.

Nel frattempo, se avete altre idee, saro' lietissimo di vagliarle

[Andrea993]

Hai pensato di usare un b-albero (b-tree) siccome credo che ci saranno tantissimi elementi da numerare, mi sembra stupido tenere tutto il database in memoria.

Prova a studiarti i b-alberi, trovi anche librerie gia pronte su internet, nel tuo caso dovrebbe essere la soluzione migliore.

guarda su wiki