[C] Confronto tra Hashtable e RB-Trees

[daniele_dll]

Hola a todos,

attualmente utilizzo in un applicativo delle double-linked list, principalmente perché mi interessava implementare il funzionamento e testarne il comportamento su campo, senza però esagerare con il carico.

Ora che ho verificato che la logica dell'applicativo e apposto ho necessità di ottimizzare il suo funzionamento. L'applicativo richiede attualmente due strutture dati:
- la prima è la configurazione, contenuta nel file sotto forma di

Blocco1
{
  Blocco2 // commento
  {
    Chiave1 valore
    /**
     * commento
     **/
  }
  
  Chiave2 valore
  # Commento
}

Chiave3 valore

Viene caricata all'inizio ed è poi leggibile tramite delle macro
TABLE_GET(config->table, "Blocco1.Blocco2.Chiave1")

- la seconda è un elenco di informazioni associati a chiavi contenenti due gruppi di IP/PORTA

Mentre la prima list è piccola e difficlmente può influire sulle performance dell'applicativo, la seconda può diventare veramente enorme soprattutto perché lavora tramite il modulo queue di netfilter con la conseguenza che a contenere decine di migliaia di elementi che devono essere ricercati in una frazione di secondo non ci vuole nulla.

Le hashtable sfruttano gli array, tramite un ridimensionamento dinamico che avviene quando la tabella raggiunge i limiti ed è di solito 1.5/1.7 grande rispetto alla dimensione della tabella attuale. Il cuore di un hashtable è principalmente la funzione di hashing. Di conseguenza se la funzione di hashing è scritta bene è in grado di rendere molto bene viceversa può trasformare il tutto in una killer application.

Dei Red-Black trees ... non so quasi niente a parte che sono un evoluzione dei binary trees, che come per i precedenti sconosco in gran parte, di conseguenza non posso fare paragoni tra le hashtable e gli rb-tree.

Tutto poi dipende dall'implementazione, ma effettivamente che differenza c'è a livello di performance (operazioni da effettuare) per cercare, eliminare, inserire un nodo?

E soprattutto, conoscete qualche libreria ottimizzata e performante che faccia bene il suo lavoro?

[king64]

Una volta ho provato questa e non era affatto malaccio . Saluti

[daniele_dll]

Originariamente inviato da king64
Una volta ho provato questa e non era affatto malaccio . Saluti

Ciao,

innanzi tutto grazie per il link, gli darò un occhio magari cosi inizio a capirci di più con questo tipo di alberi binari, però non avresti qualcosa di più recente? Certo, alla fin fine il lavoro è sempre quello immagino, però il codice risale a 15 anni fà ed immagino ci siano state delle evoluzioni negli algorittimi per gli alberi rb

grazie cmq!

[daniele_dll]

Se a qualcuno dovesserò interessare ho trovato queste:
- http://cprops.sourceforge.net/cp_hashtable.3.html
- http://cprops.sourceforge.net/cp_hashlist.3.html
- http://cprops.sourceforge.net/cp_rbtree.3.html

o, più in generale
- http://cprops.sourceforge.net/

Tra le altre cose c'è scritto che il codice è sviluppato per lavorare in ambiente multi-thread, ergo il codice è thread-safe, che è moltooo buono

Qualcuno c'ha avuto a che fare con questa libreria?