Newsgroup: it.comp.lang.c++
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...
Voi cosa ne pensate? Tra l'altro forse sono un po' OT perche` forse non e`
necessariamente una questione di linguaggio...


E' stato deciso gia' tempo fa che questioni generiche di programmazione, 
se riguardano implementazioni in C++, sono cmq in topic - se non sbaglio 
esistono cmq newsgroup piu' generici di informatica, piu' adatti.
Anyway, e' una questione di complessita' computazionale. I costi di 
inserimento/rimozione sono theta di 1 per le liste (se hai gia' un 
puntatore all'elemento o al precedente), ed O(n) (o theta...?) per gli 
array. D'altronde, sugli array ordinati puoi fare ricerca dicotomica in 
log(n), sulle liste, ordinate o meno, hai sempre un O(n). E cosi' via... 
insomma: dipende da quello che devi fare, as usual.
-- 
Mat/tia Belletti - Undergraduate student @ 
cs.unibo.it
ICQ: 33292311    - email: 
mbel...@cs.unibo.it
IRC: RedGlow     - site(s): 
http://mbellett.web.cs.unibo.it/
Jabber: RedGlow  - Linux registered user 299762 @ machine 213003

 necessariamente una questione di linguaggio...
Certo che invece è una questione di linguaggio sapere scegliere tra le
strutture che il Linguaggio (array) e La Libreria Standard (le altre tre +
std::string se si tratta di caratteri) ti offre! E per scegliere devi sapere
come sono implementate e che metodi ti mettono a disposizione.
Facci sapere che cosa devi fare, qual'è il problema, così proviamo a dare
una risposta.
fabiomdf
 
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 insomma: dipende da quello che devi fare, as usual.
e si mi rendo conto...
Io cercavo di generalizzare...

 una risposta.
io sto parlando di qualcosa di generico, quindi una struttura con diversi
dati dentro...
e se si tratta di una lista con in piu' i riferimenti degli elementi
adiacenti oppure il tutto inglobato dentro un'altra struttura...

 sulla nomenclatura che usi: cos'e` "O(n)" infinitesimo? e theta di 1?!? 
http://www.diiie.unisa.it/aree/informatica/docenti/mvento/Ordine%20di%20grandezza%20delle%20funzioni.pdf

>
http://www.diiie.unisa.it/aree/informatica/docenti/mvento/Ordine%20di%20grandezza%20delle%20funzioni.pdf
Ma bello, appena posso ci do` un'occhiata...

 adiacenti oppure il tutto inglobato dentro un'altra struttura...
Signori, devo ammettere che questa volta sono senza parole...
Non ho una grande frenquentazione di NewsGroups ma mi pare di non avere mai
visto niente di simile.
Ma chi me lo ha fatto fare a chiedere quale fosse il problema?


 Ma chi me lo ha fatto fare a chiedere quale fosse il problema?
Ma cosa ho mai detto...
Troppo sintetico forse?!?

...

Ma hai un problema concreto o devi rispondere a un compito? Se hai un
problema concreto descrivilo, che so, voglio implementare una rubrica
telefonica...
Ciao,
Nicola

 Io cercavo di generalizzare...
Per quanto riguarda i costi computazionali, Max M. ti ha gia' passato un 
link (utile, credo, anche se non l'ho visto).
Per quanto riguarda invece questo tuo commento, che poi si riferisce 
anche agli ultimi scambi di battute che ho letto su questo thread: il 
punto e' che _non puoi_ generalizzare, su questo argomento.
Ovvero: se chiedi - cosa conviene usare? La risposta e': dipende. Full 
stop. In alcuni casi converra' assolutamente l'una, nell'altro caso 
converra' assolutamente l'altra, in altri sara' indifferente.
Posso pero' darti un ("il", direbbero alcuni) criterio di scelta, che 
funziona in base al caso in cui ti trovi, ed e': il costo 
computazionale. Ma questo e' un argomento abbastanza vasto, anche le sue 
basi sono intuitive, e che vanno decisamente OT :-)


> 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?

 Esiste qualcosa di gia` collaudato in rete a cui posso ispirarmi?
come detto sopra....PER FARE COSA?????
ciao
menez
