Newsgroup: it.comp.programmare
Titolo: Differenze tra liste ed array

Ciao a tutti,
avrei bisogno di un consulto:
secondo voi cosa e` meglio a livello di
performance/progettazione/programmazione tra l'utilizzo di una lista
(bi)direzionale o un array.
Considerando che i punti salienti dovrebbero essere:
-    facilita` di aggiungere e togliere elementi nella lista ma con
     l'obbligo di percorrerla tutta nella ricerca e cancellazione...
-    ricerca ultra rapida nel caso di array ma notevolmente piu` scomoda
     l'aggiunta e la cancellazione degli elementi...

Zio ha scritto:

imo, informazioni non sufficenti. Che vuol dire 'obbligo di percorrerla 
tutta'?
Inoltre, perché non usare un onesto, semplice principio di 
programmazione, quello di usare un'interfaccia comune così poi, casomai 
ce ne fose bisogno (e non è detto) ti basta cambiare quel pezzetto di 
implementazione ?

 implementazione ?
Esatto, ma quale approccio devo usare o meglio cosa mi conviene visto che
sono un po' con l'acqua alla gola di risorse del computer...

 sono un po' con l'acqua alla gola di risorse del computer...
quello che dico io è:
(supponendo che tu stia scrivendo codice C) scrivi un paio di funzioni 
tipo aggiungi(elemento) e rimuovi(elemento).
Inizia ad usare un semplice array, poi verifica di cosa ha efettivamente 
bisogno il programma (magari avrai 1000 accessi diretti e relativamente 
pochi inserimenti, quindi un array andrà bene). Casomai puoi sempre 
cambiare il meccanismo su cui si basano quelle funzioni di conseguenza. 
Preoccuparsi di performance troppo presto è un errore tremendo ;)

 Preoccuparsi di performance troppo presto è un errore tremendo ;)
beh non sono cosi` d'accordo...
Devo fare un'analisi preliminare e il requisito fondamentale e` la
performance e in piu`, cosa che non ho ancora detto, vorrei mettere
nell'eventuale calderone la gestione della memoria, in quanto devo fare
milioni di riallocazioni in breve tempo e questo potrebbe essere a regime un
ulteriore problema, ma preferendo un metodo piuttosto che un altro, forse...

 ulteriore problema, ma preferendo un metodo piuttosto che un altro,
forse...
Se vuoi fare una analisi seria devi dare qualche dato piu' preciso su quello
che devi fare:
Che genere di applicazione stai scrivendo?
Avrai principalmente accessi per inserimento, per ricerca, per
cancellazione? Hai la possibilita' di fare accesso diretto se usi un array?
Che dati ci devi mettere dentro? Quanti? Che linguaggio intendi usare per
implementare il tutto? Hai la necessita' di fare ordinamenti? ecc ecc
Ciao
Menez
 
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

menez ha scritto:

..puoi usare librerie esterne? su che piattaforma lavori?
tutti i dati sono uguali o alcuni potrebbero essere più usati di altri?
quanta memoria hai a disposizione? Che tipo di accesso ti servirà 
(solamente diretto o magari selezioni e che tipo di selezioni)

> Voi cosa ne pensate?
Io vorrei creare una libreria generica che sia performante anche nelle
situazioni piu` critiche (velocita` di ricerca, aggiunta e cancellazione
degli elementi).
Ci ho un po' riflettuto e mi sembra di aver capito che se utilizzassi un
albero ordinato vinco in tutti i casi :)
A parte uno: non sarei in grado di farla :"(
Esiste qualcosa di gia` collaudato in rete a cui posso ispirarmi?

Ciao Zio,
sono sicuro di esserti utile visto che ho già provato l'algoritmo ;)
qualche tempo fa ho implementato una lista bidirezionale che
successivamnte ho trasformato in Template...
si tratta di una lista bidirezionale con una struttura supplementare
dinamica,
sei obbligato a scendere a compromessi se è la velocità è ciò che
cerchi
e vuoi comunque mantenere semplicità legata a flessibilità.
sinteticamente:
- la lista ha la concatenazione bidirezionale ordinata degli elementi
- la lista ha la concatenazione semplice ordinata di una lista
ulteriore
  contenete il riferimento a questi elementi con distanza maggiore,
  la distanza aumenta al crescere del numero degli elementi presenti
nella lista.
dimenticavo, l'allocazione e la deallocazione di memoria rallenta
l'algoritmo
di un tempo infitamente ingiusto per chi ritiene essere il più veloce
del west ;)
è indispensabile un gestore di memoria,
senza spaventarsi per la parolona, in definitiva è solo una lista di
elementi allocati,
( personalmente utilizzo array, poi vedi tu) e quando chiedi di
deallocarla,
inserisce il rifeirmento in una lista di tipo pila e te la restituirà
quando chiedi nuovamente allocazione.
ciao
duido