时间戳

首页 > 解决方案 > Cython 遍历数组和索引仍然很慢

python - Cython 遍历数组和索引仍然很慢

问题描述

我目前正在尝试加速一种算法，该算法采用 x,y 坐标数组，找到彼此相距最远的指定数量的点（基于两个给定的起点）并返回它们的索引。

这就是代码的样子：（distMat 是一个数组，它保存所有点之间的距离，numIndices 是所需的点数，index0 和 index1 是两个 startPoints 的索引。）

import numpy as np
cimport numpy as np
cimport cython

DTYPE = np.float
ctypedef np.float_t DTYPE_t
ctypedef np.int32_t INT32_t
ctypedef np.int64_t INT64_t


def find_furthest_indices(np.ndarray[DTYPE_t, ndim=2] distMat, int numIndices, int index0, int index1):
    cdef int i, j
    cdef double dist, minDist, curDist
    cdef np.ndarray[INT32_t, ndim=1] selectedIndices = np.empty(numIndices, dtype=np.int32)
    cdef np.ndarray[INT32_t, ndim=1] remainingIndices = np.arange(numIndices, dtype=np.int32)

    selectedIndices[0] = index0
    selectedIndices[1] = index1
    for i in range(numIndices-2):
        minDist = 0.0
        for j in remainingIndices:
            dist = np.inf

            for k in selectedIndices[:i+1]:
                curDist = distMat[j][k]
                if curDist < dist:
                    dist = curDist

            if dist > minDist:
                minj = j
                minDist = dist

        selectedIndices[i+2] = minj
        remainingIndices = remainingIndices[remainingIndices!=minj]

    return selectedIndices

它可以工作，但是（正如预期的那样）在处理较大的数组时仍然有点慢（例如 5000 点 -> distMat 是 5000x5000 并且 numIndices = 500）。这可能是因为算法的性质（对于那些真正想知道的人来说是“Kennard-Stone”），但我想知道 cythonize 的彩色输出： CythonizeOutput

它将以下几行标记为深黄色，这意味着有很多 Python 交互要转换为 C.. 我不明白为什么这三个在其中：

for j in remainingIndices:

for k in selectedIndices[:i+1]

和

curDist = distMat[j][k]

有人可以解释为什么这些线在这种情况下很慢吗？我已经为给定的参数添加了类型定义，所以遍历它们和索引应该很快？？

提前致谢！！！

标签： pythonindexingiterationcython

解决方案

for j in remainingIndices:

使用 Python iter 协议进行迭代。在 Cython 中，最好使用范围和索引。你想要这样的东西：

for jidx in range(remainingIndices.shape[0]):
    j = remainingIndices[jidx]

for k in selectedIndices[:i+1]

和上面一样

curDist = distMat[j][k]

创建数组的一个切片，然后对切片进行索引（这两个都必须回退到 Python）。你要

curDist = distMat[j, k]

推荐阅读