Cython：如何按另一个向量对一个向量的内容进行排序？

Question

我正在尝试在 Cython 中对两个 C++ 向量进行排序，一个按其自身的内容排序，另一个按第一个向量的内容排序。

cimport cython
from libcpp.vector cimport vector
from libcpp.algorithm cimport sort as stdsort

def function():

    cdef vector[np.npy_float] distances
    cdef vector[np.npy_intp] indices

    d = [9., 8., 3., 2., 3.]
    for i in range(len(d)):
        distances.push_back(d[i])
        indices.push_back(i)

    stdsort(distances.begin(), distances.end())
    // distances = [2.0, 3.0, 3.0, 8.0, 9.0]
    // Sort indices by distances?

    return distances, indices

我知道在纯 C++ 中，您可以使用包含距离和索引的对象轻松地完成此操作，并为该对象提供自定义排序函数，但是在 Cython 中执行此操作的简单方法是什么？

Answer 1

为了在 C++ 中获取排序索引，通常不会创建具有索引值对的新向量，而是选择一个比较器，这将在不实际复制内存的情况下实现相同的目的。

将其转换为 Cython 将如下所示：

%%cython -+ -c=-std=c++11
from libcpp.vector cimport vector
cdef extern from *:
    """
    #include <algorithm>
    #include <vector>
    void sort_via_score(std::vector<int>& indices, const std::vector<double>& scores){
        std::sort(indices.begin(), indices.end(),
                  [&scores](int i, int j){return scores.at(i)<scores.at(j);}
                 );
    }
    """
    void sort_via_score(vector[int]& indices, vector[double]& scores)
    
def sort_indices(lst):
    cdef vector[double] scores = lst
    cdef vector[int] indices = range(len(lst))
    sort_via_score(indices, scores)
    return indices

该函数sort_indices是一个包装器，它允许我们快速检查实现：

sort_indices([5,4,3,2,1])
# [4, 3, 2, 1, 0] as expected

sort_via_score其工作原理与 Python 中的以下单行代码类似：

def sort_indices_py(scores):
    return sorted(range(len(scores)), key=lambda x: scores[x])

-向量scores在闭包中用于查找索引的分数。没有创建将索引及其分数放在内存中的新对象 - 它们key仅由 - 函数的逻辑组合。

上面的解决方案使用逐字 C 代码，因为使用 C++ 编写 C++ 代码比使用 Cython 容易得多。

如果真的想坚持使用“纯”Cython（我不推荐），那么可以使用以下代码来模拟 C++ 闭包：

%%cython -+
from libcpp.vector cimport vector
from libcpp.algorithm cimport sort as stdsort

cdef vector[double]* vec
cdef bint comp_fun(int i, int j):
    return vec.at(i)<vec.at(j)

def sort_indices2(lst):
    cdef vector[double] scores = lst
    cdef vector[int] indices = range(len(lst))
    global vec
    vec = &scores # "global closure"
    stdsort(indices.begin(), indices.end(), comp_fun)
    return indices