Cython Итерация по массиву и индексация все еще медленная

Question

В настоящее время я пытаюсь ускорить алгоритм, который принимает массив координат 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). Вероятно, это связано с природой алгоритма («Кеннард-Стоун» для тех, кто действительно хочет знать), но мне интересно узнать о цветном выводе из cythonize: CythonizeOutput

Он помечает следующие строки темно-желтым цветом, означая, что существует большое количество Python взаимодействий для перевода на C .. Я не понимаю, почему эти три среди них:

for j in remainingIndices:

for k in selectedIndices[:i+1]

и

curDist = distMat[j][k]

Может кто-нибудь пролить свет на то, почему эти строки медленны в этом контексте? Я добавил определения типов для заданных параметров, поэтому итерации по ним и индексация должны быть быстрыми ??

Заранее спасибо !!!

Answer 1

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]