python - Python 3 中的三向字符串比较

Question

假设您要优化用 Python 实现的(字节)字符串比较密集型算法。由于中央代码路径包含此语句序列

if s < t:
    # less than ...
elif t < s:
    # greater than ...
else:
    # equal ...

如果能优化成类似的东西就好了

r = bytes_compare(s, t)
if r < 0:
    # less than ...
elif r > 0:
    # greater than ...
else:
    # equal ...

其中(假设的)bytes_compare() 理想情况下只会调用 three-way comparison C 函数 memcmp()通常优化得很好。这会将字符串比较的次数减少一半。除非字符串超短，否则这是一个非常可行的优化。

但是如何使用 Python 3 实现目标呢？

附言:

Python 3 移除了三向比较全局函数 cmp() 和魔术方法 __cmp__()。即使使用 Python 2，bytes 类也没有 __cmp__() 成员。

使用 ctypes 包可以直接调用 memcmp() 但使用 ctypes 的外部函数调用开销非常高。

Answer 1

Python 3(包括 3.6)根本不包含对字符串的任何三向比较支持。尽管富比较运算符 __lt__()、__eq__() 等的内部实现调用了 memcmp()(在 C 实现中bytes - 参见 Objects/bytesobject.c)没有可以利用的内部三向比较函数。

因此，写一个C extension通过调用 memcmp() 提供三路比较功能的次优选择是:

#include <Python.h>
static PyObject* cmp(PyObject* self, PyObject* args) {
    PyObject *a = 0, *b = 0;
    if (!PyArg_UnpackTuple(args, "cmp", 2, 2, &a, &b))
        return 0;
    if (!PyBytes_Check(a) || !PyBytes_Check(b)) {
        PyErr_SetString(PyExc_TypeError, "only bytes() strings supported");
        return 0;
    }
    Py_ssize_t n = PyBytes_GET_SIZE(a), m = PyBytes_GET_SIZE(b);
    char *s = PyBytes_AsString(a), *t = PyBytes_AsString(b);
    int r = 0;
    if (n == m) {
        r = memcmp(s, t, n);
    } else if (n < m) {
        r = memcmp(s, t, n);
        if (!r)
            r = -1;
    } else {
        r = memcmp(s, t, m);
        if (!r)
            r = 1;
    }
    return PyLong_FromLong(r);
}
static PyMethodDef bytes_util_methods[] = {
    { "cmp", cmp, METH_VARARGS, "Three way compare 2 bytes() objects." },
    {0,0,0,0} };
static struct PyModuleDef bytes_util_def = {
    PyModuleDef_HEAD_INIT, "bytes_util", "Three way comparison for strings.",
    -1, bytes_util_methods };
PyMODINIT_FUNC PyInit_bytes_util(void) {
    Py_Initialize();
    return PyModule_Create(&bytes_util_def);
}

编译:

gcc -Wall -O3 -fPIC -shared bytes_util.c -o bytes_util.so -I/usr/include/python3.6m

测试:

>>> import bytes_util
>>> bytes_util.cmp(b'foo', b'barx')
265725

与通过 ctypes 包调用 memcmp 相比，这个外部调用具有与内置字节比较运算符相同的开销(因为它们也是作为 C 扩展实现的标准的 Python 版本)。