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

Question

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

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

这在 Cython 中是否可能，也许通过以自定义方式包装队列，或者根本不可能？

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

我决定通过将其逐个元素添加到priority_queue. 但是，我不知道该怎么做。

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

我不介意将对象转换为缓冲区/指针。

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*)>>;

然后您将无法使用libcpp.queue.priority_queueCython 提供的包装器。相反，编写您自己的，包装您需要的函数（“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)

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

最后是一个快速的 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 对象 + Cython + C++ 是一团糟：我不建议这样做（但你可以尝试！）