将自定义比较器传递到Cython中的优先级队列 [英] Pass a custom comparer to a priority queue in Cython

问题描述

Cython libcpp 模块包含 priority_queue 的模板，这很不错，除了以下几点：我不能向它传递一个自定义比较器（或者至少不知道如何操作）。

The Cython libcpp module contains a template for priority_queue, which is great, except for one thing: I cannot pass it a custom comparer (or, at least, I don't know how to).

我需要这个，因为我需要 priority_queue 进行排序的 argsort 而不是 sort （是的，优先级队列是最佳的

I need this because I need the priority_queue to do an argsort of sorts rather than a sort (yes, a priority queue is optimal for what I want to do), and I need it to be fast.

在Cython中是否可能做到这一点，也许是通过以自定义方式包装队列，还是根本不？

Is this possible within Cython, perhaps by wrapping a queue in a custom way, or not at all?

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

As an example, say I want to sort a vector[int[:]] by one of the elements in a stable way. The actual algorithm is much more complicated.

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

I decide to sort it by adding it, element-by-element to the priority_queue. However, I don't know how to do that.

我的实际操作类似于，但是我在合并 int [：] s一维元素由一个特定元素组成，原始列表也由该元素排序。

My actual operation is something like this question, however I'm merging sorted int[:]s of 1-D elements by a particular element, where the original lists are also ordered by that element.

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

I don't mind converting the objects to a buffer/pointer.

推荐答案

可以实现此功能，但我真的不建议这样做。主要问题是：

It is possible to make this work, but I real don't recommend it. The main problems are:

• 除非您准备编写引用计数，否则C ++容器无法轻易容纳Python对象（例如memoryviews）。包装代码（在C ++中）


• 您可以获得指向内存视图第一个元素的C指针，但是：
  
  
  
  
  • 您必须确保保留对基础对象（拥有内存）的引用，否则Python将释放它，并且您将使用访问无效的内存。
  
  
  • 指针会丢失有关数组长度的所有信息。
  
  
  • C++ containers can't readily hold Python objects (such as memoryviews) unless you're prepared to write reference counting wrapper code (in C++)
  • You can get a C pointer to the first element of a memoryview, but:
    • you must ensure that a reference to the underlying object (that owns the memory) is kept, otherwise Python will free it and you'll be using accessing invalid memory.
    • a pointer loses all information about how long the array is.

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

    Therefore my advice is to find another way of doing it. However:

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

    You need to write a very small C++ file to typedef the type of priority queue you want. This uses std::function as the comparator, and I've assumed you want to store longs. This file is needed because Cython's template support is pretty limited.

    // 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_queue 包装器。而是自己编写，包装所需的功能（ priority_queue_wrap.pyx）

    You then can't use the libcpp.queue.priority_queue wrapper provided with Cython. Instead, write your own, wrapping the functions you need ("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兼容的对象的列表，将它们转换为指针，并将它们添加到队列中。最后，它按顺序遍历队列并打印它可以显示的内容。请注意，输入列表已超出队列 ！！

    I've then created an example function that goes through a list of memoryview compatible objects, converts them to pointers, and adds them to the queue. Finally, it goes through the queue in order and prints what it can. Note that the input list outlives the queue!

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

    Finally a quick Python test function that creates an appropriate list:

    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 ++真是一团糟：我不建议这样做（但您可以尝试！）

    ---

    In summary, Python objects + Cython + C++ is a mess: I don't recommend doing it this way (but you can try!)

    这篇关于将自定义比较器传递到Cython中的优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！