- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

Python调用C语言实现数独计算逻辑提速100倍

云端小宅女发表于 2021/07/27 17:33:20 2021/07/27

【摘要】完全不会C/C++的我，想到能否将计算逻辑用C语言或go语言重写后，交给Python调用实现程序性能的进一步优化。经过几十次瞎尝试，顺利用Python调用了c语言编写的计算逻辑，成功将程序优化到耗时1毫秒以内。后面也尝试了python调用go语言，但是不知道如何通过python生成[]byte的splice对象，只好宣步失败，也说明python借助ctypes调用go语言并不是那么随心所欲，还是直

之前我们实现python自动玩数独游戏，详见：《让程序自动玩数独游戏让你秒变骨灰级数独玩家》

链接：https://blog.csdn.net/as604049322/article/details/118583461

最终达到了这样的效果：

中间我们将一个超难的数独，程序计算耗时由17秒优化到3秒，有读者希望将计算数独的逻辑用C++改写一遍重发。

完全不会C/C++的我，想到能否将计算逻辑用C语言或go语言重写后，交给Python调用实现程序性能的进一步优化。经过几十次瞎尝试，顺利用Python调用了c语言编写的计算逻辑，成功将程序优化到耗时1毫秒以内。后面也尝试了python调用go语言，但是不知道如何通过python生成[]byte的splice对象，只好宣步失败，也说明python借助ctypes调用go语言并不是那么随心所欲，还是直接调用c语言来的方便。

下面看看python调用c语言的操作流程：

Python调用c语言

下载gcc编译工具

作为非专业人士用MinGW就够了，官方下载地址是：https://sourceforge.net/projects/mingw-w64/

百度云下载地址：
https://pan.baidu.com/s/1ZmjQUf5QcBbeHCi7mIrYxg 提取码: edc5

本人使用的是win10系统，经测试x86_64-8.1.0-release-win32-seh-rt_v6-rev0好使。

下载并解压后，将MinGW的bin目录加入环境变量中：

命令行执行gcc -v出现如下提示后说明安装成功：

C语言解数独代码

编写c语言的解数独的代码：

#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

typedef enum __bool { false = 0, true = 1, } bool;

int line[9];
int column[9];
int block[3][3];
bool valid;
int* spaces[81];
int spacesSize;

void flip(int i, int j, int digit) {
    line[i] ^= (1 << digit);
    column[j] ^= (1 << digit);
    block[i / 3][j / 3] ^= (1 << digit);
}

void dfs(char** board, int pos) {
    if (pos == spacesSize) {
        valid = 1;
        return;
    }

    int i = spaces[pos][0], j = spaces[pos][1];
    int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
    for (; mask && !valid; mask &= (mask - 1)) {
        int digitMask = mask & (-mask);
        int digit = __builtin_ctz(digitMask);
        flip(i, j, digit);
        board[i][j] = digit + '0' + 1;
        dfs(board, pos + 1);
        flip(i, j, digit);
    }
}

void solveSudoku(char** board) {
    memset(line, 0, sizeof(line));
    memset(column, 0, sizeof(column));
    memset(block, 0, sizeof(block));
    valid = 0;
    spacesSize = 0;

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] != '.') {
                int digit = board[i][j] - '0' - 1;
                flip(i, j, digit);
            }
        }
    }

    while (true) {
        bool modified = false;
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff;
                    if (!(mask & (mask - 1))) {
                        int digit = __builtin_ctz(mask);
                        flip(i, j, digit);
                        board[i][j] = digit + '0' + 1;
                        modified = true;
                    }
                }
            }
        }
        if (!modified) {
            break;
        }
    }

    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            if (board[i][j] == '.') {
                spaces[spacesSize] = malloc(sizeof(int) * 2);
                spaces[spacesSize][0] = i;
                spaces[spacesSize++][1] = j;
            }
        }
    }

    dfs(board, 0);
}

上述函数，未编写main函数直接在c语言中测试，而是在后续python调用中测试通过。若有对c语言感兴趣的童鞋，可以自行编写main函数，直接运行c程序进行测试。

个人使用以下main函数进行测试：

int main() {
    char *board[] ={
        "...6...3.", "5.....6..", ".9...5...",
        "..4.1...6", "...4.3...", "8...9.5..",
        "...7...4.", "..5.....8", ".3...8..."
    };
    for(int i=0;i<9;i++)
        printf ("%s\n",board[i]);
    solveSudoku((char**)board);
    for(int i=0;i<9;i++)
        printf ("%s\n",board[i]);
    return 0;
}

结果程序在solveSudoku的递归调用中直接停止运行，无法得到结果。如果有对c语言编译器比较熟悉的读者，看看能不能给个简单的解决方案。

但神奇的是，后续测试发现Python却能正常调用这个函数，真是神奇，这似乎说明有些c代码无法在纯c的环境中跑，需要在Python等其他高级环境中才能跑？间接性说明Python和c语言可以结合起来一起用，既能享受Python的便捷，又能享受c语言操作内部字节的高效。

下面我们继续操作：

将C代码编译为动态链接库

假设上述代码的文件名是solveSudoku.c，使用如下命令编译：

gcc -shared solveSudoku.c -o solveSudoku.dll

注意：以上编译命令仅针对Windows平台编译测试通过，Mac平台可能需要-Wl和-fPIC参数