R-Code beschleunigen: Schleifen vs. Vektorisierung vs. Lookup-Tables

Kurzfassung:
R erlaubt dem Anwender, vergleichsweise schnell Analysecode zu schreiben, da die formalen Anforderungen gering sind. Dafür gilt R nicht zu unrecht als vergleichsweise langsam hinsichtlich der Code-Laufzeit. Wir vergleichen drei Varianten, einem Datensatz mit Skat-Karten die Werte der Spielkarten zuzuordnen. Vektorisierter Code ist dabei um Längen schneller als eine Schleife. Eine noch schnellere Variante, ein Lookup-Table, dürfte hingegen viel weniger bekannt sein.

Programmieren mit R

Die Open Source-Software R ist ein ausgezeichnetes Werkzeug für die interaktive Datenanalyse. Analysen können leicht in Skripten hinterlegt und damit reproduzierbar gemacht werden. Wer sich von der statistischen Seite an R heranwagt, kann vieles erreichen, ohne im engeren Sinn „professionell“ zu programmieren. R erleichtert den Einstieg auf diese Weise, indem es im Vergleich zu anderen Programmiersprachen an vielen Stellen weniger strikt vorgeht. So müssen etwa Variablen nicht vorab definiert werden und R bemüht sich, Variablentypen passend zu den Daten selbst bestmöglich zu bestimmen.

Werden die Analysen komplexer, dann arbeiten sich viele Anwender allmählich tiefer in die R-Programmierung. Spätestens dann stoßen viele auf einen Nachteil: Da R während der Laufzeit übersetzt wird, ist es langsamer als kompilierte Sprachen wie etwa C++.

Praxisbeispiel: Skat – den Spielkarten Werte zuweisen

In diesem Beitrag geht es um drei Möglichkeiten, einem Datensatz mit 1000 Skat-Karten die Werte der Spielkarten hinzuzufügen.

Zunächst wird ein Datensatz per Zufallsziehung mit Zurücklegen erzeugt:

set.seed(2018)
skat <- sample(c("Sieben", "Acht", "Neun", "Zehn", "Bube", "Dame", "König", "As"), size = 1000, replace = TRUE)

Für eine Häufigkeitstabelle der Karten in der richtigen (nach Skat-Regeln) Reihenfolge codieren wir die Karten als factor um:

library(forcats)
skat <- fct_relevel(skat, "Sieben", "Acht", "Neun", "Zehn", "Bube", "Dame", "König", "As")
table(skat)

skat
Sieben Acht Neun Zehn Bube Dame König As
137 122 123 116 135 127 128 112

Die Spielkarten sind nicht genau, aber einigermaßen gleich verteilt. Als nächstes wandeln wir den Vektor in einen Datensatz um und machen aus dem Faktor wieder einen Text-Vektor (character). Das ist hilfreich für Vergleiche – der factor hingegen wird intern mit Zahlencodes gespeichert.

skat <- data.frame(Karte = skat, Wert = NA)
# Wir wollen auf die Texte (Spielkarten) zugreifen, nicht auf die internen Zahlencodes des factors
skat$Karte = as.character(skat$Karte)

Um die verschiedenen Möglichkeiten, Zahlenwerte zuzuweisen, gut vergleichen zu können, packen wir die jeweiligen Anweisungen in Funktionen. Wir beginnen mit einer Schleife.

Kartenwerte zuweisen per Schleife

Schleifen gelten in R als notorisch langsam. Wir beginnen mit dieser Variante und wollen dann sehen, um wie viel schneller wir mit anderen Möglichkeiten werden.

Schleife <- function(skat) {
for (i in seq_along(skat$Karte)) {
if (skat$Karte[i] == "Sieben" | skat$Karte[i] == "Acht" | skat$Karte[i] == "Neun") {
skat$Wert[i] <- 0
} else if (skat$Karte[i] == "Bube") {
skat$Wert[i] <- 2
} else if (skat$Karte[i] == "Dame") {
skat$Wert[i] <- 3
} else if (skat$Karte[i] == "König") {
skat$Wert[i] <- 4
} else if (skat$Karte[i] == "Zehn") {
skat$Wert[i] <- 10
} else if (skat$Karte[i] == "As") {
skat$Wert[i] <- 11
}
}
skat
}

Der Code weist jeder Sieben, Acht oder Neun den Wert 0 zu, jedem Buben den Wert 2, den Damen den Wert 3, dem König den Wert 4, der Zehn die 10 sowie dem As die 11. Funktioniert das in der Praxis?

skat <- Schleife(skat)
tail(skat)

Karte Wert
995 Sieben 0
996 Dame 3
997 Zehn 10
998 As 11
999 Sieben 0
1000 Bube 2

Das sieht gut aus – jedenfalls hat es funktioniert, wenn es auch nicht besonders R-typisch oder effizient programmiert ist.

Vektorisierung: R-typisch und schneller als eine Schleife

Eine Stärke von R besteht in der Vektorisierung vieler Funktionen. Vektorisierte Funktionen nehmen einen Vektor als Eingabe anstatt nur eines einzelnen Wertes, und arbeiten ihn Element für Element ab. Dabei greifen sie auf interne, bereits kompilierte Funktionen zurück und sind somit wesentlich schneller als manuell in R programmierte Schleifen.

Hier eine vektorisierte Variante der obigen Schleife:

Vektorisiert <- function(skat) {
skat$Wert[skat$Karte == "Sieben" | skat$Karte == "Acht" | skat$Karte == "Neun"] <- 0
skat$Wert[skat$Karte == "Bube"] <- 2
skat$Wert[skat$Karte == "Dame"] <- 3
skat$Wert[skat$Karte == "König"] <- 4
skat$Wert[skat$Karte == "Zehn"] <- 10
skat$Wert[skat$Karte == "As"] <- 11
skat
}

Der „Trick“ besteht darin, dass jede Zeile nur ein Mal aufgerufen werden muss. Innerhalb der eckigen Klammern wird ein Index gebildet, der alle Zeilen des Datensatzes auswählt, auf die die jeweilige Bedingung zutrifft – also alle Zeilen mit den Karten Sieben, Acht oder Neun; dann alle Zeilen im Datensatz mit Buben, und so weiter.

Funktioniert auch diese Variante?

test <- Vektorisiert(skat)
identical(skat, test)
[1] TRUE

Ja. Wie fällt der Geschwindigkeitsvergleich aus?

Geschwindigkeitsvergleich von R-Funktionen: microbenchmark

Hier greifen wir auf das microbenchmark-Paket zu, das genauere Messungen erlaubt als system.time() und das zudem einige Visualisierungsoptionen bietet. Wir rufen jede Funktion 10 Mal auf. So können externe Einflüsse wie zum Beispiel Betriebssystemprozesse im Hintergrund besser ausgeglichen werden als bei einem einzigen Durchlauf.

library(microbenchmark)    # Paket ggf. zuvor installieren
microbenchmark(
Schleife(skat),
Vektorisiert(skat),
times = 10
)
Geschwindigkeitsvergleich: Schleife vs. Vektorisierung; Einheit: Millisekunden

Zum einen haben sich die wiederholten Durchläufe (10) gelohnt: Mindestens ein mal brauchte die Schleife wesentlich länger (97 Millisekunden vs. Mittelwert von 72 ms) als sonst. Zweitens wird der enorme Geschwindigkeitsunterschied deutlich. Median und Mittelwert weisen einen etwa 25fachen Zeitvorteil der vektorisierten Variante aus.

Alternative: Lookup-Table (Nachschlage-Tabelle)

Soweit dürfte das vielen R-Anwendern vertraut sein. Geht es noch schneller? Die folgende Variante ist inspiriert von Garrett Grolemunds Hands On Programming with R und nennt sich Lookup-Table (etwa: Nachschlage-Tabelle). So sieht der Code aus:

Lookup <- function(skat) {
tabelle <- c("Sieben" = 0, "Acht" = 0, "Neun" = 0, "Bube" = 2, "Dame" = 3, "König" = 4, "Zehn" = 10, "As" = 11)
skat$Wert <- unname(tabelle[skat$Karte])
skat
}

Die tabelle ist ein benannter numerischer Vektor (named vector) mit den Kartenbezeichnungen als Namen und den Zahlenwerten als Werten. Der Trick besteht in der unname-Funktion, die die Zuordnung der Namen zu den Werten berücksichtigt und die entsprechenden Werte zurückliefert. Vorteil gegenüber den vektorisierten Funktion: Es muss nicht für jeden Kartenwert eine eigene Codezeile geschrieben werden – der Code ist kürzer und kompakter.

Test:

test2 <- Lookup(skat)
identical(skat, test2)
[1] TRUE

Wie schnell ist diese Variante im Vergleich zur vektorisierten Funktion? Diesmal weisen wir das Ergebnis des microbenchmark-Aufrufs einem Objekt zu, um weiter darauf zugreifen zu können, insbesondere für grafische Darstellungen.

zeiten <- microbenchmark(
Schleife(skat),
Vektorisiert(skat),
Lookup(skat),
times = 10
)

zeiten
boxplot(zeiten)
autoplot(zeiten)
Geschwindigkeitsvergleich: Schleife vs. Vektorisierung vs. Lookup-Table; Einheit: Mikrosekunden

Der Lookup-Table ist um so viel schneller, dass microbenchmark die Einheit wechselt und nun Mikro- statt Millisekunden darstellt. Die Laufzeiten des Lookup-Tables schwanken recht stark, sind jedoch im Median um den Faktor 10 schneller als die vektorisierte Funktion, im Mittelwert, der von dem hohen Ausreißer nach oben beeinflusst wird, immer noch um den Faktor 4.

Grafisch sieht das so aus:

Boxplot zum Geschwindigkeitsvergleich: Schleife vs. Vektorisierung vs. Lookup-Table; Einheit: Mikrosekunden
autoplot zum Geschwindigkeitsvergleich: Schleife vs. Vektorisierung vs. Lookup-Table; Einheit: Mikrosekunden

Das Autoplot finde ich optisch etwas ansprechender und man kann die Verteilungen der je 10 Messungen etwas besser erkennen. In beiden Diagrammen ist die Zeitachse logarithmisch skaliert und in beiden erkennt man den einen Ausreißer beim Lookup-Table – ansonsten sprechen beide eine deutliche Sprache, was die Rangfolge der drei Methoden betrifft.

Zusammenfassung / TL;DR

Der Beitrag zeigt drei Möglichkeiten, einem Datensatz eine neue Variable zuzuweisen, die sich auf Texteinträge einer anderen Variable bezieht. Vektorisierte Funktionen sind in R wesentlich schneller als R-Schleifen. Es gibt hier jedoch eine noch kompaktere und schnellere Möglichkeit: Einen Lookup-Table (Nachschlage-Tabelle, Codebuch). Mit dem microbenchmark-Paket wurden die Laufzeiten verglichen.

Zum Einstieg in die R-Programmierung sei das oben genannte
Hands On Programming with R empfohlen. Wesentlich tiefer geht Hadley Wickhams Advanced R, das auch online lesbar ist:
https://adv-r.hadley.nz/

Wer sich mehr mit Datenanalyse als mit Programmierung im engeren Sinn beschäftigen möchte, sei auf R for Data Science (R4DS) verwiesen.

Freue mich über Kommentare!