Newsgroup: it.comp.lang.c++
Titolo: Inserimento ordinato in una lista standard.

Un dubbio mi attanaglia:
dal punto di vista prestazionale, è + efficiente inserire in testa con
la push_front e poi chiamare la sort della lista, oppure effettuare
prima la ricerca tramite un iteratore della posizione in cui effettuare
l'inserimento (con la find()) e poi chiamare la insert()?
grazie!
daniele


La funzione membro sort() garantisce al piu' NlogN confronti, contro
gli N(N-1)/4 (se non ho sbagliato i conti) dell'inserimento in
posizione. Bisognerebbe pero' tener conto del fatto che std::list non
consente indirizzamento casuale e che quindi lo spostarsi tra due nodi
non adiacenti comporta lo scorrimento di tutti i nodi intermedi. Questo
non ha effetto sull'inserimento ordinato, ma potrebbe averlo
sull'ordinamento.
In ogni caso per mantenere una sequenza ordinata mi sembra meglio usare
un contenitore fatto apposta, come std::set o std::map.
Ciao,
Nicola

 posizione.
La insert in una list non e' a tempo costante, e la search a tempo lineare?
In totale il singolo inserimento mi viene semplicemente N.
Mi viene il dubbio che tu abbia valutato la complessita' globale (creazione 
di una lista di N elementi), mentre secondo me l'OP chiedeva il costo della 
singola operazione (ho una lista ordinata e voglio fare un inserimento che 
mantenga l'ordinamento).
Tutto questo fermo restando che, come dici, e' meglio usare un set (o piu' 
in generale un multiset), che nell'inserimento singolo ha complessita' 
d'inserimento logN (quindi migliore di entrambi i casi precedenti), e nel 
complesso paragonabile alla sort().
--
Marco

 complesso paragonabile alla sort().
L'uso di un set, assumendo valori tutti diversi, comporta nel caso
peggiore log1+log2+...+log(N-1) confronti, che e' meglio di NlogN.
Ciao,
Nicola

 peggiore log1+log2+...+log(N-1) confronti, che e' meglio di NlogN.
Non č vero, sono entrambi O(NlogN) e l'ordinamento finale č 
intrinsecamente piů efficiente, quindi quasi tutte le implementazioni 
ben fatte tendono a riflettere questo fatto.
Kiuhnm
P.S. Appena ho tempo esamino la tua risposta all'altro mio post!

 peggiore log1+log2+...+log(N-1) confronti, che e' meglio di NlogN.
Giusto! Ho scritto "paragonabile" per pigrizia, non avevo voglia di 
ragionare troppo ;)
Pendiamo dalle labbra (o dalle dita) dell'OP per sapere la sua 
interpretazione =)
--
Marco 

*PaN!* ha scritto:


 Non č vero, sono entrambi O(NlogN) e l'ordinamento finale č 
penso che abbia ragione Nicola nei casi concreti, mentre il tuo 
ragionamento fila per N->oo.
Mi pare di ricordare per N grandi (ma non necessariamente 
infiniti), log1+log2+...+log(N-1), ossia la sommatoria dei 
logaritmi, tende a NLogN-N (c'č quindi un fattore di vantaggio 
(quel -N) che cmq non č nullo.
P.S. come si chiama quella formula ... ho in mente il nome 
Stirling, ma mica sono molto sicuro.
ciao
Soviet_Mario


 NLogN-N (c'è quindi un fattore di vantaggio (quel -N) che cmq non è nullo.
Sì, è l'approssimazione di Stirling.
Kiuhnm

 un'operazione e l'altra (inserimento, cancellazione, ecc...).
Considerato che l'OP fa gia' uso di una struttura linkata non sono
convinto che questo consiglio sia valido. Diverso sarebbe se
l'alternativa fosse con un std::vector.
Ciao,
Nicola

 l'alternativa fosse con un std::vector.
Una lista linkata può essere ordinata con il mergesort e qualche 
versione speciale del quicksort (di cui non ricordo il nome) che lavora 
con tre sotto-liste.
Non dimentichiamo che l'inserimento in un albero richiede un 
ribilanciamento che consiste solitamente nel risalire, dopo avere 
inserito il nuovo elemento, fino alla radice eseguendo rotazioni, skew, 
split o altre operazioni a seconda della tipologia di albero utilizzata.
A me piacciono le skiplist (di Pough, se non erro) per la loro 
semplicità e perché la struttura può essere percorsa come una lista 
linkata, dato che a livello 0 *è* una lista linkata.
Kiuhnm

 split o altre operazioni a seconda della tipologia di albero utilizzata.
Ho fatto alcuni benchmark con il compilatore+libreria C++ 13.10.3077 per 
80x86 di Visual Studio 2003:
A) Lista doppiamente linkata con ordinamento finale.
     list<int> li;
     for (int j = 0; j < n_items; ++j) {
       li.push_back(rand());
     }
     li.sort();
B) Multiset.
      multiset<int> msi;
     for (int j = 0; j < n_items; ++j) {
       msi.insert(rand());
     }
C) Array dinamico con ordinamento finale.
     vector<int> vi;
     for (int j = 0; j < n_items; ++j) {
       vi.push_back(rand());
     }
     sort(vi.begin(), vi.end());
D) Coda a due estremita' con ordinamento finale.
     deque<int> di;
     for (int j = 0; j < n_items; ++j) {
       di.push_back(rand());
     }
     sort(di.begin(), di.end());
E) Lista doppiamente linkata ordinata.
     list<int> li;
     for (int j = 0; j < n_items; ++j) {
       int value = rand();
       li.insert(lower_bound(li.begin(), li.end(), value), value);
     }
F) Array statico con ordinamento finale.
     static int ai[1000];
     for (int j = 0; j < n_items; ++j) {
       ai[j] = rand();
     }
     sort(ai, ai + n_items);
I tempi sono in nanosecondi per elemento inserito nella struttura e 
comprendono il tempo per creare e distruggere la struttura e per 
generare il numero casuale.
La deviazione standard e' inferiore a 10 nanosecondi.
   n_items n_items
      =40   =400
A   1000    820
B    600    610
C    320    270
D    370    460
E    640   1380
F    159    126
Per i dati considerati, risulta che la tecnica piu' efficiente e' 
sicuramente la F, seguita sicuramente dalla C, seguita dalla D, dalla B 
e infine da A per molti elementi e da E per pochi.
Estrapolando verso lo zero, D potrebbe essere migliore di C se si hanno 
sicuramente pochissimi elementi.
Estrapolando verso infinito, F e C rimangono i migliori, A migliora, 
mentre D ed E peggiorano notevolmente.
L'algoritmo piu' efficiente ha lo svantaggio che si fissa a tempo di 
compilazione il numero massimo di elementi, quindi il vector e' la 
soluzione piu' efficiente e generale.
Ovviamente, se l'oggetto contenuto invece di essere un "int" fosse stato 
una "string", i risultati sarebbero stati diversi.
-- 
     Carlo Milanesi
 
http://digilander.libero.it/carlmila

 Per i dati considerati, [...]
I risultati non mi sorprendono se non per il caso A, dove mi aspettavo 
qualcosa di meglio.
I confronti andrebbero fatti usando le migliori implementazioni 
conosciute, ma valle a trovare...
Kiuhnm

 conosciute, ma valle a trovare...
Prova questa versione alternativa:
	list<int> li;
	for (int j = 0; j < n_items; ++j)
	  li.push_back(rand());
	list<int>::iterator it = li.begin();
	int* ai = new int[li.size()];
	for (int j = 0; j < n_items; ++j, ++it)
		ai[j] = *it;
	sort(ai, ai + n_items);
	it = li.begin();
	for (int j = 0; j < n_items; ++j, ++it)
	  *it = ai[j];
Kiuhnm

       *it = ai[j];
delete[] ai;
Kiuhnm


Al di la' di quanto gia' discusso nel thread tieni presente che in
molti casi la differenza e' trascurabile, almeno dal punto di vista
della percezione dell'utente. A meno che tu non sappia gia' che
lavorerai su una mole di dati decisamente corposa o con cicli ripetuti
molte volte puoi tranquillamente scegliere la via che ti risulta piu'
comoda. Piuttosto spendi qualche minuto per incapsulare struttura dati
ed algoritmo, in modo da poter cambiare idea in futuro senza dover
riscrivere mezzo programma.
Ciao,
Nicola

Kiuhnm ha scritto:

Se chiamiamo G il suddetto algoritmo, e chiamiamo H la variante in cui 
si sostituiscono le righe:
     int* ai = new int[li.size()];
     delete[] ai;
con la riga:
     static int ai[1000];
ottengo i seguenti risultati (deviazione standard circa 2):
        n_items n_items
         = 40    = 400
G       626     627
H       607     623
Dato che tale algoritmo e' piu efficiente del caso A (lista doppiamente 
linkata con ordinamento finale) e si differenzia da essa solo per 
l'algoritmo di ordinamento, viene da chiedersi perche' la Microsoft ha 
implementato un algoritmo inefficiente per l'ordinamento di liste.
