Newsgroup: it.comp.lang.c++
Titolo: Massima grandezza vector

Salve a tutti,
ho un dubbio che mi assilla: quanti elementi può contenere un
vector<T> ? C'è un qualche limite "strutturale" alla sua grandezza
(tralasciando la quantità disponibile di memoria fisica-virtuale)?
Grazie e ciao
InSa
-- 
++ Powered by Sid ++

 (tralasciando la quantità disponibile di memoria fisica-virtuale)?
Non vedo perché dovrebbe esserci un limite. Se ci fosse, userei 
ovviamente una mia classe.
Comunque aspettiamo la conferma...
Kiuhnm

 (tralasciando la quantità disponibile di memoria fisica-virtuale)?
credo che la funzione membro max_size() restituisca il valore a cui ti 
riferisci.
-- 
"E' solo dopo aver perso tutto che siamo liberi di fare qualsiasi cosa."
"buuuhhhhhhhhhhrrrrrrr"

 ti riferisci.
Se compilo (con gli oppurtuni include, namespace, etc):
vector<int> a;
cout<<a.max_size();
ottengo che al massimo posso avere un vector con 1073741823 elementi. A
parte una domanda "filosofica" (perchè non posso avere infiniti elementi
all'inteno di un vector?), c'è un qualche altro contenitore che mi
permette di avere infiniti elementi al suo interno?


 all'inteno di un vector?), c'è un qualche altro contenitore che mi
Avevi detto "a parte la memoria fisica/virtuale".
Se stai usando un modello flat (cioè non segmentato) e usi un 
indirizzamento a 32 bit, mi spieghi come puoi accedere a più di 2^32 
byte? Se ogni elemento è di almeno 4 byte, allora il numero massimo di 
elementi è 2^30-1 (lo 0 è ritenuto invalido).
Allora quel limite è un non-limite. Su IA64 il valore massimo sarà 2^62 
o 2^61.
L'unico modo è quello di emulare la segmentazione cioè di appoggiarti a 
un file. Con le API di Win32 puoi mappare un file in memoria e usarlo 
come parte di ram virtuale. Potresti scrivere una tua classe vector che 
faccia questo automaticamente, oppure puoi creare una lista o un array 
di vector.
Secondo me ti preoccupi troppo: lo sai quanti sono 2^30-1 elementi???
Kiuhnm

 Secondo me ti preoccupi troppo: lo sai quanti sono 2^30-1 elementi???
Si, 1.073.741.823 elementi, ovvero la capacità massima di un vector ;)
Il vettore dovrebbe essere riempito di elementi presi da un db, vediamo
se basta.
Grazie e ciao.


 permette di avere infiniti elementi al suo interno?
Tutti i computer si basano su concetto che il processore elabora degli 
indirizzi di memoria.
Gli indirizzi di memoria sono memorizzati in registri costituiti da 
sequenze finite di bit.
Per esempio, un processore a 32-bit indirizza la memoria con numeri 
compresi tra 0 e 2^32-1.
La memoria indirizzabile da un processo e' ovviamente non maggiore della 
memoria indirizzabile dal processore su cui gira il processo.
La memoria allocabile da una struttura dati e' ovviamente non maggiore 
della memoria indirizzabile dal processo che gestisce tale struttura dati.
Pertanto tutte le strutture dati sono finite, e la struttura vector non 
e' limitata se non dall'architettura del computer.
Tutto questo finche' si parla di strutture dati in memoria principale 
(come sono i contenitori).
Se invece si parla di memoria secondaria, o memoria di massa, allora i 
limiti si spostano, ma anche la memoria secondaria e' limitata.
Per esempio, per poter recuperare un dato sulla memoria secondaria 
devono poterlo indirizzare, e l'indirizzo deve stare in memoria principale.
Se la memoria principale e' inferiore a 2^32 byte * 8 bit/byte = 2^35 
bit, non posso indirizzare piu' di 2^(2^35) posizioni, che espresso come 
numero decimale avrebbe circa 10 miliardi di cifre.
Ma d'altra parte, non ci sono cosi' tante particelle elementari 
nell'universo conosciuto.
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 nell'universo conosciuto.
Non è detto che l'indirizzo debba essere contenuto interamente nella ram 
e comunicato tutto in una volta (anzi, è improbabile).
Kiuhnm

 e comunicato tutto in una volta (anzi, è improbabile).
In ogni caso il tuo computer a 32bit non sara` mai in grado di gestire 
un'applicazione che, seppure in swap, indirizzi piu` di 4gb (e 4gb se li 
ciuccia il tuo vector da 2^30 elementi :) ).
Quindi se devi fare un'applicazione che legga da un database 1 miliardo 
di record (ma anche 100 milioni per dire) valuta SERIAMENTE di passare 
ad un'architettura a 64bit o inizia a fare i salti mortali a creare 
layer intermedi per gestire la cosa.
Ciao,
  Gabry

 nell'universo conosciuto.
Scusa la digressione, ma questo argomento, per quanto popolare, non ha
molto senso. I problemi complessi nel nostro campo riguardano in genere
non tanto l'enumerazione di un insieme di entita', quanto gli stati che
assumono. Il numero di particelle che puoi trattare e' dell'ordine di
un logaritmo dell'insieme degli stati, ovvero un numero non poi cosi'
alto.
Ciao,
Nicola

 ciuccia il tuo vector da 2^30 elementi :) ).
No, non è vero. Posso benissimo usare ptr da 64 bit e, in generale, di n 
bit senza problemi. Il problema è l'efficienza, ma il nostro discorso 
era teorico. In C++ si potrebbe anche fare in modo abbastanza 
trasparente, probabilmente.
Tu parli di 2^n mentre io e Carlo parlavamo già di 2^(2^n). La mia 
obiezione era che si può andare addirittura oltre, anche se in effetti 
ci sarebbero ancora più problemi pratici, ma siamo già nell'assurdo.
Kiuhnm

 alto.
A dire il vero, non conosco metodi per costruire hard disk logaritmici 
cioè tali che la superficie del disco sia il logaritmo della quantità di 
dati contenuti. Magari...
Kiuhnm


Proprio per questo la RAM, la memoria di massa, la potenza di calcolo
non saranno mai abbastanza.
Ciao,
Nicola

 non saranno mai abbastanza.
Continuo a non capire la critica che hai mosso a Carlo. Ha semplicemente 
dato un limite inferiore al numero massimo di locazioni indirizzabili. 
Ogni locazione contiene ovviamente dati. Da dove salterebbe fuori il 
logaritmo in questo discorso? Se le locazioni sono n, l'hard disk sarà 
probabilmente grande kn, non klogn.
Kiuhnm

 probabilmente grande kn, non klogn.
Adesso ho capito cosa volevi dire.
Qui non consideravo la quantità d'informazioni effettivamente contenute, 
ma il numero di locazioni fisiche presenti nell'hard disk. E' chiaro che 
un avanzamento tecnologico renderà possibile rappresentare la stessa 
quantità di dati usando sempre meno particelle. Addirittura si 
potrebbero usare i quark...
Kiuhnm


Io intendevo criticare un aspetto collaterale dell'intervento di Carlo.
Come ho gia' sentito o letto altre volte da altri, Carlo si e' riferito
al numero di particelle elementari dell'universo come termine di
raffronto per l'interesse pratico di poter rappresentare numeri molto
grandi.
La mia obiezione consiste nell'osservazione che i problemi "difficili"
dell'informatica di solito non sono legati all enumerazione dei dati
quanto alla loro combinazione. Ad esempio il numero delle particelle
elementari e' inferiore a 64! (fattoriale, non esclamativo :-)
Ciao,
Nicola

 elementari e' inferiore a 64! (fattoriale, non esclamativo :-)
Definiscimi "essere legato all'enumerazione dei dati" ed "essere legato 
alla combinazione dei dati".
Kiuhnm

Nicola Musatti wrote:

Infatti, non intendevo sostenere che la principale limitazione alla 
risoluzione dei problemi stia nella memoria.
Intendevo solo rispondere alla domanda: "c'è un qualche contenitore che 
mi permette di avere infiniti elementi al suo interno?"
E sostenevo che non e' pensabile un computer digitale reale con una 
memoria "infinita", anche se ne e' pensabile uno con una memoria piu' 
grande dell'immaginazione di molte persone.


 (tralasciando la quantità disponibile di memoria fisica-virtuale)?
Dovrebbe dipendere dall'implementazione nella libreria standard, quindi 
potrebbe non essere uguale per tutti i compilatori. Un possibile limite 
  che mi viene in mente è la dimensione dei puntatori nella macchina: 
per una CPU che usa puntatori a 32 bit non sarei sorpreso di scoprire 
che il limite per i vector<T> sia circa di 2^32 elementi (a prescindere, 
come hai detto tu, dalle considerazioni di memoria disponibile). Non 
credo che un "vector", internamente, sia solo un semplice array.

 ci sarebbero ancora più problemi pratici, ma siamo già nell'assurdo.
Mah, mah, state ancora parlando di limiti imposti dalla memoria e 
dall'architettura, mentre il nostro InSa parlava di "prescindere" da 
limiti fisici...
Appropo, la cosa è un esercizio teorico piuttosto interessante: 
progettare una struttura che si comporti come un array e che possa 
accogliere non "soltanto" un numero molto grande di elementi ma proprio 
"infiniti" elementi. Al posto di un normale tipo predefinito come indice 
dovremmo usare numeri rappresentati come una stringa (di caratteri 
oppure una stringa binaria di bytes, in linea di principio è la stessa 
cosa). Come implementazione si dovrebbe usare un albero di qualche 
genere, forse un B-albero, oppure un qualche tipo di lista 
"multilivello"... lista di liste, o magari liste di alberi di liste ecc...
Volendo complicare ancora le cose, ci si potrebbe chiedere se e in che 
modo una struttura simile possa garantire un tempo di accesso limitato 
superiormente (lasciamo perdere costante) per qualunque elemento della 
struttura stessa...

 "infiniti" elementi. Al posto di un normale tipo predefinito come indice 
Non è difficile, solo poco efficiente.
Kiuhnm

se basta.
Perche' mai vorresti leggere una milardata di elementi da un DB e
tenerli in un vector ?
Di sicuro l'accesso ai dati su disco tramite DB e' molto piu' veloce
che tramite swap...
Per curiosita', e' solo un "esperimento" o e' qualcosa che ti serve sul
serio ?
Se hai bisogno di avere tutti i dati in memoria contemporaneamente per
qualche elaborazione particolarmente complicata e gli accessi via DB
sono troppo lenti puoi considerare di distribuire i dati tra un certo
numero di macchine in rete (magari collegate via switch gigabit/s).
Puoi anche "virtualizzare" l'accesso in rete dietro una classe che
determina la macchina a cui chiedere il dato dall indice e comunica con
le altre in maniera trasparente.
(Mi capita spesso di lavorare con simili ordini di grandezza, ma di
solito basta considerare pochi record alla volta e non tutti insieme)
Saluti,
Fabio

 dovremmo usare numeri rappresentati come una stringa
Oppure numeri di qualche libreria che offre interi di dimensione
arbitraria. 
-- 
Uccidete i filosofi e tenetevi riso e bacchette per voi.

 Non credo che un "vector", internamente, sia solo un semplice array.
Si che lo e', sostanzialmente per definizione.
Ciao,
Nicola

 solito basta considerare pochi record alla volta e non tutti insieme)
In effetti considererei un record per volta, ma il tempo di accesso al
db (e di modifica) imho è troppo alto.
Ora però ho un altro problema: il salvataggio di tale vector.
#define _OT_
Tale vector è un vector<mpz_t> dove mpz_t è una classe definita in GMP
(
http://snipurl.com/mzgf
) e serve per gestire grandi numeri interi
(_dovrebbe_ essere implementata come array di interi). Il "salvataggio"
di tale vector io vorrei farlo su un db mysql tramite un campo blob (uno
per ogni elemento del vector), ma non riesco a capire come fare. Il
problema l'ho anche postato qui 
http://snipurl.com/mzgi
 , ma devo ancora
ricevere una risposta.
Il problema principalmente è "interfacciare" una libreria matematica
con un db, non importa quale precisa libreria e quale preciso db. (Se
mi dite che la libreria matematica XYZ si sposa con il db ABC io passo
subito ad usare quelli)
Scusate l'OT, ma se qualcuno ha qualche dritta da darmi gli offro una (o
più) birra(/e).
#endif
Grazie e ciao


 me dicendo che con il db avrei un calo prestazionale non trascurabile.
Ma a quanto ho capito il tuo DB avrebbe praticamente una sola tabella
con una sola colonna: quindi tanto vale mettere tutto su uno o piu'
File (con accesso casuale) e amen.
Se i record sono a grandezza fissa ti muovi con seek (magari
implementandoti una cache "ad hoc" se hai un particolare pattern di
accesso).
Non e' chiaro inoltre se il vettore sara' "sparso", magari se il 99.99%
degli elementi e' nullo fai prima con una (hash) map.
Fabio

 accesso).
Una tabella con 2 colonne, ad ogni select modifico il campo di una
colonna. Avevo già pensato di mettere tutto su file, ma la classe _non_
ha grandezza fissa e quindi non saprei come "gestirla" (googlando ho
visto che il procedimento per inserire un vector in un file è inserire
a-il numero di elementi contenuti b-la dimensione degli elementi c-dal
primo elemento scrivere su file a*b byte. Questo è impraticabile, visto
che gli elementi hanno grandezza "dinamica").
Per ora uso il db solo come "salvataggio" del vector, se si pianta
tutto trasporterò tutto su db. :)


 ha grandezza fissa e quindi non saprei come "gestirla".
Qui hai due possibilita', a seconda di come sono i tuoi dati.
1) Se le dimensioni dei valori non cambiano molto, e hanno una
dimensione massima "ragionevole", puoi usare record a grandezza fissa.
Hai uno "spreco" in termini di spazio ma una maggiore efficienza in
termini di tempo, il solito trade-off insomma.
2) Usi due file, uno fa da indice e l'altro contiene i dati veri e
propri.
L'indice e' un file con record a grandezza fissa con 2 campi: chiave e
posizione nell'altro file.
L'altro file contiene i vari record a lunghezza variabile. quando devi
accedere a un dato cerchi nell'indice (per esempio con una ricerca
binaria) l'offset a cui si trova il tuo dato nell'altro file. Questo si
complica un po' quando aggiorni i record del secondo file aumentandone
la dimensione (devi fare un po' di book-keeping, complicato ma tutto
sommato divertente).
2b) molto piu' semplice, usi le librerie Berkeley DB (free e
disponibili ovunque) per avere gia' pronto quanto sopra (molto piu'
efficiente di DBMSl, essendo librerie che operano direttamente sui file
invece di accedere un server esterno).
(Google per ulteriori dettagli ;-)
Saluti,
Fabio

 arbitraria. 
Che però dovrebbe risolvere lo stesso problema...
Hai mai realizzato un allocatore di memoria?
Ecco, il problema è simile.
In effetti il problema è conosciuto perché il 99% degli allocatori di 
memoria di sistema hanno vari problemi (incluso quello di Linux e di 
molte altre piattaforme; ultimamente avranno risolto i problemi, spero).
Kiuhnm

 Ecco, il problema è simile.
Qualcosa di simile, anche se a livello più alto (ovvero non si lavorava a
livello di OS, ma si doveva gestire la memoria di un interprete, quindi la
malloc l'avevo già in mano).
-- 
USB Priests for only 10$

 2b) molto piu' semplice, usi le librerie Berkeley DB
Approvato! ;)
[OT] Ma che vantaggi avrei nel mio caso rispetto ad utilizzare mysql?


 [OT] Ma che vantaggi avrei nel mio caso rispetto ad utilizzare mysql?
Il vantaggio principale e' che non ti serve un istanza di mysql che
gira sulla tua macchina
(mangiandosi piu' ram della tua applicazione ;-)
Praticamente e' come se avessi il db (ma solo le due tabelle che ti
servono) dentro il tuo eseguibile.
Fabio

On 6 Mar 2006 10:46:56 -0800, Fabio 
was talkin'about:
#define IMHO

Se il problema é non avere un DBMS full puoi valutare soluzioni come 
sqlite o firebird embedded.
-- 
  Giuseppe "Cowo" Corbelli \/\ My software: 
http://cowo.yoda2000.net
    **ANTI-SPAM** -- **Substitute IHATESPAM with cowo to reply by mail**
  -<! Heavy Metal Or No Metal At All! Whimps And Posers Leave The Hall !>-
 	 			Manowar - Metal Warriors

 Si che lo e', sostanzialmente per definizione.
Sě, ma allora come mai č ridimensionabile? Se viene ridotto non c'č 
problema, ma se viene ampliato? Si disalloca il vecchio array e ne viene 
riallocato uno nuovo della dimensione voluta?


Esattamente. O meglio, se viene ampliato per accodamento, la lunghezza 
del nuovo array non e' quella strettamente necessaria, ma viene allocato 
piu' spazio, cosi' che aggiungendo un gran numero di elementi il numero 
di riallocazioni sia un logaritmo del numero di inserimenti.
La base del logaritmo varia pero' tra le implementazioni.
I seguente programma aggiunge a un vettore di caratteri centomila 
caratteri uno alla volta, e ogni volta che c'e' una riallocazione stampa 
la lunghezza dell'array.
#include <vector>
#include <iostream>
int main() {
    std::vector<char> v;
    size_t cap = v.max_size();
    for (int i = 0; i < 100000; ++i) {
       if (v.capacity() != cap) {
          cap = v.capacity();
          std::cout << cap << std::endl;
       }
       v.push_back(0);
    }
}
Con Visual C++ 7.1 si ottiene il seguente output, corrispondente a un 
fattore di scalatura del 150%.
0
1
2
3
4
6
9
13
19
28
42
63
94
141
211
316
474
711
1066
1599
2398
3597
5395
8092
12138
18207
27310
40965
61447
92170
138255
Con GCC 3.3.3 si ottiene il seguente output, corrispondente a un fattore 
di scalatura del 200%, ossia ad ogni riallocazione la dimensione raddoppia.
0
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
Ovviamente, durante la riallocazione devono essere in memoria virtuale 
sia il nuovo array che quello vecchio.
