<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">2013/12/17 Pietro Battiston <span dir="ltr"><<a href="mailto:me@pietrobattiston.it" target="_blank">me@pietrobattiston.it</a>></span><br><div>

 </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Ma in generale sono dati estremamente semplici - in alcuni<br>
casi ad ogni chiave è associata una breve stringa, in altri una lista di<br>
brevi stringhe, in altri un piccolo dizionario i cui valori sono brevi<br>
stringhe (insomma, tutti tipi perfettamente supportati da Redis). Ad<br>
esempio un set di dati che utilizzo è la descrizione di una rete. Quindi<br>
la struttura base è un semplice dizionario<br>
<br>
{ "elemento1" : ["elemento53", "elemento114", "elemento54"],<br>
  "elemento2" : ["elemento1", "elemento32"],<br>
... }<br>
<br>
Io ho bisogno di rispondere in modo più veloce possibile alla domanda "a<br>
chi è collegato elementox?".</blockquote><div><br></div><div>Ho chiacchierato ampiamente di queste cose ad Europython. Comunque preparati a soffrire veramente tanto se i dati sono tanti, tu non ti mangi teoria dei grafi a colazione *e* hai un'ottima comprensione di tutto lo stack software che usi.</div>

<div><br></div><div>Cioe', gia' la rappresentazione che scegli la sopra, intendiamoci, o Python riesce ad internare tutte quelle stringhe (e se hai facile facile 1 milione di nodi sarebbero cazzi comunque)… vuoi scoprire se due nodi sono lo stesso nodo? Un confronto che potrebbe essere fatto in un'operazione, deve invece confrontare stringhe con prefisso comune.</div>

<div><br></div><div>Se poi invece di vuoler scoprire a chi e' collegato 1, vuoi scoprire se 1 e 42 sono collegati… buona fortuna! Paga O(n) per qualcosa che potrebbe essere O(1). Vedi la classica rappresentazione dei grafi in Python. Vedi anche la mia presentazione ad EP2013 per vedere come stanno le cose in memoria e il dolore che ti porti appresso a quando cominci a nestare liberalmente strutture dati. </div>

<div><br></div><div>Il che si risolve in:</div><div>1) passi a teoria algebrica dei grafi e ti smanacci matrici sparse (facile -- se sei forte in algebra -- efficiente, veloce, ma non scala indefinitivamente -- a meno che tu non abbia sistemi per fare calcolo distribuito su anelli arbitrari di matrici, cosa che noi iniziammo a costruire e non finimmo realmente, e che non mi risulta esista altrove)</div>

<div><br></div><div>2) cerchi di cominciare in termini di map-reduce e hai qualcuno che ti sostiene tale infrastruttura (non vuoi davvero mettere su e tenere in piedi dei cluster)</div><div><br></div><div>3) ti rendi conto che map-reduce per problemi sui grafi non funziona sempre troppo bene, e guardi a qualche implementazione di Pregel… buona fortuna qui</div>

<div><br></div><div>4) provi a vedere se qualche nosql graph db funziona per le tue cose, se no provi a simularlo con qualcosa di diverso -- anche relazionale, altro che denormalizzato! -- Poi e' noto che query SQL per esprimere cose sui grafi sono un dolore veramente grosso, ma non e' che denormalizzando il dolore passa, aumenta, semmai.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Veniamo al problema 2: dopo che ho fatto tutte le analisi che devo fare<br>
sul dizionario tipo quello descritto sopra, devo spostare la mia<br>
attenzione ad un altro dizionario. Diciamo che la dimensione di ognuno<br>
di questi dizionari è dell'ordine di grandezza di 1-2 GB, e di RAM<br>
disponibile, inclusa quella che uso per il sistema, ne ho 5 GB. Quindi:<br>
faccio il flush del database Redis, carico la descrizione del nuovo<br>
dizionario.<br></blockquote><div><br></div><div>Ma allora e' roba piccola piccola! Non ci sono problemi.</div><div>Se poi lo passi invece che in strutture orribilmente ridondanti a qualcosa di compatto tipo una matrice sparsa, vedi che la RAM ti droppa drasticamente. Scegli le strutture dati opportune, prima di metterti in mezzo con strumenti relativamente complicati.</div>

<div> </div></div>-- <br> .<br>..: -enrico-
</div></div>