Die Auswirkungen von vektorisierten Operationen auf die Leistung

Skriptsprachen werden oft mit ihrer Langsamkeit in Verbindung gebracht. Mit immer schnelleren Computern wird dies vielleicht immer weniger relevant, aber wenn wir in den Bereich der Big(ger)-Daten vordringen, ist Leistungseffizienz immer willkommen. In diesem Blogbeitrag werfen wir einen Blick auf die Auswirkungen von vektorisierten Operationen. Als Beispiel erstellen wir ein Python-Skript, um zu prüfen, ob eine Postleitzahl innerhalb einer bestimmten Entfernung von einem Referenzpunkt liegt, und messen, wie sich die Vektorisierung auf die Leistung auswirkt.

Die Prüfung, ob zwei Punkte innerhalb eines bestimmten Abstands liegen, wenn man ihren Breiten- und Längengrad angibt, ist normalerweise sehr schnell. Die Vektorisierung würde nicht viel helfen, wenn Sie den Vorgang nur einmal durchführen. Aber was ist, wenn Sie diese Operation hunderttausende Male wiederholen? In einer C-Welt wäre auch das sehr schnell. In Python? Nicht so sehr!

Das Wichtigste zuerst: Entfernung zwischen zwei Punkten

Da es keinen Sinn machen würde, die Leistung eines Skripts zu verbessern, ohne zu wissen, was das Skript tun soll, möchte ich Ihnen die Haversinus-Formel zur Berechnung des Abstands zwischen zwei Punkten vorstellen:

d = 2 r arcsinleft(sqrt{sin^2left(frac{phi_2 - phi_1}{2}right) + cos(phi_1) cos(phi_2)sin^2left(frac{lambda_2 - lambda_1}{2}right)}right)

wobei phi_{1,2} der Breitengrad der beiden Punkte und lambda_{1,2} ihr Längengrad ist (beide in Radiant). Wenn Sie für r den (durchschnittlichen) Erdradius eingeben, erhalten Sie die Entfernung zwischen den beiden Punkten in derselben Einheit (also in km, wenn Sie km verwendet haben, m, wenn Sie m verwendet haben, und so weiter).

Eine pythonische Haversin-Formel

Wenn Sie Angst vor der Mathematik haben, aber Python lieben, keine Sorge: wir stellen Ihnen auch den fertigen Python-Code zur Verfügung (ACHTUNG: Sie benötigen NumPy, damit es funktioniert):

from numpy import sin, cos, pi, arcsin, sqrt
def get_distance(lat, lon, pcode_lat, pcode_lon):
    """
    Find the distance between (lat,lon) and the reference point
    (pcode_lat,pcode_lon).
    """
    RAD_FACTOR = pi / 180.0  # degrees to radians for trig functions
    lat_in_rad = lat * RAD_FACTOR
    lon_in_rad = lon * RAD_FACTOR
    pcode_lat_in_rad = pcode_lat * RAD_FACTOR
    pcode_lon_in_rad = pcode_lon * RAD_FACTOR
    delta_lon = lon_in_rad - pcode_lon_in_rad
    delta_lat = lat_in_rad - pcode_lat_in_rad
    # Next two lines is the Haversine formula
    inverse_angle = (sin(delta_lat / 2) ** 2 + cos(pcode_lat_in_rad) *
                     cos(lat_in_rad) * sin(delta_lon / 2) ** 2)
    haversine_angle = 2 * arcsin(sqrt(inverse_angle))
    EARTH_RADIUS = 6367  # kilometers
    return haversine_angle * EARTH_RADIUS

Wir könnten uns fragen, wie schnell dieser Code ist, wenn wir 400000 Postleitzahlen überprüfen wollen (das ist ungefähr die Anzahl der Postleitzahlen in den Niederlanden). Dies ist nützlich, wenn wir eine Liste von Postleitzahlen erhalten möchten, die in einem bestimmten Radius von einer Referenzpostleitzahl liegen.

Einige Leistungsmessungen

Um die Leistung des obigen Codes zu messen, erstellen wir ein Array mit einigen zufälligen Breiten- und Längengradpaaren, die um (52.3905927,4.8412508) (das Koordinatenpaar unseres Büros) zentriert sind

from numpy import random
godatadriven = (52.3905927,4.8412508)
points = random.randn(400000, 2) * 0.01
points[:, 0] = points[:, 0] + godatadriven[0]
points[:, 1] = points[:, 1] + godatadriven[1]

Die Syntax points[:, 0] ist die NumPy-Art zu sagen: Wählen Sie alle Felder der ersten Spalte aus, was in unserem Fall der Breitengrad von points wäre. Um zu messen, wie viel Zeit benötigt wird, um die Entfernungen zwischen points und godatadriven zu ermitteln, können wir die magische Funktion ipython %timeit verwenden, die misst, wie viel Zeit ein Skript im Durchschnitt bei mehreren Durchläufen zur Ausführung benötigt:

def iterate_distance():
    d = []
    for p in points:
        d.append(get_distance(p[0], p[1], godatadriven[0], godatadriven[1]))
%timeit iterate_distance()  # runs in 3.53 seconds

Wenn Sie mit Python vertraut sind, wird Ihnen der obige Code einen Schauer über den Rücken jagen, da er keine Listenverarbeitung verwendet. Die Änderung des Codes hat leider nur einen geringen Einfluss auf die Leistung:

%timeit [get_distance(p[0], p[1], godatadriven[0], godatadriven[1]) for p in points]
# runs in 3.46 seconds

Wenn Sie eine Echtzeitanwendung entwickeln, bei der eine Überprüfung der Postleitzahl eine Zwischenberechnung sein könnte, sind 3,46s eine Ewigkeit. Zum Glück können wir mit NumPy ein wenig zaubern.

Die Vektorisierung ist die Rettung

In unserem Code ist points ein NumPy-Array. NumPy-Arrays können leicht manipuliert werden, da sie so kodiert wurden, dass sie eine wirklich praktische Möglichkeit darstellen, Blöcke von Computerspeicher zu beschreiben. Die von NumPy gewählte besondere Struktur ermöglicht es, die Arrays ganz einfach mit C- oder Fortran-Code zu verändern. Das ist hier von grundlegender Bedeutung, denn wie wir oben gesehen haben, ist die 400000-fache Berechnung einer ähnlichen Operation in Python nicht gerade die cleverste Idee.

Die Vektorisierung ist ein Prozess, bei dem diese elementweisen Operationen gruppiert werden, so dass NumPy sie viel schneller ausführen kann. Im obigen Code haben Sie bereits ein paar Beispiele für vektorisierte Operationen gesehen:

points = random.randn(400000, 2) * 0.01
points[:, 0] = points[:, 0] + godatadriven[0]

Die Skalierung von randn um 0,01 erforderte keine zwei for-Schleifen für jedes seiner Elemente: wir wiesen NumPy einfach an, das gesamte Array mit 0,01 zu multiplizieren, und das war erledigt. Dasselbe gilt, wenn wir godatadriven[0] zu points[:, 0] hinzufügen: Wir mussten nicht für jedes Element eine for-Schleife schreiben, denn auch hier hat NumPy das erledigt.

Das heißt, hier ist die vektorisierte Operation zur Ermittlung der Entfernung in NumPy:

%timeit get_distance(points[:, 0], points[:, 1], godatadriven[0], godatadriven[1])
# runs in 21.5 ms!

was etwa 165 Mal schneller ist!

Mit Pandas alles zusammenfügen

Nehmen wir an, Sie haben einen Pandas-Datenrahmen mit der vollständigen Liste der Postleitzahlen

import pandas as pd
zip = pd.read_csv("zip.csv", names=["zip", "lat", "lon"], index = "zip")

und dass Sie, wenn Sie eine Postleitzahl und einen bestimmten Radius angeben, eine Liste der Postleitzahlen erhalten möchten, die innerhalb des angegebenen Radius liegen. Das können Sie mit dem folgenden Code erreichen:

def get_zips(postal_code, radius):
    """
    Return the postal code that are within radius of postal_code.
    """
    lat, lon = zip.ix[postal_code]
    zip_distance = get_distance(zip.lat, zip.lon, lat, lon) < radius
    return zip[zip_distance].index.values

Dank der vektorisierten Natur der NumPy-Operationen (einschließlich des Vergleichs mit radius im vorherigen Codeabschnitt) wird die Prüfung in wenigen Millisekunden durchgeführt, wodurch sie sich gut für Echtzeit-Webanwendungen eignet. Und nicht nur das: Der resultierende Code ist sehr sauber und pythonisch und erfordert sogar weniger Eingaben als eine Listenverarbeitung.

Hinweis: Wenn Sie Lust haben, finden Sie ein IPython-Notebook mit dem Leistungstest online bei nbviewer. Die dort angegebenen Zeiten können leicht von den Zeiten in diesem Beitrag abweichen.