首先，您似乎必须在函数内键入变量。一个很好的例子是here。
其次，cython -a对于“注释”，您可以对 cython 编译器生成的代码进行非常出色的分解，并以颜色编码指示它有多脏（阅读：python api 重）。在尝试优化任何东西时，此输出非常重要。
第三，关于使用 Numpy的著名页面解释了如何以 C 风格快速访问 Numpy 数组数据。不幸的是，它冗长而烦人。然而，我们很幸运，因为最近的 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上解释的技巧，这是我自己学习的地方，但有助于看到它们融合在一起。
对原始代码的最重要更改在注释中，但它们都相当于向 Cython 提供有关如何生成不使用 Python API 的代码的提示。
顺便说一句：我真的不知道为什么infer_types默认情况下不启用。它允许编译器在可能的情况下隐式使用 C 类型而不是 Python 类型，这意味着更少的工作量。
如果您cython -a在此运行，您将看到调用 Python 的唯一行是您对 random.sample 的调用，以及构建或添加到 Python set()。
在我的机器上，您的原始代码在 2.1 秒内运行。我的版本在 0.6 秒内运行。
下一步是让 random.sample 退出该循环，但我将把它留给你。
我已经编辑了我的答案以演示如何预先计算 rand 样本。这将时间缩短到0.4 秒。