素数测试 Python C 扩展比纯 Python 慢

Question

我已经在 C 扩展和纯 Python 代码中实现了一个 6k+-1 primality test 函数，但看起来纯 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 倍。

素数测试 Python C 扩展比纯 Python 慢

Primality test Python C extension is slower than pure Python

c

python

performance