Dimensioni dinamiche degli array. perchè si e perchè no?

di il
31 risposte

31 Risposte - Pagina 2

  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    American horizon ha scritto:


    Grazie ancora a tutti per le spiegazioni.
    Tirando le somme si può dire quindi che se conosco a priori la grandezza massima di una collezione di dati conviene usare sempre e comunque un array in quanto generalmente più veloce del vettore, viceversa, se proprio non posso stabilirne una grandezza precisa di una collezione, allora sono obbligato ad usare i vettori.

    Tornando ai paraogoni tra i vari linguaggi e le diverse filosofie, si può comunque affermare che l'accesso ad una collezione di dati in un linguaggio come PHP che mette a disposizione solo array dinamici (che corrispondono quindi ai vettori di java) non raggiungerà mai le prestazioni di un medesimo codice java basato su array statici.
    Devi comunque considerare che usualmente le strutture dati vanno a braccetto con gli algoritmi come ben descritto, ad esempio, nei libri di Knuth.

    Ovvero, per un certo problema risulta migliore l'utilizzo di un certo algoritmo, e tale algoritmo a volte (anzi, spesso) si porta dietro una sua struttura dati più o meno complessa.

    Moltissime cose si possono risolvere tramite l'uso di Array, però spesso tale approccio risulta si intuitivo, ma inefficiente e/o poco performante.
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    Commodore64 ha scritto:



    Moltissime cose si possono risolvere tramite l'uso di Array, però spesso tale approccio risulta si intuitivo, ma inefficiente e/o poco performante.
    Intendi array ARRAY o vettori?
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    Migliorabile forse non mi sono spiegato bene.
    Col termine statico intendevo un array di dimensioni fisse,ho usato quella parola perchè in italiano l'inverso di dinamico è proprio statico!

    Bisogna fare una precisazione,tutte le keyword quali "static,protected,public,private" non influenzano l'area di memoria utilizzata,ma influenzano la loro visibilità.

    Ho però fatto un grave errore dimenticandomi che in java gli array sono oggetti e di conseguenza saranno allocati nell'heap,perchè java non sa gestire oggetti "statici" ovvero generati nello stack.
    In pratica tutto ciò che dichiari come "new" sarà allocato nell'heap.

    Quindi la scelta degli sviluppatori di adottare un array "statico" allocato nell'heap rimane un mistero!
    forse la jvm lo può allocare nello stack e usarlo li per aumentarne le prestazioni,ma non conoscendo il suo reale funzionamento non posso dire nienete.
    Nel linguaggio C e C++ (versioni standard ovvio) non esiste neppure il concetto di un vettore ridimensionabile in automatico, perchè questa cosa è totalmente al di fuori della filosofia del linguaggio C (e quindi del C++)
    Eresia!
    nel c e c++ esistono i vettori statici e dinamici! e a differenza di altri linguaggi non traggono in inganno:
    
    int vettore[999]; //vettore statico nello stack
    int* vector = malloc(sizeof(int) * 999); //vettore dinamico nell'heap
    vector = realloc(vector,sizeof(int) * 99999) //resize vettore dinamico
    
    Per sopperire al fatto che ti mancano gli array dinamici puoi sempre crearti la tua classe array che ne gestisca la funzionalità.

    Consiglio anche questa microlettura per capire un pò la differenza tra stack e heap.
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    X vbextreme: mi dispiace contraddirti, ma stai pasticciando concetti e linguaggi.

    In Java indicare un campo o un metodo static vuol dire che e' un campo/metodo di classe e non di istanza. Certo, ha impatto sulla visibilita', ma anche su dove l'oggetto e' allocato: tendendo sempre presente il concetto di reference, un oggetto static e' un oggetto globale, quindi allocato nell'area di memoria degli oggetti globali.

    Qualunque sia il tipo di visibilita', via Reflection posso leggerlo e scriverlo anche senza la presenza di una istanza, da qualunque parte del codice.

    Il perche' allocare tutto nello heap? Banale: uniformita' di implementazione, minor complessita' nella progettazione del garbage collector. E sopprattutto, poiche' Java ha abbracciato la filosofia by reference, sarebbe complicato far si che un metodo di una classe abbia come valore di ritorno un vettore allocato sullo stack: dobrebbe crearne un'altro nello heap, copiare il contenuto e ritornare quest'ultimo. Inutile.

    Se vuoi sapere tutto su come si progettano i GC, c'e' un'ottimo testo al riguardo (forse il migliore sull'argomento):



    L'esempio fatto in C e' fuorviante: tu hai mostrato come sfruttare le routine di allocazione della memoria per implementare un vettore dinamico. Purtoppo questo approccio non funziona. Ad esempio una volta reallocato, da nessuna parte c'e' scritto quanti elementi contiene (o puo' contenere al massimo). Per farlo dovresti implementare una struttura dati tipo:

    struct Vector {
    int count;
    int size;
    int *data;
    };

    Ma questo, evidentemente, non e' piu' il concetto di array dinamico a cui stai facendo riferimento.

    Dire che Java non puo' allocare oggetti nello stack, e' altrettanto fuorviante: lo stack in Java e' usato come in tutti i linguaggi: i tipi primitivi ed i reference (i puntatori) sono allocati sullo stack.

    Comunque: i misteri non esistono, e' solo mancanza di informazioni.
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    American horizon ha scritto:


    Commodore64 ha scritto:



    Moltissime cose si possono risolvere tramite l'uso di Array, però spesso tale approccio risulta si intuitivo, ma inefficiente e/o poco performante.
    Intendi array ARRAY o vettori?
    Nel senso matematico del termine, quindi anche matrici (vettori di vettori ecc. )
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    Forse non riesco a spiegarmi.
    In Java indicare un campo o un metodo static vuol dire che e' un campo/metodo di classe e non di istanza
    Per quello ho scritto statico e non static!
    un oggetto static e' un oggetto globale, quindi allocato nell'area di memoria degli oggetti globali.
    La memoria è suddivisa in due parti:
    Stack
    Heap

    Non esiste una memoria globale,ma esisterà una memoria gestita dalla vm come area di memoria globale!
    Il perche' allocare tutto nello heap? Banale: uniformita' di implementazione, minor complessita' nella progettazione del garbage collector.
    Il Garbage Collector serve proprio per gestire la memoria dell'heap e basta,non esiste un Garbage Collector per lo stack,lo stack è gia gestito dalla cpu!!!!
    L'esempio fatto in C e' fuorviante: tu hai mostrato come sfruttare le routine di allocazione della memoria per implementare un vettore dinamico. Purtoppo questo approccio non funziona. Ad esempio una volta reallocato, da nessuna parte c'e' scritto quanti elementi contiene (o puo' contenere al massimo).
    Si vede che sei agli inizii.
    Cosa vuol dire che da nessuna parte c'è scritto quanti elementi contiene?l'ho poi scritto?
    Racchiudere il tutto in una struttura o classe è solo una semplificazione del programmatore ma non serve a niente per il codice:
    Esistono infinite tecniche per estrarre la dimensione del vettore.
    Ecco un esempio di un vettore di char dinamico,praticamente l'uso di strighe in c senza il terminatore '\0',come noterai non serve assolutamente a niente creare strutture o diavolerie simili!
    
    void whyprint(int* vect,int count)
    {
        int i = 0;
        for (i = 0; i < count ; i++)
            printf("%c",vect[i]);
    }
    
    int main()
    {
        int* vect = NULL;
        int count = 0;
        char c;
    
        while ( (c=getchar()) != '\n' && c != EOF  )
        {
            if (vect == NULL)
                vect = malloc(++count);
            else
                vect = realloc(vect,++count);
    
            vect[count-1] = c;
        }
    
        whyprint(vect,count);
        return 0;
    }
    
    
    Dire che Java non puo' allocare oggetti nello stack, e' altrettanto fuorviante: lo stack in Java e' usato come in tutti i linguaggi: i tipi primitivi ed i reference (i puntatori) sono allocati sullo stack.
    
    Assolutamente falso,c++ crea oggetti anche nello stack:
    
    oggetto sobj; //creato oggetto di nome sobj nello stack
    oggetto* dobj = new oggetto(); // creo oggetto nell'heap di nome dobj
    
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    vbextreme ha scritto:


    Nel linguaggio C e C++ (versioni standard ovvio) non esiste neppure il concetto di un vettore ridimensionabile in automatico, perchè questa cosa è totalmente al di fuori della filosofia del linguaggio C (e quindi del C++)
    Eresia!
    nel c e c++ esistono i vettori statici e dinamici! e a differenza di altri linguaggi non traggono in inganno:
    
    int vettore[999]; //vettore statico nello stack
    int* vector = malloc(sizeof(int) * 999); //vettore dinamico nell'heap
    vector = realloc(vector,sizeof(int) * 99999) //resize vettore dinamico
    
    Per sopperire al fatto che ti mancano gli array dinamici puoi sempre crearti la tua classe array che ne gestisca la funzionalità.

    Consiglio anche questa microlettura per capire un pò la differenza tra stack e heap.
    Nessuna eresia.

    Il tuo esempio è accettabile ma non si tratta di una caratteristica interinseca del linguaggio C / C++ (neppure la alloc/realloc è intrinseca, è semplicemente una funzione di base del linguaggio, ma NON fa parte della semantica del linguaggio)

    Sicuramente la filosofia del C / C++ ti dice che se ti mancano gli array dinamici... te li devi costruire a codice...

    Diverso è il discorso, ad esempio, per linguaggi come PHP (se non ricordo male) e alcuni vecchi tipi di BASIC, che in effetti nella loro semantica di base compendono il vettore ridimensionabile a piacimento. Quella è una cosa diversa, la discussione verteva su quello, se una cosa del genere va bene oppure non va bene. (IMHO, la risposta è che tutto dipende dai casi in esame... )
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    Esatto, se nel C++ o nel Java è possibile utilizzare escamotage per rendere variabili le dimensioni di un array statico, questo non significa che si tratta di una procedura consentita di default dal linguaggio..

    Tanto per dire, se io ho un array[10], ad un certo punto necessito di un array che abbia 5 settori in più. Nulla mi vieta di creare un array2[array.length() + 5] (ok è una sintassi abbozzata non credo esista)

    Ma resta il fatto che è diverso dal metodo push messo a disposizione da PHP o AS3, a meno che il metodo push non nasconda dietro proprio questa tecnica di "riallocazione" sopra descritta (in pratica crea un nuovo array partendo dalle dimensioni dell'originale e aggiungendogli di volta in volta un nuovo settore).. Questo non lo so bisognerebbe studiarne la classe, per il momento mi sono limitato solo ad usarlo senza sapere i meccanismi che cela
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    a meno che il metodo push non nasconda dietro proprio questa tecnica di "riallocazione" sopra descritta
    Come fanno tutti i linguaggi ad alto livello,nascondono.

    Tornando al thread se si vuole creare una classe vector che implementi la riallocazione dinamica di un vettore si può partire studiando come allocare direttamente la memoria
    Poi si passerà a studiare un perfetto approccio ad un classe che simili i vettori.
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    American horizon ha scritto:


    esatto, se nel C++ o nel Java è possibile utilizzare escamotage per rendere variabili le dimensioni di un array statico, questo non significa che si tratta di una procedura consentita di default dal linguaggio..

    Tanto per dire, se io ho un array[10], ad un certo punto necessito di un array che abbia 5 settori in più. Nulla mi vieta di creare un array2[array.length() + 5] (ok è una sintassi abbozzata non credo esista)

    Ma resta il fatto che è diverso dal metodo push messo a disposizione da PHP o AS3, a meno che il metodo push non nasconda dietro proprio questa tecnica di "riallocazione" sopra descritta (in pratica crea un nuovo array partendo dalle dimensioni dell'originale e aggiungendogli di volta in volta un nuovo settore).. Questo non lo so bisognerebbe studiarne la classe, per il momento mi sono limitato solo ad usarlo senza sapere i meccanismi che cela
    Sicuramente.

    Un migliore approccio potrebbe essere quello di usare una linked list i cui elementi siano puntatori (o reference) agli elementi del vettore, nel qual caso gli elementi del vettore potrebbero essere altri vettori completi (e così via, iterativamente) oppure istanze di classi (oltre che tipi base)

    Aggiungere e togliere elementi risulta molto veloce, nella nostra ipotesi l'insieme non è ordinato quindi la procedura di inserimento o rimozione non deve conservare il vincolo di ordinamento completo.

    Considera comunque che con un vettore dinamico tu non è che hai risolto tutti i problemi del mondo. Potrebbe essere che in un tuo software ti capiti di "inventare" un algoritmo che va a braccetto con (ad esempio) la struttura dati albero bilanciato, nel qual caso devi usare un albero bilanciato, mediante librerie di classi oppure te lo devi costruire tu a codice.
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    Un migliore approccio potrebbe essere quello di usare una linked list
    Non confondiamo gli array con le linked list.
    Un array è costituito da blocchi di memoria adiacenti,mentre una linked list i blocchi di memoria sono sparsi.
    Come hai fatto notare, le linked list si usano quando si vuole avere velocità nell'inserimento ed eliminazione dei dati,mentre l'array si userà quando si vorrà avere una miglio velocità di lettura e scrittura della memoria.

    array = + veloce accesso alla memoria dell'array.
    linked list = + veloce riallocazione e gestione pseudo array.
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    vbextreme ha scritto:


    Si vede che sei agli inizii.
    Hai proprio ragione .

    Comunque si sta' pasticciando con concetti diversi, invece di chiarire. Il risultato e' un polpettone di paradigmi di programmazione.
    Ma va bene cosi'
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    vbextreme ha scritto:


    a meno che il metodo push non nasconda dietro proprio questa tecnica di "riallocazione" sopra descritta
    Come fanno tutti i linguaggi ad alto livello,nascondono.
    Quindi il push del PHP crea ogni un array statico ex-novo? Lo sai con certezza?

    A questo punto sorge un'ulteriore domanda.
    Se alla base non esistono array realmente dinamici (bensì sono tutti statici con metodi "subdoli" per allungarli) qual è la reale differenza tra gli array e i vettori nel java?
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    vbextreme ha scritto:


    Un migliore approccio potrebbe essere quello di usare una linked list
    Non confondiamo gli array con le linked list.
    Un array è costituito da blocchi di memoria adiacenti,mentre una linked list i blocchi di memoria sono sparsi.
    Come hai fatto notare, le linked list si usano quando si vuole avere velocità nell'inserimento ed eliminazione dei dati,mentre l'array si userà quando si vorrà avere una miglio velocità di lettura e scrittura della memoria.

    array = + veloce accesso alla memoria dell'array.
    linked list = + veloce riallocazione e gestione pseudo array.
    Intendevo dire (ovviamente) che il nostro amico potrebbe costruire una sua classe che vada a "simulare" gli array dinamici usando le linked list.

    Diciamo che non è obbligatorio a priori che un array sia costituito in forma fisica da una sequenza di blocchi di memoria adiacenti. Se questo accade, allora ci sono facilitazioni nel calcolo della posizione in memoria dell'elemento N-esimo, quindi un suo accesso a maggiore velocità.

    Nel caso di "simulazione" via linked list si potrebbero usare tecniche hash per questa funzione, che chiaramente non hanno la performance della struttura contigua, ma non sono neanche da buttare. In ogni caso la linked list offre superiore velocità di inserimento, di append e remove, e spreca poca memoria per elementi allocati ma non usati, quindi in una applicazione real world non è garantito che l'array classico sia migliore della linked list con hash. Insomma, tutte cose che si studiano sui libri di Knuth, che ci insegna principalmente che le implementazioni devono sempre seguire le esigenze dei casi concreti e particolari.
  • Re: Dimensioni dinamiche degli array. perchè si e perchè no?

    Diciamo che non è obbligatorio a priori che un array sia costituito in forma fisica da una sequenza di blocchi di memoria adiacenti. Se questo accade, allora ci sono facilitazioni nel calcolo della posizione in memoria dell'elemento N-esimo, quindi un suo accesso a maggiore velocità.
    Invece si,altrimenti non si parlerebbe piu di array ma di linked list.
    Perchè poi simulare un array con delle linked quando lo si può creare realmente?
    che ci insegna principalmente che le implementazioni devono sempre seguire le esigenze dei casi concreti e particolari.
    Perciò se uno crea un oggetto array vuole un array e non una linked list!
    qual è la reale differenza tra gli array e i vettori
    Partiamo dicendo che in informatica array e vettore sono la stessa cosa,caso diverso per la matrice che sarebbe un "vettore di vettori"
    Nel caso specifico di java NO!
    Perchè java non chiami con i nomi appropriati le cose non lo so!
    In java gli array sono realmente array statici
    In java i vettori sono le linkedlist
Devi accedere o registrarti per scrivere nel forum
31 risposte