使用cython加速python代码

Question

我有一个函数，它基本上对很多简单定义的哈希函数进行调用，并测试它是否发现重复。我需要用它做很多模拟，所以希望它尽可能快。我正在尝试使用cython来做到这一点。 cython代码当前使用一个普通的python整数列表调用，其值在0到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 

如何将inputx和listofpos转换为使用C类型数组并以C速度访问数组？有没有其他的速度可以使用？ setofvalues可以加快吗？

因此，有一点可以与之比较，在m = 5000时调用floyd（）的50个调用当前大约需要30秒。

更新：示例代码片段，以显示如何调用floyd。

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

Answer 1

首先，似乎你必须键入内函数变量。 A good example of it is here.

二，cython -a为“注释”，给你一个非常优秀的细分cython编译器生成的代码和一个颜色代码表明它是多么脏（读：python api重）。在尝试优化任何事情时，这个输出是非常重要的。

第三，working with Numpy上现在着名的页面解释了如何获得对Numpy阵列数据的快速C风格访问。不幸的是它冗长而烦人。不过，我们很幸运，因为最近的Cython提供了Typed Memory Views，这两个都很容易使用，真棒。在尝试做其他事情之前，请先阅读整个页面。

十多分钟左右，我想出了这个：

# 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 compilation 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 

这里没有技巧，没有上docs.cython.org解释，这是我学会了他们自己，但有助于看到这一切来一起。

对原始代码的最重要更改在注释中，但它们都等于给出有关如何生成不使用Python API的代码的Cython提示。

顺便说一句：我真的不知道为什么infer_types默认情况下不会启用。它可以让编译器 在可能的情况下隐式使用C类型而不是Python类型，这意味着更少的工作。

如果您在此上运行cython -a，您会看到调用Python的唯一行是您对random.sample的调用，以及构建或添加到Python集合（）。

在我的机器上，您的原始代码在2.1秒内运行。我的版本在0.6秒内运行。

下一步是从random循环中取出random.sample，但我会把它留给你。

我已经编辑我的答案来说明如何预先计算兰特样本。这带来的时间缩短到0.4秒。

Answer 2

您是否需要使用此特定的哈希算法？为什么不使用内置的散列算法来实现字典？例如：

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