Damerau-Levenshtein距离性能改进

Question

我正在使用Python扩展来计算Damerau-Levenshtein距离。我对C一点也不熟悉--我只是知道它通常有更好的性能。不过，我不知道如何取得这些成绩。我从https://github.com/jamesturk/jellyfish/blob/main/jellyfish/_jellyfish.py翻译了一个Python版本，基本上是1:1，速度也不错，但我怀疑我是在做出一个有经验的C程序员不会做出的性能让步。如果有人能指出我正在做的任何低效的事情，我将不胜感激！另外，我只是担心处理ASCII的角色。

#define PY_SSIZE_T_CLEAN
#include <Python.h>
#include <string.h>

// This is a 1:1 translation of https://github.com/jamesturk/jellyfish/blob/main/jellyfish/_jellyfish.py

int min_int(int arr[], size_t size)
{
    // simply loop over an array of integers to find the min
    int min = arr[0];
    for (size_t i = 1; i < size; i++)
    {
        int val = arr[i];
        if (val < min)
        {
            min = val;
        }
    }
    
    return min;
}

static PyObject* distance(PyObject *self, PyObject *args)
{
    const char* s1;
    const char* s2;

    if ( !PyArg_ParseTuple(args, "ss", &s1, &s2) ) // s means string argument
    {
        return NULL;
    }

    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int infinite = len1 + len2;

    int nrows = len1 + 2;
    int ncols = len2 + 2;

    // initialize distance matrix
    int score[nrows][ncols];
    for (size_t i = 0; i < nrows; i++)
    {
        for (size_t j = 0; j < ncols; j++)
        {
            score[i][j] = 0;
        }
    }

    score[0][0] = infinite;
    for (size_t i = 0; i <= len1; i++)
    {
        score[i + 1][0] = infinite;
        score[i + 1][1] = i;
    }
    for (size_t i = 0; i <= len2; i++)
    {
        score[0][i + 1] = infinite;
        score[1][i + 1] = i;
    }
    
    // Since we are only dealing with ascii characters, this is equivalent to the dictionary
    // in the Python implementation. Instead of accessing using the character as the index, we
    // can cast the character to its integer version, and access by index.
    int da[256] = { 0 };

    for (size_t i = 1; i <= len1; i++)
    {
        int db = 0;
        for (size_t j = 1; j <= len2; j++)
        {
            const char s2_char = s2[j - 1];
            int i1 = da[(int)s2_char];
            int j1 = db;
            int cost = 1;
            if (s1[i - 1] == s2_char)
            {
                cost = 0;
                db = j;
            }
            
            int arr[4] = {
                score[i][j] + cost,
                score[i + 1][j] + 1,
                score[i][j + 1] + 1,
                score[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1)
            };
            score[i + 1][j + 1] = min_int(arr, 4);
        }
        const char s1_char = s1[i - 1];
        da[(int)s1_char] = i;
    }
        
    long distance = score[len1 + 1][len2 + 1];

    return PyLong_FromLong(distance);
}

编译器标志是-Wsign-compare -Wunreachable-code -fno-common -dynamic -DNDEBUG -g -fwrapv -O3 -Wall -isysroot /Library/Developer/CommandLineTools/SDKs/MacOSX12.sdk

它可用于查看和使用论哥德波特。我正在MacOS x86_64-apple-darwin21.6.0上编译，clang版本14。

Answer 1

请写这个

int min_int(int arr[], size_t size)
{
    assert(size > 0);

这将避免UB，并给调用者一个很好的诊断，如果他搞砸了他的合同。或者，如果断言可能被禁用，则添加显式if。

此外，写下为什么这段代码不针对C++20或提供std::min的类似代码也是有用的。您可以对代码的速度表示关注。使用其他人编写和调优的代码是解决这些问题的最佳方法之一。

在distance中，非常有帮助的"ss"评论，谢谢。

我很遗憾，这个函数没有命名为damerau_levenshtein_distance，这样可以更好地跟踪python源代码。每当一个工件与另一个工件对应1:1时，建立可跟踪性就很重要。很好地保留了所有的变量名。

如果调用者出错，相应的python源将引发一个很好的诊断TypeError。在这里，也许NULL做了类似的事情？也就是说，我们不会将一个None对象返回给调用者，对吗？哦，我明白了，有一个例外，准备好了，当它返回假的时候，很好。

把分数矩阵归零很好。如果您进行基准测试，您可能会观察到memset做得更快。或者，要求在分配时将其归零。(附带注意: python代码使用整数对象，这意味着大量对象指针的追逐。它有机会使用数组代替。)

            int arr[4] = {

我理解为什么要创建一个临时数组，用于在python代码中对min参数进行文字呈现。但是在这里只计算普通的min()就更自然了，如果有必要的话不止一次。(或者#define min4，如果你觉得它可以提高可读性的话。)

        da[(int)s1_char] = i;

我想我们应该更喜欢一个没有签名的ssize_t演员，对吧？

而且，我知道您说过有一个"ASCII“假设(7位？)，但是const char s1_char声明可能应该没有签名。我想要的是帮助编译器很容易地证明它有一个有效的da索引。

score条目是正数的，有符号表示，这似乎没问题。有机会让每个条目消耗更少的位。

“非Unicode”假设可以写得更清楚。另外，对于少于256个不同编码点的字符串，预处理程序可以将符号映射到直接与当前(未修改的)函数一起工作的小值。

这是设计上的考虑。

我假设python应用程序会在循环中重复调用这个函数。

提供比原始python源代码提供的API更大的API是否有意义？也就是说，如果一个额外的函数允许调用者传入一个单词容器来计算距离，那么我们是否会更快地工作呢？这个想法是C比python for循环更快地遍历它们。