Hashtable e sorting

Se avete dubbi o domande sulla programmazione in generale, fatele qui
Rispondi
ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 16 luglio 2010, 17:30

La domanda e' piuttosto generica e riguarda sostanzialmente la necessita' di "analizzare", periodicamente, i dati contenuti in una hashtable in modo da ordinarli secondo criteri differenti.
Per entrare maggiormente nel merito... ho un hashtable nella quale memorizzo pacchetti TCP (La chiave viene calcolata sugli indirizzi IP + porte TCP) e ad intervalli regolari ho necessita' di scandire i pacchetti presenti nella tabella e trarne dei "risultati".
Ad esempio: l'indirizzo IP che risulta aver generato il maggior numero di pacchetti, la porta TCP target utilizzata con maggiore frequenza, etc., etc.

Ora... non essendo "possibile" ordinare la tabella ho bisogno di un approccio opportuno che mi permetta di estrapolare le informazioni di mio interesse e di poterle visualizzare/stampare secondo i criteri desiderati.

Quale potrebbe essere un approccio non troppo complesso che riduca il piu' possibile l'attivita' svolta da ogni thread (Supposto di avere, ad esempio, un thread che ad ogni intervallo di tempo si occupa di un certo criterio di ordinamento) ?
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

aleph
Robin Hood
Messaggi: 1530
Iscritto il: 12 febbraio 2008, 16:30
Contatta:

Messaggio da aleph » 16 luglio 2010, 20:00

la soluzione più semplice è usare, invece dell'hashtable, un'idiotissima lista (ordinata in ordine cronologico) e fare le ricerche su questa . .

se i tipi di ricerche da fare sono relativamente pochi, puoi usare una struttura dati differente per ogni campo coinvolto, inserendo ogni nuovo pacchetto in ogni struttura (cioè tieni più copie dell'intero set di pacchetti, ogni copia ordinata secondo un valore differente) . . ovviamente moltiplichi lo spazio necessario e il costo all'inserimento di nuovi pacchetti, in compenso le ricerche sono ottimizzate al meglio . .

poi dipende anche dal linguaggio/framework che usi, in un linguaggio ad alto livello farei una struttura modulare che di base usa un sistema semplice ma permette di aggiungere componenti che ottimizzano analisi più complesse . .
ImmagineOutside of a dog, computers are a man's best friend, inside a dog it's too dark to type.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 17 luglio 2010, 9:36

Se sono partito dal fatto che memorizzo in una hashtable c'e' un motivo.

Altrimenti non mi sarei posto il problema o per lo meno non me lo sarei posto in questi termini.
La presenza della tabella hash e' necessaria in quanto devo raggruppare i dati per "flussi" secondo certi parametri (Quelli che determinano la chiave).

Le ricerche avvengono ripetutamente ad intervalli di, diciamo, pochi minuti e probabilmente secondo 4/5 criteri differenti (Pertanto 4/5 ricerche "distinte" alla volta).
L'implementazione avviene in C.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Sawk
Arciere
Messaggi: 217
Iscritto il: 13 gennaio 2008, 17:27

Messaggio da Sawk » 17 luglio 2010, 10:29

ho implementato un codice simile e ti consiglio il perl. Le prestazioni sono praticamente identiche e le sue hashtable (utilizzabili in modo molto diverso rispetto al C) aiutano decisamente molto:
Ad esempio:

Codice: Seleziona tutto

$numero_connessioni{ $ip }++
aggiunge 1 al valore della chiave $ip ogni volta che l'ip specificato da $ip si ripresenta (o si presenta per la prima volta). Niente dichiarazioni o altro. Non più di 100 righe di codice.

Se invece vuoi implementare tutto in C, la cosa diventa decisamente più lunga. Le hash table non vanno bene perché:
- l'uso degli hash ha senso in casi particolari. Per un programma come questo dovrai gestire le collisioni, quindi liste concatenate. Tanto vale organizzare le strutture dati in modo da non avere tempo quadratico di ricerca delle informazioni, e non dover gestire codici per la generazione delle chiavi (base64 o quello che è)
- usare l'ordinamento su hashtable non è una buona idea. Le hashtable non sono pensate per essere strutture ordinate (il nome esprime questo concetto). In generale potresti avere dei notevoli rallentamenti nel programma, o comunque delle complicazioni.

Quindi liste concatenate, come aleph ha suggerito, è la migliore soluzione al tuo problema. Non è vero che in questo caso c'è la necessità di avere delle hash table. Sarà sufficiente gestire le liste di struct in modo opportuno. Magari con un array di liste.

Poi un piccolo db può (ripeto "può") semplificare notevolmente le cose e scaricare tutta l'organizzazione dei dati direttamente su questo. La parte organizzativa e applicativa la mantieni nel programma. Potrai fare TUTTE le operazioni di qualunque tipo sui dati: ordinamento, visualizzazione dati di un certo tipo, etc.. Chiaramente è solo una idea. Non è assolutamente necessario. Si tratta di non più di 2 tabelle.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 17 luglio 2010, 11:18

Allorra... apprezzo le tue considerazioni, sensate ed interessanti ma il problema non e' questo.
Il fatto che io utilizzi il C e' un requisito e non si scappa.
Analogamente per quanto riguarda il fatto che i dati vengano memorizzati in una tabelle hash:
- la tabella deve contenere flussi, e' necessario che l'inserzione avvenga il piu' velocemente possibile e che ad ogni entry corrisponda un flusso differente
- l'attivita' di ricerca/analisi e' una attivita' collaterale che DEVE partire dal presupposto di dover lavorare su una struttura gia' testata e funzionante (Le collisioni non sono un problema, in questo contesto)
- l'utilizzo di un db e' da escludere vista l'enorme quantita' di dati che possono arrivare nell'unita' di tempo

Pertanto i miei dubbi riguardano principlamente/essenzialmente/unicamente il come affrontare l'analisi della tabella hash in modo da estrapolare i dati secondo un certo ordinamento.
Potrei utilizzare delle strutture "di supporto" (Liste, array o quant'altro) nelle quali memorizzare dei puntatori che facciano riferimento ai dati secondo il relativo criterio di ordinamente... ma so sinceramente se e quanto questo sia fattibile senza risultare eccessivamente complesso.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Sawk
Arciere
Messaggi: 217
Iscritto il: 13 gennaio 2008, 17:27

Messaggio da Sawk » 17 luglio 2010, 12:36

Un approccio all'utilizzo delle tabelle di hash è questo:

1) filtrare TUTTO il traffico inutile. Esempio: frammentazione dei pacchetti etc. Mantenere solo le informazioni utili sulla base di quello che ti interessa.

2) chiave = ind. ip. Meglio non usare anche la porta usata (es: chiave = 127.0.0.1:3303) per non creare ridondanza tra le chiavi.

3) valore = lista concatenata relativa alle connessioni dell'ip. Ogni struct all'interno contiene: src_port, dst_port, conn_in (ora di connessione), conn_out (ora di termine), conn_time (durata connessione) tutte in formato epoch. Eventualmente altre informazioni: byte_trasferiti, etc... La lista è ordinata in senso crescente in base all'ora di connessione.

Procedura di inserimento: connessione => ip. Identifico la presenza della chiave (dell'ip) nella tabella. Se c'è già, aggiungo un elemento alla coda della lista con le info relative, altrimenti creo una nuova chiave e inserisco l'elemento nella nuova lista associata al suo valore. Tempo di esecuzione lineare rispetto il numero di chiavi memorizzate.

Ordinamento secondo quali parametri ? Per qualunque informazione associata ad un ip, una possibilità è: identifico chiave, applico un algoritmo di ordinamento (meglio mergesort/quicksort) sui dati all'interno della lista che mi interessano (devono essere numerici).

Immagina di avere 200 ind ip e in media 1000 connessioni per ciascuno, che è un caso abbastanza reale. (tralascio i calcoli delle complessità) Il numero di operazioni è ~2 milioni. Un calcolatore attuale non ha grossi problemi con una complessità simile.

Howl
Arciere Provetto
Messaggi: 435
Iscritto il: 28 luglio 2008, 19:32

Messaggio da Howl » 17 luglio 2010, 13:35

ArchGuy ha scritto:Potrei utilizzare delle strutture "di supporto" (Liste, array o quant'altro) nelle quali memorizzare dei puntatori che facciano riferimento ai dati secondo il relativo criterio di ordinamente...
Ma in questo modo ogni volta che inserisci un nuovo elemento (o modifichi uno già esistente, non so se nel tuo caso ciò possa accadere o meno) nella hash table dovresti modificare anche le varie strutture ordinate associate e questa operazione costa almeno un tempo logaritmico. Quindi ti ritroveresti con una hash table lenta quanto una struttura ordinata.
Se (e solo se) puoi raccogliere tutti i dati in un unico array (non sempre si ha spazio libero contiguo sufficiente per contenerlo), forse conviene memorizzare tutti i dati in questo array e far puntare le liste della tabella hash ad esso. Conserveresti quindi la tabella hash, con le varie liste, però i dati sarebbero tutto memorizzati in un unico array su cui eseguiresti di volta in volta l'ordinamento richiesto in nlogn.
Ogni nuovo elemento lo inserisci quindi in fondo all'array e poi calcoli la lista della hash table a cui questo elemento va aggiunto e quindi lo aggiungi ad essa in coda.

EDIT: naturalmente se i tuoi elementi sono struct conviene costruirti un array di puntatori a struct, se no l'allocazione contigua può diventare veramente un problema. Se sai già il n° di elementi che dovrà contenere circa conviene inoltre sovradimensionare l'array piuttosto che ogni volta riallocare spazio mentre cresce dinamicamente.
Ultima modifica di Howl il 17 luglio 2010, 13:50, modificato 1 volta in totale.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 19 luglio 2010, 9:40

Howl ha scritto:
ArchGuy ha scritto:Potrei utilizzare delle strutture "di supporto" (Liste, array o quant'altro) nelle quali memorizzare dei puntatori che facciano riferimento ai dati secondo il relativo criterio di ordinamente...
Ma in questo modo ogni volta che inserisci un nuovo elemento (o modifichi uno già esistente, non so se nel tuo caso ciò possa accadere o meno) nella hash table dovresti modificare anche le varie strutture ordinate associate e questa operazione costa almeno un tempo logaritmico. Quindi ti ritroveresti con una hash table lenta quanto una struttura ordinata.
Se (e solo se) puoi raccogliere tutti i dati in un unico array (non sempre si ha spazio libero contiguo sufficiente per contenerlo), forse conviene memorizzare tutti i dati in questo array e far puntare le liste della tabella hash ad esso. Conserveresti quindi la tabella hash, con le varie liste, però i dati sarebbero tutto memorizzati in un unico array su cui eseguiresti di volta in volta l'ordinamento richiesto in nlogn.
Ogni nuovo elemento lo inserisci quindi in fondo all'array e poi calcoli la lista della hash table a cui questo elemento va aggiunto e quindi lo aggiungi ad essa in coda.

EDIT: naturalmente se i tuoi elementi sono struct conviene costruirti un array di puntatori a struct, se no l'allocazione contigua può diventare veramente un problema. Se sai già il n° di elementi che dovrà contenere circa conviene inoltre sovradimensionare l'array piuttosto che ogni volta riallocare spazio mentre cresce dinamicamente.
La hashtable non deve dipendere dall strutture "collaterali" ovviamente.
Semmai e' il contrario (Con conseguente possibilita' di corse critiche).
L'inserimento e la rimozione dei dati in tabella avviene regolarmente se non che in caso di modifiche durante l'intervallo occorrera', al momento della successiva fase di analisi, modificare la struttura di supporto in questione aggiornandone i puntatori.
Il problema, come gia' detto, e' che fare tutto cio' non so se e quanto sia piu' opportuno rispetto ad effettuare ogni volta un ordinamento agendo direttamente sulla hashtable, dopo averla eventualmente, "lockata".
La problematica dell'ordinamento da effettuare e' che ad esempio alcuni dei criteri da prendere in considerazione dipendono da una piccola parte dei "campi" che costituiscono il valore delle entry della tabella (La chiave viene calcolata in base a ind. mittente, ind. dest., porta mitt., porta dest. mentre il valore contiene dati quali numero di byte scambiati, protocollo utilizzato, data/ora inizio dello scambio dei dati, data invio/ricezione ultimo pacchetto, etc.) come ad esempio quello secondo il quale dovrei ordinare i flussi in ordine non crescente di numero di pacchetti scambiati.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 19 luglio 2010, 9:48

Sawk ha scritto:Un approccio all'utilizzo delle tabelle di hash è questo:

1) filtrare TUTTO il traffico inutile. Esempio: frammentazione dei pacchetti etc. Mantenere solo le informazioni utili sulla base di quello che ti interessa.

2) chiave = ind. ip. Meglio non usare anche la porta usata (es: chiave = 127.0.0.1:3303) per non creare ridondanza tra le chiavi.

3) valore = lista concatenata relativa alle connessioni dell'ip. Ogni struct all'interno contiene: src_port, dst_port, conn_in (ora di connessione), conn_out (ora di termine), conn_time (durata connessione) tutte in formato epoch. Eventualmente altre informazioni: byte_trasferiti, etc... La lista è ordinata in senso crescente in base all'ora di connessione.

Procedura di inserimento: connessione => ip. Identifico la presenza della chiave (dell'ip) nella tabella. Se c'è già, aggiungo un elemento alla coda della lista con le info relative, altrimenti creo una nuova chiave e inserisco l'elemento nella nuova lista associata al suo valore. Tempo di esecuzione lineare rispetto il numero di chiavi memorizzate.

Ordinamento secondo quali parametri ? Per qualunque informazione associata ad un ip, una possibilità è: identifico chiave, applico un algoritmo di ordinamento (meglio mergesort/quicksort) sui dati all'interno della lista che mi interessano (devono essere numerici).

Immagina di avere 200 ind ip e in media 1000 connessioni per ciascuno, che è un caso abbastanza reale. (tralascio i calcoli delle complessità) Il numero di operazioni è ~2 milioni. Un calcolatore attuale non ha grossi problemi con una complessità simile.
La chiave e' "forzata" a dover essere calcolata su indirizzo mittente, indirizzo destinazione, porta mittente, porta destinazione.
L'inserimento e la rimozione non devono essere in nessun modo influenzati dalle fasi di analisi dei dati ne' dalla natura delle eventuali strutture di supporto utilizzate.

Il tuo approccio sarebbe quindi quello di effettuare un ordinamento andando a lavorare direttamente sulla tabella ?
VOlendo effettuare un ordinamento in base ad un campo non chiave (Ad esempio... dimmi quale e' l'indirizzo che ha generato piu' traffico oppure dimmi quale e' l'indirizzo che ha ricevuto piu' dati oppure ordinami i flussi per data di inizio "scambio").

Dimenticato di dire che la tabella verra' "ripulita" ad intervalli di tempo regolari in funzione della data di inizio scambio dati (In modo da eliminare i dati meno recenti).
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Sawk
Arciere
Messaggi: 217
Iscritto il: 13 gennaio 2008, 17:27

Messaggio da Sawk » 19 luglio 2010, 11:47

per la chiave puoi usare la base64. Non sarà molto performante (dato che si tratta di confrontare stringhe) ma sicuramente funziona, ed è forse la cosa migliore per una chiave che comprende un insieme di elementi. Per vedere il risultato:

Codice: Seleziona tutto

echo "scrivi qualcosa" | base64
Al posto di "scrivi qualcosa" puoi mettere "127.0.0.1:4404.128.1.2.1:3409" e vedere che esce.
Ad ogni modo l'introduzione di una chiave simile rende laboriosa e abbastanza inutile l'implementazione di uno hash per il problema.

L'ordinamento che ho proposto viene fatto sulla tabella, ma senza alterare la posizione degli elementi nella lista. Semplicemente si tiene traccia in un array della posizione degli elementi rispetto certe loro proprietà:

Es sui byte scambiati:
elem. 1 -> 500B
elem. 2 -> 200B
elem. 3 -> 700B

Li ordino in senso crescente. L'array avrà indici associati al numero di elemento:
1 -> 2
2 -> 1
3 -> 3

Se ripeti questa procedura per tutte le chiavi dell'hash la complessità (in media) di esecuzione potrebbe essere cubica rispetto il numero di elementi per chiave.

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 19 luglio 2010, 11:56

Sawk ha scritto:per la chiave puoi usare la base64. Non sarà molto performante (dato che si tratta di confrontare stringhe) ma sicuramente funziona, ed è forse la cosa migliore per una chiave che comprende un insieme di elementi. Per vedere il risultato:

Codice: Seleziona tutto

echo "scrivi qualcosa" | base64
Al posto di "scrivi qualcosa" puoi mettere "127.0.0.1:4404.128.1.2.1:3409" e vedere che esce.
Ad ogni modo l'introduzione di una chiave simile rende laboriosa e abbastanza inutile l'implementazione di uno hash per il problema.

L'ordinamento che ho proposto viene fatto sulla tabella, ma senza alterare la posizione degli elementi nella lista. Semplicemente si tiene traccia in un array della posizione degli elementi rispetto certe loro proprietà:

Es sui byte scambiati:
elem. 1 -> 500B
elem. 2 -> 200B
elem. 3 -> 700B

Li ordino in senso crescente. L'array avrà indici associati al numero di elemento:
1 -> 2
2 -> 1
3 -> 3

Se ripeti questa procedura per tutte le chiavi dell'hash la complessità (in media) di esecuzione potrebbe essere cubica rispetto il numero di elementi per chiave.
Il calcolo della chiave viene fatto secondo una funziona di hashing "ad hoc" che dovrebbe "minimizzare" la possibilta' di collisioni.

Non ho sinceramente ben compreso come/cosa intendi per ordinare lavorando direttamente sulla tabella.
A me sembra che "vorresti", quando inserisci un elemento in tabella, memorizzarlo anche in una struttura di supporto secondo il criterio di ordinamento in questione facendo riferimento, anziche' alla chiave, ad uno o piu' campi del nuovo elemento.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Sawk
Arciere
Messaggi: 217
Iscritto il: 13 gennaio 2008, 17:27

Messaggio da Sawk » 19 luglio 2010, 15:28

memorizzi la posizione dell'elemento in un array. La posizione è determinata sulla base dell'ordinamento

ArchGuy
Little John
Messaggi: 1340
Iscritto il: 26 marzo 2009, 18:16
Località: Montignoso

Messaggio da ArchGuy » 19 luglio 2010, 18:16

Questo richiede un aggiornamento dell'array (O della struttura utlizzata come "supporto") ogni volta che inserisco un nuovo elemento in tabella hash o ogni volta che lo rimuovo.
E questo non voglio farlo visto che come gia' detto voglio che la fase di inserimento.rimozione dei dati sia del tutto indipendente dalla fase di "analisi".
A questo punto l'approccio piu' immediato sarebbe quello di iterare direttamente sugli elementi della tabella hash cosi' come sono stati inseriti ed utilizzarne i puntatori per effettuare, ad ogni intervallo di tempo, l'algoritmo di sorting in base al criterio di ordinamento scelto.
"La percezione è cieca se non è illuminata dalla ragione." (Gandhi)

Rispondi