Ich versuche, die Zeit einer Funktion zu verkürzen, die eine Reihe von Berechnungen mit zwei Matrizen durchführt. Auf der Suche danach habe ich von Numpy gehört, aber ich weiß wirklich nicht, wie ich es auf mein Problem anwenden soll. Außerdem glaube ich, dass eines der Dinge, die meine Funktion verlangsamen, darin besteht, viele Punktoperatoren zu haben (davon habe ich in diesem Artikel gehört)diese Seite ).

Die Mathematik entspricht einer Faktorisierung für das quadratische Zuordnungsproblem:

Mein Code ist:

    delta = 0
    for k in xrange(self._tam):
        if k != r and k != s:
            delta +=
                self._data.stream_matrix[r][k] \
                * (self._data.distance_matrix[sol[s]][sol[k]] - self._data.distance_matrix[sol[r]][sol[k]]) + \
                self._data.stream_matrix[s][k] \
                * (self._data.distance_matrix[sol[r]][sol[k]] - self._data.distance_matrix[sol[s]][sol[k]]) + \
                self._data.stream_matrix[k][r] \
                * (self._data.distance_matrix[sol[k]][sol[s]] - self._data.distance_matrix[sol[k]][sol[r]]) + \
                self._data.stream_matrix[k][s] \
                * (self._data.distance_matrix[sol[k]][sol[r]] - self._data.distance_matrix[sol[k]][sol[s]])
    return delta

Wenn Sie dies auf einem Problem der Größe 20 (Matrix von 20x20) ausführen, benötigen Sie ungefähr 20 Segmente. Der Engpass liegt in dieser Funktion

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
303878   15.712    0.000   15.712    0.000 Heuristic.py:66(deltaC)

Ich habe versucht mich zu bewerbenmap zur for-Schleife, aber da der Schleifenkörper kein Funktionsaufruf ist, ist dies nicht möglich.

Wie könnte ich die Zeit verkürzen?

EDIT1

Um eickenbergs Kommentar zu beantworten:

sol ist eine Permutation, zum Beispiel [1,2,3,4]. Die Funktion wird aufgerufen, wenn ich Nachbarlösungen generiere. Ein Nachbar von [1,2,3,4] ist also [2,1,3,4]. Ich ändere nur zwei Positionen in der ursprünglichen Permutation und rufe dann aufdeltaC, der eine Faktorisierung der Lösung mit vertauschten Positionen r, s berechnet (im obigen Beispiel r, s = 0,1). Diese Permutation soll verhindern, dass die gesamten Kosten der Nachbarlösung berechnet werden. Ich nehme an, ich kann die Werte von speichernsol[k,r,s] in einer lokalen Variablen, um zu vermeiden, dass ihr Wert in jeder Iteration nachgeschlagen wird.Ich weiß nicht, ob Sie dies in Ihrem Kommentar gefragt haben.

EDIT2

Ein minimales Arbeitsbeispiel:

import random


distance_matrix = [[0, 12, 6, 4], [12, 0, 6, 8], [6, 6, 0, 7], [4, 8, 7, 0]]
stream_matrix = [[0, 3, 8, 3], [3, 0, 2, 4], [8, 2, 0, 5], [3, 4, 5, 0]]

def deltaC(r, s, S=None):
    '''
    Difference between C with values i and j swapped
    '''

    S = [0,1,2,3]

    if S is not None:
        sol = S
    else:
        sol = S

    delta = 0

    sol_r, sol_s = sol[r], sol[s]

    for k in xrange(4):
        if k != r and k != s:
            delta += (stream_matrix[r][k] \
                * (distance_matrix[sol_s][sol[k]] - distance_matrix[sol_r][sol[k]]) + \
                stream_matrix[s][k] \
                * (distance_matrix[sol_r][sol[k]] - distance_matrix[sol_s][sol[k]]) + \
                stream_matrix[k][r] \
                * (distance_matrix[sol[k]][sol_s] - distance_matrix[sol[k]][sol_r]) + \
                stream_matrix[k][s] \
                * (distance_matrix[sol[k]][sol_r] - distance_matrix[sol[k]][sol_s]))
    return delta


for _ in xrange(303878):
    d = deltaC(random.randint(0,3), random.randint(0,3))
print d

Jetzt denke ich, die bessere Option ist die Verwendung von NumPy. Ich habe es mit Matrix () versucht, aber die Leistung nicht verbessert.

Beste Lösung gefunden

Nun, endlich konnte ich die Zeit etwas verkürzen, indem ich @ TooTones Lösung kombinierte und die Indizes in einem Satz speicherte, um das Wenn zu vermeiden. Die Zeit ist von ungefähr 18 Sekunden auf 8 Sekunden gesunken. Hier ist der Code:

def deltaC(self, r, s, sol=None):
    delta = 0
    sol = self.S if sol is None else self.S
    sol_r, sol_s = sol[r], sol[s]

    stream_matrix = self._data.stream_matrix
    distance_matrix = self._data.distance_matrix

    indexes = set(xrange(self._tam)) - set([r, s])

    for k in indexes:
        sol_k = sol[k]
        delta += \
            (stream_matrix[r][k] - stream_matrix[s][k]) \
            * (distance_matrix[sol_s][sol_k] - distance_matrix[sol_r][sol_k]) \
            + \
            (stream_matrix[k][r] - stream_matrix[k][s]) \
            * (distance_matrix[sol_k][sol_s] - distance_matrix[sol_k][sol_r])
    return delta

Um die Zeit noch weiter zu verkürzen, ist es meiner Meinung nach am besten, ein Modul zu schreiben.