python - Cython:加速简单代码

Question

我正在尝试使用 Cython 加速以下代码。从 python 导入两个参数:

processing_times:包含 500 个列表，每个列表包含 20 个整数 (500x20)。

序列:包含 500 个整数的列表。

cimport cython
@cython.boundscheck(False)
@cython.wraparound(False)

cpdef taillard_acceleration(sequence, processing_times, int job_inserted, int num_machines):

    # Static arrays - number of jobs limited to 500 jobs and 20 machines
    cdef int e[501][21]
    cdef int q[501][21]
    cdef int f[501][21]
    cdef int ms[501]

    # Variables
    cdef int sequence_length, best_makespan, best_position
    cdef int i, j, iq, jq, tmp

    # Initialize some values
    sequence_length = len(sequence)
    iq = sequence_length + 1


    for i in range(1, sequence_length + 2):
        if i < sequence_length + 1:
            e[i][0] = 0

            # Q index I
            iq = iq - 1
            q[iq][num_machines + 1] = 0

        f[i][0] = 0
        jq = num_machines + 1


        for j in range(1, num_machines + 1):
            if i == 1:
                e[0][j] = 0
                q[sequence_length + 1][num_machines + 1 - j] = 0
            if i < sequence_length + 1:
                # Q Index J
                jq = jq - 1

                if e[i][j - 1] > e[i - 1][j]:
                    e[i][j] = e[i][j - 1] + processing_times[sequence[i - 1]-1][j-1]
                else:
                    e[i][j] = e[i - 1][j] + processing_times[sequence[i - 1]-1][j-1]

                if q[iq][jq + 1] > q[iq + 1][jq]:
                    q[iq][jq] = q[iq][jq + 1] + processing_times[sequence[iq - 1]-1][jq-1]
                else:
                    q[iq][jq] = q[iq + 1][jq] + processing_times[sequence[iq - 1]-1][jq-1]

            # f(ij) = max {f(i, j-1), e(i-1, j)}
            if f[i][j - 1] > e[i - 1][j]:
                f[i][j] = f[i][j - 1] + processing_times[job_inserted-1][j-1]
            else:
                f[i][j] = e[i - 1][j] + processing_times[job_inserted-1][j-1]


    # Makespam - job k in position i
    best_makespan = 0
    best_position = 0
    for i in range(1, sequence_length + 2):
        ms[i] = 0
        for j in range(1, num_machines + 1):
            tmp = f[i][j] + q[i][j]
            if tmp > ms[i]:
                ms[i] = tmp
        # Check best insertion position
        if ms[i] < best_makespan or best_makespan == 0:
            best_makespan = ms[i]
            best_position = i


    return best_position, best_makespan

与原始 Python 代码相比，我能够将处理速度加快 4 倍:

Just Python: 0.04114614830813535
With Cython: 0.00937230621550278
Cython is 4.390183948543561 times faster

如何在此代码中获得更好的速度提升？

我已经尝试将sequence和processing_times转换为外部的numpy数组，然后使用内存 View ，但我没有得到任何改进。

cpdef taillard_acceleration(sequence_np, processing_times_np, int job_inserted, int num_machines):

    # memory view
    cdef int [:, :] processing_times = processing_times_np
    cdef int [:] sequence = sequence_np

我还应该对 q、e、f、ms 数组使用 malloc 吗？第一次使用 Cython，所以我不知道我这样做是否正确。非常感谢任何帮助。

Answer 1

大部分内容看起来都输入正确，因此您不太可能获得巨大的改进。未输入的主要内容是 sequence和processing_times 。您应该制作这些内存 View :

def taillard_acceleration(int[:] sequence, int[:,:] processing_times, int job_inserted, int num_machines):

我知道您已经尝试过此操作，但是您还应该将其索引更改为 processing_times[i,j] 的形式(而不是 processing_times[i][j] )。您正在做的事情会创建一个 1D 内存 View 作为临时对象，这可能会慢一些。

<小时/>

对于q , e , f ，和ms数组:如果您愿意重新编译以更改大小，那么您现在所做的绝对没问题。如果您认为可能想在运行时更改大小，那么您应该在运行时分配它们。您可以使用malloc但我会用:

cdef int[:,::1] e = np.zeros((501,21))

([:,::1] 告诉 Cython 该数组是二维且连续的)。像这样使用 numpy 会比 malloc 慢稍微 ，但它也更容易，而且出错的可能性也更小。如果您这样做，请将它们的索引更改为 e[i,j]如上所述。

(看起来它们的大小确实应该是 sequency_length 乘 num_machines 所以运行时大小可能是一个好主意)