Número Bacon v2.0

Molt prompte tindré preparada la versió 2.0 del programeta que calculava el Número de Bacon, que va sorgir a partir d’un repte de l’assignatura de Programació l’any passat (per saber més i conèixer detalls tècnics de la implementació anterior, visiteu la seva web).

Gràcies a aquest repte vaig poder aprendre un colló i part de l’altre l’any passat i amb aquest mateix objectiu he anat polint-lo i afegint-li característiques. Amb quines millores i característiques compta aquesta versió respecte l’anterior?

Optimització del graf.

Els vèrtex del graf són tant les pel·lícules com els actors i no únicament els actors com passava en la versió anterior. D’aquesta manera, el número d’arestes que apareixen al inserir un actor nou en una pel·lícula creix linealment i no de forma quadràtica com passava abans. Em vaig treure de la barret una implementació per a un graf no dirigit que millorava en un 20% la implementació clàssica mitjançant llistes d’adjacència, però així i tot, el fet que el número d’arestes cresquera de forma quadràtica era una bomba de rellotgeria. Ara, l’espai ocupat pel graf en memòria és molt menor (els que enteneu d’açò ja sabeu quina és la diferència entre un creixement quadràtic i un altre lineal…).

Per a que ens fem una idea, en la versió anterior havia de filtrar les pel·lícules i els actors quan es creava el graf per a que aquest no ocupara més memòria de la disponible en la computadora. Filtrant les pel·lícules per a adults, sèries de televisió, telenotícies, entregues de premis (Oscar, Grammy, etc) i moltes més coses, el graf ocupava vora 1,5GB de memòria principal. Ara, sense cap tipus de filtre ocupa uns 950MB!

Dues connotacions que té la millora de la representació del graf és el temps que tarda en generar-se i en carregar-se aquest. Abans havia de dedicar HORES a generar-lo en un fitxer i després MINUTS per carregar-lo en memòria cada vegada que s’executava el programa. Ara en uns 40 SEGONS (sense cap tipus d’optimització del nostre amic el GCC) el programa està carregat en memòria i llest per funcionar. Tornem de nou a la diferència entre un cost O(n) i un cost O(n^2).

Optimització de les taules hash.

Ara s’utilitzen funcions hash que ofereixen una millor dispersió i per tant el temps de recerca en la taula és menor. A més no s’utilitzen una, sinó dues funcions de dispersió. La primera serveix per dispersar l’element entre les cubetes de la taula i la segona per comparar els elements dins la cubeta, de forma que el element que s’està buscant es compara amb la resta de la seva cubeta amb un enter (cost constant) evitant així tenir que fer comparacions de strings (amb un pitjor cas amb cost lineal).

De totes formes, la idea és substituir les taules de dispersió en un futur per unes altres que oferisquen major tolerància a fallades d’escriptura (Fuzzy string searching) en detriment de l’eficiència. Per aquest cas, ens dóna igual un cost O(1) que un cost O(log n) i el segon ens ofereix algunes avantatges.

La idea és aconseguir el que fa Google quan t’equivoques escrivint però has escrit una cosa semblant a algun índex que tenen en la seva memòria cau. Per exemple, si busqueu al Google “el vol de lhome ocell” us apareixerà: “Did you mean? el vol de l’home ocell“. El mateix vull fer jo per si algú s’equivoca i busca “Kevin Bakon” o “Qevin Vacon“, que li aparega “Volies dir Kevin Bacon?“.

Lamentablement per fer tot això ens clavem en el meravellós món de la programació dinàmica i altres tècniques i estructures de dades avançades de les quals jo no tinc ni punyetera idea, així que això haurà de ser en paciència.

Optimització del càlcul del camí de menor pes entre dos vèrtex del graf.

Quan vaig fer el programa per primera vegada vaig utilitzar l’algorisme de Dijkstra. Havia sentit parlar d’ell en EMI1, així que quan vaig veure que els actors eren vèrtex d’un graf i “El Número Bacon” era el camí de menor pes entre l’actor indicat i Kevin Bacon, em vaig tirar de cap. Greu error. Perquè si hagués investigat un poc més abans de pegar-me la gran currada hauria descobert que l’algorisme de Recerca per Amplada (o Breadth-First Search en anglès, que queda més cool) també permet calcular el camí de menor pes en un graf no ponderat (o amb tots els pesos igual a 1), que era el que jo tenia, i en un temps molt menor.

La implementació habitual de l’algorisme de Dijkstra té un cost en el pitjor cas d’ordre quadràtic (O(V^2)), inacceptable per a la dimensió del graf del meu problema. Per això vaig trobar una implementació que utilitzava monticles de mínims (MinHeaps) per elegir el pròxim vèrtex a visitar i reduïa el cost a O((V+E)*Log(V)). Tenint en compte que el número d’arestes (E) era bastant major que V (però no arribava a V^2), llavors el cost era O(E*Log(V)), que no estava malament. Però la Recerca per Amplada, per a aquest cas, li pega cent voltes al de Dijkstra, ja que calcula el camí de menor pes en un temps O(E+V), en el nostre cas O(E) (ja que E >> V)!

Oracle.

Aquesta és la millor característica de cara a l’usuari. He construït un servidor utilitzant Sockets i Threads (mai havia utilitzat cap dels dos en C o C++, únicament en Python i Delphi) al qual se li poden enviar consultes de l’estil “link?n1=Bacon, Kevin&n2=Connery, Sean” i el servidor torna al client la distància entre els dos actors i el camí que hi ha que recórrer. A més se li poden passar filtres per buscar el camí únicament entre les pel·lícules que corresponen a un cert gènere, o que estiguen dintre d’un rang temporal, etc.

Què és pretén amb això? Doncs executar aquest servidor des del meu servidor casolà (s’anomena asimov) i fer una xicoteta pàgina web des de la qual poder enviar consultes (més o menys el que fa la web http://www.oracleofbacon.org), però també podria implementar-se en qualsevol plataforma connectada a la xarxa (una versió mòbil?). Ja especificaré millor com funciona el servidor en la documentació del programa, em queda corregir unes cosetes.

En definitiva, per a que veieu que no us mentisc, ací us deixe amb una xicoteta captura de pantalla del servidor amb tres clients connectats i els recursos que està consumint.

Vista prèvia del servidor amb tres clients connectats

En fi, ja us contaré més coses!

PS: Els qui m’heu vist cansat avui, per culpa de la frikada aquesta anit em vaig gitar mooolt tard…

PS2: Jo NO he fet la web http://www.oracleofbacon.org. He fet un servidor que és el primer pas per poder fer una web com aquesta.