funzionamento VECTOR

[stertwi]

ciao a tutti sono nuovo di questo forum...

volevo chiedere chi conosce il vero funzionamento dei vector,

ovvero mi spiego meglio:

io creo un vector[10] di 10 elementi

quando vado ad inserire l'11° elemento cosa succede in memoria?

1 - viene creato un nuovo vector di dimensione maggiore, e vengono ricopiati i 10 elementi(del vecchio) e aggiunto l'11°??

2 - oppure viene espanso(quindi side effect) il primo vector?


chiaramente l'utente vede sempre lo stesso vector sia nel 1° ke nel 2° caso, a me interessa sapere cosa realmente succede in memoria!

usando google nn sono riuscito a schiarirmi le idee!!

spero di schiarirle qui!
grazie in anticipo!

[andbin]

Originariamente inviato da stertwi
1 - viene creato un nuovo vector di dimensione maggiore, e vengono ricopiati i 10 elementi(del vecchio) e aggiunto l'11°??

Questo è quello che succede. La classe Vector (e le altre basate su array) usano internamente proprio un array. Quando la capacità dell'array non è più sufficiente, si preoccupano internamente di creare un nuovo array, copiare i dati dal vecchio al nuovo array e assegnare il reference del nuovo array alla variabile, sicuramente privata, che contengono. In tali tipi di classi, aggiungere al fondo dell'array è più semplice che aggiungere all'inizio/in mezzo.

Originariamente inviato da stertwi
2 - oppure viene espanso(quindi side effect) il primo vector?

Un volta che un array "classico" è stato creato non è ridimensionabile in alcun modo.

[stertwi]

grazie mille, sei stao esaustivo.

riguardo al ridimensionamento di un array, si lo sapevo già.

infatti io sto creando una struttura ke gode delle proprietà del vector, però al contrario del vector voglio evitare la ricopia degli elementi, xkè consuma troppe risorse , quindi ha un costo computazionale troppo elavato!

x cui ho ideato un array di Object (proprio come il vector) ke in ultima posizione prevede il riferimento ad un nuovo array,il quale estende il 1° senza modificarlo "fisicamente", ma l'utente lo vede come un unico array illimitato e quindi dinamico!

esempio:

Object[]array1=new array[10]
.....
.....//pieno da 0 a 8

inserimento ulteriore elemento
Object[] array2=new array[10];
array1[9]=array2;
array2[0]="1° nuovo elemento"; //l'utente la vede come la posizione 10
array2[1]="2° nuovo elemento"; // l'utente la vede come la posizione 11
....
... // e così via

quindi ho altre 9 caselle in più!! ma volendo ne ho molte molte di più!!

che tipi di problemi può dare quest'approccio, secondo il tuo punto di vista?

[andbin]

Originariamente inviato da stertwi
infatti io sto creando una struttura ke gode delle proprietà del vector, però al contrario del vector voglio evitare la ricopia degli elementi, xkè consuma troppe risorse , quindi ha un costo computazionale troppo elavato!

Nelle classi come Vector e ArrayList, basate su un array, esistono due valori: "capacity" e "size". La prima indica la capacità totale dell'array e la seconda indica il numero "logico" di elementi contenuti. capacity è sempre uguale o maggiore rispetto a size.

Se tu fai:
List<String> ls = new ArrayList<String> (100);

crei un ArrayList con capacità iniziale 100 e size iniziale 0. Internamente ha creato un array di 100 elementi ma il size logico è zero.
Man mano che riempi l'ArrayList, il size aumenta e quando cerchi di inserire il 101° elemento, l'array non viene ridimensionato solo a 101! In genere viene raddoppiata la capacità. Pertanto viene allocato un nuovo array di 200 elementi, vengono ricopiati i 100 elementi e inserito il 101° elemento.

Per questo si dice che la complessità computazionale dell'inserimento al fondo è O(1). Cioè è vero che ogni tanto l'array deve espandersi ma il suo "costo" è diluito nel tempo.
Aggiungere (o rimuovere) all'inizio o in mezzo invece ha una complessità O(N) perché è necessario spostare gli elementi successivi.

[stertwi]

Originariamente inviato da andbin
Aggiungere (o rimuovere) all'inizio o in mezzo invece ha una complessità O(N) perché è necessario spostare gli elementi successivi.

si hai ragione, sfruttando le proprietà dell'arrayList si, ma sfruttando le proprietà solo dell'array, ovvero non preoccupandomi di avere una sorta di array "frammentato", cioè non riempio l'array come un bicchiere, facendoti un esempio:

anke se ho le prime k posizioni dell'array a null, io posso inserire tranquillamente nella posizione k+1, proprio come in un array classico.

l'inserimento alla fine forse nn costerà O(1), secondo i miei calcoli dovrebbe costare O(log n) sia per l'inserimento che per la cancellazione, xkè nel caso ke ho serie di array di 10 collegati tra loro se devo inserire/cancellare in posizione 16 devo:
1-spostarmi in ultima posizione array1, quindi array1.length-1 (la quale ha il riferimento al prossimo array)
2-e andare nella posizione array2[16-(array1.length-1)]

questo dovrebbe costare O(log n) giusto?

evitando il caso limite della ricopia degli elementi che sicuramente costerà O(n).

[nether]

ma hai problemi di performance con gli ArrayList o e' per tuo sfizio personale?
Non sono esperto, ma non sono molto convinto da quanto potresti guadagnare con questa architettura e in quali situazioni rispetto all'architettura di ArrayList.

[stertwi]

Originariamente inviato da nether
ma hai problemi di performance con gli ArrayList o e' per tuo sfizio personale?

un pò l'uno e un pò l'altro

Non sono esperto, ma non sono molto convinto da quanto potresti guadagnare con questa architettura e in quali situazioni rispetto all'architettura di ArrayList.

l'ArrayList come il Vector non sono proprio il massimo della vita a livello di costo computazionale, ovvero, tu(utente) vedi le strutture come delle strutture dinamiche, ma in realtà non lo sono, perchè nel momento in cui queste strutture sono sature, in automatico viene creata una nuova struttura più grande che ricopia TUTTI i vecchi elementi, e questa è una grossa spesa a livello di memoria(pensa a Vector di migliaia di elementi,sono dolori) , specialmente se tu vuoi fare in modo che un algoritmo ti costi il meno possibile, con arrayList e vector di sicuro non hai maggior prestazioni e minor costo, io voglio ottenere questo.

[simo7784]

I costi computazionali non sono questi? Perche' O(log n)?

            | ArrayList | tuaStruttura |
            |           |              |
Inserimento |    O(1)   |     O(m)     |
in coda     |           |              |
            |           |              |
Inserimento |           |              |
 accesso    |    O(n)   |    O(m)     | Solitamente
non seq     |           |              |
            |           |              |
Inserimento |           |              |
in coda     |   O(n)    |     O(m)     |
caso limite |           |              |
            |           |              |
Rimozione   |    O(n)   |     O(m)     |
per indice  |           |              |
            |           |              |
Rimozione   |    O(2n)  |    O(m*l)    |
per eleme   |           |              |
            |           |              |
Letture con |           |              |
accesso     |   O(1)    |     O(m)     |
non seq     |           |              |
            |           |              |
Lettura     |           |              |
accesso     |   O(n)    |    O(m*l)    |
seq di tutto|           |              |
**********
n=numero Elementi
l=dimensioni array
m=numero array
tenendo conto che
n<=m*l

In realta' dipende molto dall'uso che fai della tua struttura, secondome.

[stertwi]

se n sta ad indicare il numero totale degli elementi
ed m il numero di array collegati tra loro

n non può mai essere minore di m

m è logaritmicamente minore di n

ti faccio l'esempio di 2 array di 10 elementi collegati tra loro
m=2
n=20

x trovare un elemento in posizione k=13 il costo è O(1) x arrivare al riferimento del secondo array( array1[9]), e O(1) x arrivare all'elemento interessato (array2[3])

chiaramente aumentando il numero degli array quindi degli elementi il costo aumenta, non lineramente ma logaritmicamente.

leggi bene i post precedenti x capire il funzionameno dell'array...

mi sa ke la tua tabella non va bene poi può essere pure ke mi sbaglio!!!

[simo7784]

n<=m*l
es n=22
nella tua struttura supponendo ogni array di lunghezza l=10 avrai come minimo m=3
quindi 22<=3*10 OK
Il costo non aumenta logaritmicamente, mi pare (ma posso sbagliare).
10 array da 10 elementi. Ho quindi m=10. nel caso peggiore accedo ad un elemento dell'ultimo array, facciamo il 95. Per accedere all'ultimo array faccio m-1 passi, per accedere all'elemento faccio un passo. Il costo e' O(m-1+1). Sarebbe logaritmico se ogni elemento degli array puntasse ad un array di valori o ad un valore. In questo caso la base del logaritmo sarebbe dettata dal numero di elementi dell'array. Vedi alberi binari.

EDIT:il fatto che m sia logaritmicamente minore di n e' da dimostrare. L=10. Inserisco 11 elementi ho m=2, n=11. Tolgo i primi dieci elementi, ho m=2, n=1.