Newsgroup: it.comp.lang.c++
Titolo: confronto per precedenti, indicizzazione ordinale

Sono curioso di vedere come un programmatore C++ affronterebbe i 
seguenti due problemi.
_Confronto per precedenti_
Supponete di avere un insieme di oggetti il cui confronto è parzialmente 
inconsistente poiché la proprietà transitiva non vale per ogni terna.
Volete mantenere una sequenza ordinata S di tali oggetti soggetta a 
inserimenti e cancellazioni.
S deve essere tale che, senza l'accesso alla funzione di confronto, sia 
impossibile determinare se il confronto tra gli oggetti è incosistente.
Per es., si potrebbe avere che a < b e b < c, ma c < a. Ciononostante, 
in S, se a e b precedono risp. b e c, allora a deve precedere c.
_Indicizzazione ordinale_
Supponete di volere accedere agli oggetti in una sequenza ordinata 
dinamica per ordinale. Si desidera cioè un operatore [] in stile vector 
che permetta di accedere all'elemento i-esimo in tempo O(logN).
Kiuhnm

 che permetta di accedere all'elemento i-esimo in tempo O(logN).
Fai un map in cui la key e' il numero ordinale dell'elemento, ovviamente 
il map va ricreato per ogni inserimento o cancellazione secondo il 
"confronto dei precedenti", il che puo' essere oneroso, ma se il 
requisito e' quello sull'accesso [] e il map non e' troppo grosso o gli 
inserimenti/cancellazioni non sono troppo frequenti potrebbe funzionare, 
calcola che per ottimizzare la creazione del map puoi usare l'hint sulla 
insert() (che in pratica ti fa fare un solo step di confronto per ogni 
elemento)
In alternativa usi un vector, anche qui sugli inserimenti devi 
ripopolare l'intero vettore (facendone un altro che pero' puoi 
preallocare di n+1 elementi per evitare la riallocazione) sul quale 
probabilmente puoi copiare brutalmente buona parte del vettore sorgente. 
Sulla cancellazione di un elemento la cosa e' + semplice che su un map e 
meno onerosa che col map. Il vector l'operatore [] lo ha gia' 
ovviamente, ed ecco risolto il punto 2.
Bye,
  Gabry

 ovviamente, ed ecco risolto il punto 2.
Improponibile anche questa.
Kiuhnm


Per inserire un nuovo elemento nella sequenza S, che è già ordinata,
bisogna eseguire il confronto a partire dall'ultimo elemento della
sequenza.
Il nuovo elemento dovrà seguire il primo elemento p che è minore di
quello da
inserire. Se l'elemento p avesse dei precedenti, questo sarebbe il
punto
in cui inserire correttamente il nuovo elemento. Se l'elemento p non
avesse dei
precedenti, questo sarebbe il punto in cui inserire correttamente il
nuovo
elemento.
Se la sequenza è vuota, basta inserire l'elemento.
Se la sequenza contiene un solo elemento basta inserire l'elemento a
seconda
dell'esito del confronto.
Ciao, Ugo

 sequenza.
Perché?
Kiuhnm

Kiuhnm wrote:
[...]
messaggio di flushing...
Kiuhnm
P.S. Ogni tanto il newsserver si blocca...

Kiuhnm wrote:
[...]
Niente da fare.
Riscrivo il post.
Temo che abbiate frainteso il primo punto del post iniziale. In effetti 
non è chiarissimo.
Assumete di avere degli oggetti che, se troppo "vicini", diventano 
inconfrontabili nel senso che il confronto non è affidabile. In pratica 
questo avviene per errori di arrotondamento durante i calcoli del 
confronto. Chiaramente non potete usare std::set perché avrebbe un 
comportamento indefinito. Allora come fare?
Non è un problema semplicissimo. Naturalmente il "come fare" sta per 
"come ovviare al problema limitando al minimo il costo computazionale 
addizionale?"
Kiuhnm


Perché se si incomincia a eseguire il confronto dal primo elemento
della
sequenza ... non si sfruttano le informazioni che sono già
disponibili
eseguendo il confronto dall'ultimo elemento e si è obbligati ad
andare a cercarle ... più avanti ;-)
Piuttosto, non ho capito bene il secondo problema.
Non capisco che cosa intendi per sequenza ordinata
dinamica e forse anche qualche cos'altro.
Ciao, Ugo

 dinamica e forse anche qualche cos'altro.
In pratica un std::set ad accesso tramite key oppure indice.
Per esempio se inserisci 5,7,1,23,8 in S, allora S[3] deve restituire 8 
ed S[0] 1.
Kiuhnm

 comportamento indefinito. Allora come fare?
Tu vuoi un algoritmo che posizioni il nuovo elemento in modo che non
accada che abbia 'a destra' cose più piccole di lui al momento
dell'inserimento (anche se ce ne potrebbero finire in seguito). Giusto?
-- 
blog:  
http://www.akropolix.net/rik0/blogs
 | Uccidete i filosofi,
site:  
http://www.akropolix.net/rik0/
      | tenetevi riso e
forum: 
http://www.akropolix.net/forum/
     | bacchette per voi.

 Non è un problema semplicissimo. 
più che altro non mi sembra risolvibile ... presumo di non avere 
capito esattamente il problema. Se non hai un operatore di 
confronto deterministico, ti devi imho accontentare di un ordine 
di massima, una classificazione a scaglioni
ciao
Soviet


Kiuhnm ha scritto:

Un set di set con un primo metodo di confronto grossolano ma affidabile 
ed il secondo più fine o adattato?
Ciao

 classificazione a scaglioni
Non č completamente vero.
Per non tirarla troppo per le lunghe, vi do la mia semplicissima 
soluzione ad entrambi i problemi, anche se la soluzione ha piccoli 
problemi. Dipende dal contesto in cui la si vuole usare.
Kiuhnm

 ed il secondo più fine o adattato?
Purtroppo non è un metodo efficiente, anche perché altrimenti tanto vale 
riscrivere il confronto in modo che non vi siano errori di 
approssimazione (usando bignum per simulare i numeri razionali).
Ma adesso, nel post successivo, vi scrivo tutta la storia, così capite 
per bene qual è il problema e come ho cercato di risolverlo.
Kiuhnm

 che permetta di accedere all'elemento i-esimo in tempo O(logN).
Passiamo a questo ch'è meglio!
A questo ho pensato per caso mentre cercavo una soluzione al primo
problema. E' di una banalità incredibile: basta modificare un albero 
ordinato (o una skip list) aggiungendo ad ogni nodo un valore che 
indichi il numero di elementi contenuti nel ramo sinistro.
Ad ogni inserimento, si procede incrementando tale valore solo se
si scende nel ramo sinistro. Nella cancellazione si decrementa. Anche il
ribilanciamento non dovrebbe comportare problemi. Al limite si usano le
skiplist dove non vi sono ribilanciamenti!
Kiuhnm