Здесь речь пойдёт о том, как написать функцию на C, скомпилировать её и импортировать в Python. Это может быть крайне полезно для ускорения определённых секций кода на питоне. Ниже я приведу разбор алгоритма о наибольшей общей подпоследовательности, который можно реализовать на питоне, а можно на C с экспортом в питон. И конечно же в заключение будет тест производительности.

Эту статью пишу не столько для других, сколько для себя, чтобы была возможность периодически подглядывать в детали. :)

Постановка задачи.

Формулировка. Пусть у нас есть две последовательности. Необходимо найти подпоследовательность максимальной длины, которая содержится в каждой из двух данных последовательностей. Порядок элементов имеет значение. Больше об этой задаче можно почитать на Википедии.

Задача о наибольшей общей подпоследовательности очень известна среди программистов. Она, в частности, входит в стандартную утилиту diff, которая сравнивает файлы и определяет секции, которые в файлах различны.

В нашем случае мы в качестве последовательностей рассмотрим строки (как последовательности символов), а вместо максимальной подпоследовательности будем вычислять её длину - для простоты.

Алгоритм на питоне.

# lcs_py.py

def solve(s1, s2):
    n1 = len(s1)
    n2 = len(s2)

    row = [0 for _ in range(n1)]
    for i2 in range(n2):
        row_p = row[:]
        for i1 in range(n1):
            if s1[i1] == s2[i2]:
                row[i1] = 1 + (row_p[i1 - 1] if i1 > 0 else 0)
            else:
                row[i1] = max(row[i1 - 1] if i1 > 0 else 0, row_p[i1])

    return row[-1]

Ситонизация.

Для увеличения производительности существует подход, который называется ситонизацией. Он состоит в том, что определённым образом оформленный питоновский код (на самом деле этот код нужно писать на Cython) можно скомпилировать в C и дальше скомпилировать в dll. После этого модуль доступен извне с синтаксисом импорта обычного питоновского модуля.

# lcs_pyx.pyx

def solve(str s1, str s2):
    n1 = len(s1)
    n2 = len(s2)

    row = [0 for _ in range(n1)]
    for i2 in range(n2):
        row_p = row[:]
        for i1 in range(n1):
            if s1[i1] == s2[i2]:
                row[i1] = 1 + (row_p[i1 - 1] if i1 > 0 else 0)
            else:
                row[i1] = max(row[i1 - 1] if i1 > 0 else 0, row_p[i1])

    return row[-1]

Чтобы его было возможно импортировать как модуль, необходимо произвести компиляцию. Для этого необходимо написать такой промежуточный файл:

# setup_pyx.py

from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize("lcs_pyx.pyx")
)
$ python3 setup_pyx.py build_ext --inplace

Алгоритм на C.

Теперь независимо оформим тот же алгоритм как библиотека на C.

/* lcs_c.h */

int solve(const char* s1, const char* s2);
/* lcs_c.c */

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

#include "lcs_c.h"

#define max(x, y) (((x) >= (y)) ? x : y)


int solve(const char* s1, const char* s2) {
    int n1 = strlen(s1);
    int n2 = strlen(s2);

    int* row = (int*)calloc(sizeof(int), n1);
    int* row_p = (int*)calloc(sizeof(int), n1);

    memset(row, 0, sizeof(int) * n1);

    for (int i2 = 0; i2 < n2; i2++) {
        memcpy(row_p, row, sizeof(int) * n1);
        for (int i1 = 0; i1 < n1; i1++) {
            if (s1[i1] == s2[i2]) {
                row[i1] = 1 + ((i1 > 0) ? row_p[i1 - 1] : 0);
            }
            else {
                row[i1] = max(
                    (i1 > 0) ? row[i1 - 1] : 0,
                    row_p[i1]
                );
            }
        }
    }

    int result = row[n1 - 1];

    free(row);
    free(row_p);

    return result;
}

Компилируем это:

$ gcc -c -fPIC "lcs_c.c" -o "lcs_c.o"
$ gcc "lcs_c.o" -shared -o "lcs_c.so"

Тест производительности.

# test.py

import ctypes
from time import time
from random import choice

import lcs_py
import lcs_pyx

lcs_c = ctypes.CDLL('/home/alexander/Stuff/longest_common_subsequence/lcs_c.so')
lcs_c_solve = lambda s1, s2: lcs_c.solve(
    ctypes.c_char_p(s1.encode('utf-8')),
    ctypes.c_char_p(s2.encode('utf-8'))
)


LENGTH = 5000


def gen_random_word(length):
    return ''.join(choice('0123456789abcdef') for _ in range(length))


def test(func, word1, word2):
    tb = time()
    res = func(word1, word2)
    te = time()
    print("time: {:.2f}, result: {}".format(te - tb, res))


word1 = gen_random_word(LENGTH)
word2 = gen_random_word(LENGTH)

test(lcs_py.solve, word1, word2)
test(lcs_pyx.solve, word1, word2)
test(lcs_c_solve, word1, word2)

Здесь генерируются два слова длиной LENGTH = 5000, состояющие из случайных цифр и букв от a до f. Далее измеряется время работы функций. Результаты производят впечатление. На моём компьютере они вот такие:

$ python3 test.py
time: 8.21, result: 1971
time: 3.48, result: 1971
time: 0.10, result: 1971

Как мы видим, чистый питон оказался в 82 раза медленнее аналогичного кода на C. Ситонизация действительно помогла ускориться, но всего в 2.4 раза.

Выводы.

Думаю, выводы здесь вполне очевидны. Каждый из подходов к алгоритмам имеет место в зависимости от задачи, времени на разработку, необходимого предела производительности и других факторов. Если производительность неважна и не хочется поддерживать все эти процедуры ускорения, то можно оставить на питоне. Если ускорение нужно существенное, то тогда на чистом C. Cython - это как промежуточный вариант, особенно удобный, когда уже есть готовый код на питоне.