原始性测试Python C扩展比纯Python慢

Question

我已经在C扩展和纯Python代码中实现了一个6k+-1素性测试函数，但纯Python代码似乎要快得多！我的C代码有什么问题吗？我还用is_prime函数在纯C中编译了一个类似的测试，它的执行时间与C扩展(几乎2秒(相同

primemodule.c

#define PY_SSIZE_T_CLEAN
#include "Python.h"
int is_prime(int n)
{
int i;
if (n <= 3)
return (n > 1);
if (n % 2 == 0 || n % 3 == 0)
return (0);
i = 5;
while ((i * i) <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
return (0);
i += 6;
}
return (1);
}
static PyObject *prime_isprime(PyObject *self, PyObject *args)
{
int n;
if (!PyArg_ParseTuple(args, "i", &n))
return (NULL);
if (is_prime(n))
Py_RETURN_TRUE;
Py_RETURN_FALSE;
}
static PyMethodDef prime_methods[] = {
{"is_prime", prime_isprime, METH_VARARGS, "Check if a number is prime"},
{NULL, NULL, 0, NULL}};
static struct PyModuleDef prime_module = {
PyModuleDef_HEAD_INIT,
"prime",
NULL,
-1,
prime_methods};
PyMODINIT_FUNC PyInit_prime(void)
{
return (PyModule_Create(&prime_module));
}

py_test.py

import time
MAX_INT = 2147483647
def is_prime(n: int) -> bool:
if n <= 3:
return n > 1
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i ** 2 <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True
t1 = time.process_time()
for i in range(MAX_INT - 100, MAX_INT):
is_prime(i)

print(time.process_time() - t1, "seconds")

c_test.py

import time
import prime
MAX_INT = 2147483647
t1 = time.process_time()
for i in range(MAX_INT - 100, MAX_INT):
prime.is_prime(i)

print(time.process_time() - t1, "seconds")

python c_test.py

2.078125 seconds

python py_test.py

0.03125 seconds

timecmd.bat a.exe

2.13 seconds

Answer 1

我认为您的C实现在整数溢出和有符号性方面存在缺陷，最终会出现比Python版本更大的循环。

将参数类型更改为unsigned int(以及i，因为否则将是编译器警告(：

static int is_prime(unsigned int n)
{
unsigned int i;
if (n <= 3)
return (n > 1);
if (n == 2 || n == 3)
return (1);
if (n % 2 == 0 || n % 3 == 0)
return (0);
i = 5;
while ((i * i) <= n)
{
if (n % i == 0 || n % (i + 2) == 0)
return (0);
i += 6;
}
return (1);
}

使它(在我的机器上，大约(比Python实现快37倍。