Newsgroup: it.comp.programmare
Titolo: trovare un oggetto in un elenco in modo "adattativo"

Ciao a tutti,ů
Il mio problema č quello in oggetto, ma č complicato
da alcune condizioni al contorno. Si tratta di un
elenco di puntatori a "void" di dimensioni
estremamente variabili da qualche decina a diverse
migliaia di elementi. L'elenco č continuamente
aggiornato con inserimento e cancellazione di
elementi. Mi servirebbe un algoritmo molto efficiente
per sapere se un puntatore dato č nell'elenco o meno e
non posso contare su alcun vantaggio a priori dato
dalla natura del problema. Stavo pensando a qualche
genere di coda o altro sistema che "capisca" quando di
un puntatore dato viene controllata spesso la presenza
nell'elenco e si adatti in modo opportuno. In altre
parole, la ricerca dei puntatori piů spesso "testati"
man mano dovrebbe diventare sempre piů veloce.
Credo sia un problema non dissimile da quello della
strategia di paginazione della memoria ma tutto quel
che ho trovato in rete mal si adatta a quel che mi serve.
Idee e consigli? Un grazie per qualsiasi "hint".
Apx.

> dalla natura del problema. Stavo pensando a qualche
Prova una map(pa). Oppure semplicemente un albero bilanciato. Che linguaggio
vuoi usare?
--- bye

 
Come linguaggio, C++ ma riguardo alle strutture dati,
quelle che suggerisci iniziano a mettermi un po' alle
corde, non tanto per l'implementazione quanto per il
test del codice e, prima ancora, avere ben compreso i
dettagli "filosofici" e di funzionamento. Ho decine di
trattazioni sugli alberi ma nessuna su quelli
bilanciati applicata al problema che mi interessa...
Su mappe, nulla di nulla, mai usate in vita mia. A
te la palla :((( (la vedo complicata per me, temo....)
Grazie!!!!
Apx

 te la palla :((( (la vedo complicata per me, temo....)
Tu spiega esattamente cosa ci devi fare con 'sti puntatori. Tu hai un
puntatore "void".. E quindi?
--- bye

 
Devo incorporare in un interprete del C alcune mie
funzioni che a loro volta manipolano oggetti nascosti
all'utente e piuttosto che formalizzare il problema -
il che sarebbe complicato - ti faccio direttamente un
caso di esempio. Un tipico mio problema è descrivere
in modo algoritmico una struttura (di quelle
dell'ingegneria civile, per intenderci). Nell'ambito
di questa, un tipico oggetto (anzi, il più semplice) è
il "nodo", che deve intendersi un punto nello spazio a
cui ad esempio possono attaccarsi travi e altra roba.
Ora supponiamo che voglia creare una fila di nodi
sull'asse X e che mi interessi il quarto nodo per
accedervi successivamente; invece di dare le
coordinate di ciascuno, posso, anzi, vorrei poter
scrivere:
{
   void      *jptr, *joint4 ;
   float       x, y=2, z=3 ;
   for( int ic = 0 ; ic < 10 ; ic++ )
   {
      jptr = create_joint(x,y,z) ;
      if(  ic == 3 )  joint4 = jptr ;
   }
   print_joint(joint4) ;
   print_beam_data (jptr) ;
}
le funzioni "create_joint" e "print_joint" fanno
riferimento a loro volta a una classe "nodo" interna
al programma con un sacco di altre informazioni
necessarie all'elaborazione e non all'utente; facciamo
si chiami "Cnodo". Quel che vorrei è che quando viene
chiamata create_joint, questa inserisca
nell'albero/lista/mappa/etc, il dato "(void*)Cnodo" in
modo che quando viene poi chiamata "print_joint" essa
possa andare a vedere se "joint4" sta nella lista. Se
sì, allora su "joint4" viene fatto il cast, convertito
in Cnodo e di qui partono le operazioni necessarie. Ma
c'è anche "print_beam_data" che stampa i dati di una
trave; allo stesso modo, la struttura dati "vedrebbe"
che "jptr" punta a un tipo interno ma non a quello
giusto (questo controllo avviene poi, in uno stadio
successivo) e segnala l'errore di tipo interno, per
così dire.
Ci saranno altri tipi "interni" oltre al tipo nodo ma
tutte le funzioni di interfaccia devono interagire
tramite puntatori a void. Questo deriva sia da una
limitazione dell'interprete che sto usando e non è
aggirabile, e da una mia necessità anch'essa non
aggirabile. So che potendo usare direttamente i tipi
interni il problema non si porrebbe. Ma proprio non li
posso usare.
Come puoi immaginare quanto mi occorre è praticamente
vicino a un allocatore (anzi, in caso di crash totale
occorre pure scorrere la struttura dati e liberare
quanto è stato allocato dinamicamente) e le richieste
a tale base dati sono pesanti e continue. Siccome i
cicli come quello dell'esempio capitano spesso, in
molti punti del flusso del programma ci saranno
accessi addirittura sempre allo stesso puntatore e un
sistema abbastanza intelligente potrebbe trarne
vantaggio.
Spero di essere riuscito a dare l'idea!
Ciao
Apx.

Ooopsss era ovviamente qualcosa tipo:
   for( int ic = 0 ; ic < 10 ; ic++ , x += 2.0 )


    float       x, y=2, z=3 ;
Mi spieghi perchč non puoi ritornare una struct e vivere felice?
--- bye

 Mi spieghi perchč non puoi ritornare una struct e vivere felice?
nel senso, avere la tua funzione  create_joint(x,y,z) con un protipo del
tipo:
struct cnode* create_joint(float x, float y, float z);
Se no, se sei proprio paranoico e non vuoi che gli utenti sappiano qualcosa
usa struct innestate:
struct myobject {
    int iType;
    void *element;
}
dove iType contiene il tipo di elemento. (vuoto = 0, nodo = 1, linea = 2,
figura = 3, ???)
--- bye

 
No, non sono paranoico, è che l'interprete che sono
*costretto* a usare fa casini con le struct, posso
contare solo sui tipi fondamentali e le chiamate a
funzione. Tutto qui. So che ci sono disponibili
interpreti assai più sofisticati e pure "free" ma sono
costretto a usarne uno in particolare.

 te la palla :((( (la vedo complicata per me, temo....)
Mi intrometto.
Se hai il supporto della Standard Template Library, ti consiglio di usare
gli array associativi.
Secondo me è un'ottima soluzione.
Cito dal sito 
http://www.sgi.com/tech/stl/AssociativeContainer.html
An Associative Container is a variable-sized Container that supports
efficient retrieval of elements (values) based on keys. It supports
insertion and removal of elements, but differs from a Sequence in that it
does not provide a mechanism for inserting an element at a specific
position. [1]
...
...
Complexity guarantees
Average complexity for erase key is at most O(log(size()) + count(k)).
Average complexity for erase element is constant time.
Average complexity for erase range is at most O(log(size()) + N), where N is
the number of elements in the range.
Average complexity for count is at most O(log(size()) + count(k)).
Average complexity for find is at most logarithmic.
Average complexity for equal range is at most logarithmic.
Ti puoi creare una mappa dove la chiave è il valore, a seconda di quello che
vuoi fare potrebbe andare bene anche un "set". In ogni caso se non conosci
la STL, non è semplice da spiegare.
Se hai un pò di tempo da investire ti consiglio (conoscendo già il C++) di
guardare Thinking C++ vol 2, di Bruce Eckel, dove puoi imparare ad usare i
container, gli iteratori e gli algoritmo della STL.

 
Nononono, anzi grazie infinite e poi il NG è fatto
apposta affinché tutti intervengano e volevo
esattamente questo.
In effetti, stavo pensando a qualcosa del genere con
la STL ma mi sono arenato. Premetto che non sopporto
l'uso del NG tipo "fatemi il programma" ma vorrei
pregare chi avesse un attimo di pazienza di dare un
occhio a quel che ho fatto. Un paio d'ore di approccio
alla STL mi hanno consentito di tirare fuori il
programma qui sotto ma, questo è il buffo, capisco a
malapena cosa sto facendo. Potresti/e dirmi solo se la
direzione è giusta? Non chiedo mi facciate il
programma, ci tengo a ribadirlo, ma solo darmi una
mano a correggere il tiro. Come a chi è addentro sarà
ovvio i casini arrivano al "dset.find" ma non capisco
come interpretare il messaggio di errore, cosa
tipicamente difficile con i template per i
principianti. Il compilatore è il borland 5.5.
In tutti i casi grazie del suggerimento, perché è la
direzione che cercavo.
Ciao!
Apx.
///////////////////////////
// STL
#include  <iostream>
#include  <set>
using namespace std ;
// CSL
//
#include  <stdio.h>
//..........................................................
prova insiemi
class  Cdata
{
   public:
     int       key  ;
     Cdata () { ; }
     ~Cdata () { ; }
     Cdata (const Cdata &v2) { key = (v2.key) ; }
     Cdata &operator = (const Cdata &v2)
     {
       key = (v2.key) ;
       return (*this) ;
     }
     bool operator < (const Cdata &v2) const
     {
       return ( key < (v2.key) ) ;
     }
} ;
// 
...........................................................
principale
void      main ()
{
   int     ic  ;
   Cdata
  dat[10]  ;
   Cdata
  probe    ;
   set <Cdata, less<Cdata> >
  dset     ;
   pair <set <Cdata, less<Cdata> > :: iterator, bool>
  iter     ;
   iterator <set <Cdata> >
  itt      ;
   // inserisci con chiave
   for( ic = 0 ; ic < 10 ; ic++ )
   {
     dat[ic].key = ( 20 + 2 * ic ) ;
     dset.insert(dat[ic]) ;
   }
   // controlla se c'è
   for( ic = 0 ; ic < 200 ; ic++ )
   {
     probe.key = ic ;
     // qui scasina
     if(  dset.find(probe)  )
       printf("!!! TROVATO %5d\n",ic) ;
     else
       printf("        --  %5d\n",ic) ;
   }
}

oooooooooopppppppppsssss come non detto, sono riuscito
a mettere in piedi una cosa che funziona e ho capito
l'errore....

oooooooooopppppppppsssss come non detto, sono riuscito
a mettere in piedi una cosa che funziona e ho capito
l'errore.... Il bello č che la mia prima versione
dell'implementazione erano un paio di centinaia di
linee di codice, ora sono una decina. Sono senza
parole per il genio che č stato profuso nella STL,
ancora non riesco a crederci...

 ancora non riesco a crederci...
A volte la realtà è meglio della fantasia.
Buon lavoro!