El blog de Trespams

[ x ]

Faig servir les cookies de Google Analytics per al control de visites i estadístiques..
És una pardalada, però la llei diu que us he d'avisar, ja veus. Així que si visitau aquest blog donau-vos per informats o sortiu ara mateix i netejau les cookies del vostre navegador. Si continuau llegint, suposaré que ja us està bé. Si vols saber com llevar les cookies del teu navegador: aquí ho pots trobar

A la pregunta de Servo ....

Al comentari del darrer apunt de Servo es demanava el perquè el Set hauria de ser més ràpid si el primer algorisme és d'ordre N.

El codi dels sets es molt semblant al dels diccionaris, però està una mica més optimitzat, a l'igual que els diccionaris està implementat com una taula hash, però a diferència d'aquests els conjunts sols guarden el parell clau/hash en lloc de la tripleta clau/valor/valor del diccionari.

Com que els sets guarden els parells clau/hash, totes les operacions binàries, com la intersecció s'executen sense cap cridada al mètode _ _hash__ dels elements individuals. Això és molt més ràpid que el codi equivalent que fa servir diccionaris.

També resulta que quan feim un bucle damunt un set Python (CPython) directament recorre la taula hash en lloc de fer ús d'un iterador (que seria un poc més lent).

La pregunta ha servit per fer un poc de recerca, de fet la meva resposta és la traducció d'una resposta molt completa l'he trobada a Python in Science .

Però no ens conformem amb això, fem un "show me the code" a la plana citada anteriorment hi ha un exemple que ens anirà bé per començar. Es tracta de trobar la intersecció de dos conjunts, però ho podem adaptar per fer les cerques al diccionari:


import random
import time
REPETICIONS = 1000

## Generam els valors
seta = set([random.randint(0,100000) for n in xrange(10000)])
setb = set([random.randint(0,100000) for n in xrange(10000)])

print "Cerques a conjunts"

t0 = time.clock()
    for i in xrange(REPETICIONS):
    total = seta.intersection(setb)
print "Intersections - Time: %s seconds"%(time.clock()-t0)

t0 = time.clock()
for i in xrange(REPETICIONS):
    total2 = []
    for element in seta:
        if element in setb:
            total2.append(element)
print "Fent el bucle Time: %s seconds"%(time.clock()-t0)

## I ara el nostre cas

print "Cerques amb diccionaris"

## Generam els valors
dicta = {}
dictb = {}
for i in xrange(10000):
    dicta[random.randint(0,100000)]=i
    dictb[random.randint(0,100000)]=i

t0 = time.clock()
for x in xrange(REPETICIONS):
    total2 = []
    for valor in dicta.keys():
         if dictb.get(valor):
            total2.append((valor, dicta[valor]))

print "Bucle - Time: %s seconds"%(time.clock()-t0)

t0 = time.clock()
for x in xrange(REPETICIONS):
    total2 = [ (repe,dicta[repe]) for repe in   set(dicta).intersection(set(dictb))]

print "Set intersection - Time: %s seconds"%(time.clock()-t0)

I aquí el resultat


Cerques a conjunts
Intersections - Time: 0.94 seconds
Fent el bucle Time: 6.11 seconds
Cerques amb diccionaris
Bucle - Time: 11.63 seconds
Set intersection - Time: 6.97 seconds

En el primer cas estam davant un algorisme d'ordre N² davant un algorisme NlogN sin o record malament de la intersecció de conjunts.

El nostre cas és una mica menys clar en el que fa a l'ordre de l'algorisme, però amb el codi es pot veure com el resultat final s'obté és un 60% més ràpid.

Tot i això fixem-nos amb que per a obtenir el resultat en segons he tingut que fer 1.000 iteracions i que hem fet servir un conjunt de 10.000 elements, sols per a que quedi clar de que potser ambdós algorismes són prou ràpids per a la nostra tasca diària. Sols hem de tenir clar que quan cerquem maneres d'optimitzar el nostre codi, mirar si feim aquests tipus d'algorismes moltes vegades

blog comments powered by Disqus
<<<<<<< main/templates/puput/base.html ======= >>>>>>> main/templates/puput/base.html