将自定义比较器传递给 Cython 中的优先级队列

Question

Cython libcpp 模块包含 priority_queue 的模板，这很棒，除了一件事：我无法将自定义比较器传递给它（或者，至少，我不知道如何）。

我需要这个，因为我需要 priority_queue 来做某种 argsort 而不是 sort（是的，优先队列最适合我想做的事情），我需要它快。

在 Cython 中这可能吗，也许 wrapping a queue in a custom way，或者根本不可能？

例如，假设我想按其中一个元素以稳定的方式对 vector[int[:]] 进行排序。实际算法要复杂得多。

我决定通过将它逐个元素添加到 priority_queue 来对其进行排序。但是，我不知道该怎么做。

我的实际操作类似于 this question，但是我正在按特定元素合并已排序的 int[:] 一维元素，其中原始列表也按该元素排序。

我不介意将对象转换为 buffer/pointer。

Answer 1

这项工作是可行的，但我真的不推荐这样做。主要问题是：

C++ 容器不能轻易容纳 Python 对象（例如内存视图），除非您准备编写引用计数包装器代码（在 C++ 中）
您可以获得指向内存视图第一个元素的 C 指针，但是：
- 你必须确保保留对底层对象（拥有内存）的引用，否则Python将释放它并且你将使用访问内存无效。
- 指针会丢失有关数组长度的所有信息。
你可以使用的比较器非常有限（它们必须可以表示为 cdef 函数）——例如我写了一个比较数组的第二个元素的，但是它需要重新编译才能更改为比较第三个元素。

因此我的建议是找到另一种方法。然而：

您需要编写一个非常小的 C++ 文件来 typedef 您想要的优先级队列类型。这使用 std::function 作为比较器，我假设你想存储 longs。需要此文件，因为 Cython 的模板支持非常有限。

// cpp_priority_queue.hpp
#include <functional>
#include <queue>

using intp_std_func_prority_queue = std::priority_queue<long*,std::vector<long*>,std::function<bool(long*,long*)>>;

然后您将无法使用 Cython 提供的 libcpp.queue.priority_queue 包装器。相反，自己编写，包装您需要的功能 ("priority_queue_wrap.pyx")

# distutils: language = c++

from libcpp cimport bool

cdef extern from "cpp_priority_queue.hpp":
    cdef cppclass intp_std_func_prority_queue:
        intp_std_func_prority_queue(...) # get Cython to accept any arguments and let C++ deal with getting them right
        void push(long*)
        long* top()
        void pop()
        bool empty()

cdef bool compare_2nd_element(long* a, long* b):
    # note - no protection if allocated memory isn't long enough
    return a[1] < b[1]


def example_function(list _input):
    # takes a list of "memoryviewable" objects
    cdef intp_std_func_prority_queue queue = intp_std_func_prority_queue(compare_2nd_element) # cdef function is convertable to function pointer

    cdef long[::1] list_element_mview
    cdef long* queue_element


    for x in _input:
        #print(x)
        list_element_mview = x
        assert list_element_mview.shape[0] >= 2 # check we have enough elements to compare the second one
        queue.push(&list_element_mview[0]) # push a pointer to the first element

    while not queue.empty():
        queue_element = queue.top(); queue.pop()
        print(queue_element[0],queue_element[1]) # print the first two elements (we don't know that we have any more)

然后我创建了一个示例函数，该函数遍历 memoryview 兼容对象列表，将它们转换为指针，并将它们添加到队列中。最后，它按顺序遍历队列并打印它能打印的内容。请注意，输入列表比队列长！

最后一个创建适当列表的快速 Python 测试函数：

import priority_queue_wrap
import numpy as np

a = np.vstack([np.arange(20),np.random.randint(0,10,size=(20,))])
l = [a[:,n].copy() for n in range(a.shape[1]) ]

print(l)
priority_queue_wrap.example_function(l)

总而言之，Python objects + Cython + C++ 一团糟：我不建议这样做（但你可以试试！）

将自定义比较器传递给 Cython 中的优先级队列

Pass a custom comparer to a priority queue in Cython

priority-queue

cython

comparison-operators