El Blog de Trespams

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