Acelerando el código python con cython.

Tengo una función que básicamente hace muchas llamadas a una función hash definida simple y prueba para ver cuándo encuentra un duplicado. Tengo que hacer muchas simulaciones con él, así que me gustaría que fuera lo más rápido posible. Estoy tratando de usar cython para hacer esto. El código de cython se llama actualmente con una lista normal de python de enteros con valores en el rango de 0 a m ^ 2.

import math, random cdef int a,b,c,d,m,pos,value, cyclelimit, nohashcalls def h3(int a,int b,int c,int d, int m,int x): return (a*x**2 + b*x+c) %m def floyd(inputx): dupefound, nohashcalls = (0,0) m = len(inputx) loops = int(m*math.log(m)) for loopno in xrange(loops): if (dupefound == 1): break a = random.randrange(m) b = random.randrange(m) c = random.randrange(m) d = random.randrange(m) pos = random.randrange(m) value = inputx[pos] listofpos = [0] * m listofpos[pos] = 1 setofvalues = set([value]) cyclelimit = int(math.sqrt(m)) for j in xrange(cyclelimit): pos = h3(a,b, c,d, m, inputx[pos]) nohashcalls += 1 if (inputx[pos] in setofvalues): if (listofpos[pos]==1): dupefound = 0 else: dupefound = 1 print "Duplicate found at position", pos, " and value", inputx[pos] break listofpos[pos] = 1 setofvalues.add(inputx[pos]) return dupefound, nohashcalls 

¿Cómo puedo convertir inputx y listofpos para utilizar matrices de tipo C y acceder a las matrices a velocidad C? ¿Hay otras aceleraciones que pueda usar? ¿Se pueden acelerar los valores de conjunto?

Para que haya algo con lo que comparar, 50 llamadas a floyd () con m = 5000 actualmente toman alrededor de 30 segundos en mi computadora.

Actualización: Fragmento de código de ejemplo para mostrar cómo se llama a floyd.

 m = 5000 inputx = random.sample(xrange(m**2), m) (dupefound, nohashcalls) = edcython.floyd(inputx) 

En primer lugar, parece que debe escribir las variables dentro de la función. Un buen ejemplo de ello está aquí.

En segundo lugar, cython -a , para “anotar”, le brinda un excelente desglose del código generado por el comstackdor de cython y una indicación codificada por colores de lo sucia (lea: python api heavy). Esta salida es realmente esencial cuando se trata de optimizar cualquier cosa.

En tercer lugar, la ahora famosa página sobre cómo trabajar con Numpy explica cómo obtener acceso rápido y de estilo C a los datos de la matriz de Numpy. Desafortunadamente es verboso y molesto. Sin embargo, estamos de suerte, porque Cython más reciente proporciona vistas de memoria mecanografiada , que son fáciles de usar y asombrosas . Lea toda la página antes de intentar hacer otra cosa.

Después de diez minutos más o menos, se me ocurrió esto:

 # cython: infer_types=True # Use the C math library to avoid Python overhead. from libc cimport math # For boundscheck below. import cython # We're lazy so we'll let Numpy handle our array memory management. import numpy as np # You would normally also import the Numpy pxd to get faster access to the Numpy # API, but it requires some fancier comstacktion options so I'll leave it out for # this demo. # cimport numpy as np import random # This is a small function that doesn't need to be exposed to Python at all. Use # `cdef` instead of `def` and inline it. cdef inline int h3(int a,int b,int c,int d, int m,int x): return (a*x**2 + b*x+c) % m # If we want to live fast and dangerously, we tell cython not to check our array # indices for IndexErrors. This means we CAN overrun our array and crash the # program or screw up our stack. Use with caution. Profiling suggests that we # aren't gaining anything in this case so I leave it on for safety. # @cython.boundscheck(False) # `cpdef` so that calling this function from another Cython (or C) function can # skip the Python function call overhead, while still allowing us to use it from # Python. cpdef floyd(int[:] inputx): # Type the variables in the scope of the function. cdef int a,b,c,d, value, cyclelimit cdef unsigned int dupefound = 0 cdef unsigned int nohashcalls = 0 cdef unsigned int loopno, pos, j # `m` has type int because inputx is already a Cython memory view and # `infer-types` is on. m = inputx.shape[0] cdef unsigned int loops = int(m*math.log(m)) # Again using the memory view, but letting Numpy allocate an array of zeros. cdef int[:] listofpos = np.zeros(m, dtype=np.int32) # Keep this random sampling out of the loop cdef int[:, :] randoms = np.random.randint(0, m, (loops, 5)).astype(np.int32) for loopno in range(loops): if (dupefound == 1): break # From our precomputed array a = randoms[loopno, 0] b = randoms[loopno, 1] c = randoms[loopno, 2] d = randoms[loopno, 3] pos = randoms[loopno, 4] value = inputx[pos] # Unforunately, Memory View does not support "vectorized" operations # like standard Numpy arrays. Otherwise we'd use listofpos *= 0 here. for j in range(m): listofpos[j] = 0 listofpos[pos] = 1 setofvalues = set((value,)) cyclelimit = int(math.sqrt(m)) for j in range(cyclelimit): pos = h3(a, b, c, d, m, inputx[pos]) nohashcalls += 1 if (inputx[pos] in setofvalues): if (listofpos[pos]==1): dupefound = 0 else: dupefound = 1 print "Duplicate found at position", pos, " and value", inputx[pos] break listofpos[pos] = 1 setofvalues.add(inputx[pos]) return dupefound, nohashcalls 

No hay trucos aquí que no estén explicados en docs.cython.org , que es donde los aprendí yo mismo, pero ayuda a que todo se junte.

Los cambios más importantes en su código original están en los comentarios, pero todos ellos equivalen a dar sugerencias a Cython sobre cómo generar código que no use la API de Python.

Como infer_types aparte: realmente no sé por qué infer_types no está infer_types forma predeterminada. Permite que el comstackdor utilice implícitamente los tipos C en lugar de los tipos Python cuando sea posible, lo que significa que menos trabajo para usted.

Si ejecuta cython -a en esto, verá que las únicas líneas que llaman a Python son sus llamadas a random.sample, y la creación o adición a un conjunto de Python ().

En mi máquina, su código original se ejecuta en 2.1 segundos. Mi versión se ejecuta en 0,6 segundos.

El siguiente paso es obtener random.sample fuera de ese bucle, pero te lo dejo a ti.

He editado mi respuesta para demostrar cómo precomputar las muestras de rand. Esto reduce el tiempo a 0,4 segundos .

¿Necesitas usar este algoritmo de hash en particular? ¿Por qué no usar el algoritmo de hash incorporado para los dictados? Por ejemplo:

 from collections import Counter cnt = Counter(inputx) dupes = [k for k, v in cnt.iteritems() if v > 1]