Das Problem ist, dass es unglaublich einfach ist, Anweisungen zu schreiben, die nicht bedeuten, was Sie denken. Zum Beispiel kann ein Programm der Computerinterpretation völlig widersprechen. Außerdem,Es gibt buchstäblich keine Möglichkeit zu sagen, ob ein Programm überhaupt beendet wird, ohne es auszuführen. Und es gibt viele, viele Möglichkeiten, die Ausführung eines Programms erheblich zu verlangsamen. Ich meine ... wirklich langsamer. Verlangsamen Sie es, damit es Ihr ganzes Leben oder länger dauert. Dies geschieht am häufigsten bei Programmen, die von Personen ohne Computerausbildung geschrieben wurden, dh von Wissenschaftlern aus anderen Bereichen. Meine Aufgabe ist es, solche Programme zu reparieren.
Die Leute verstehen nicht, dass die Informatik Ihnen die Theorie der Berechnung, die Komplexität der Algorithmen und die Berechenbarkeit lehrt (dh können wir wirklich etwas berechnen? Zu oft halten wir es für selbstverständlich, dass wir es können!). Die Informatik liefert das Wissen, die Logik und die Analysemethoden, um beim Schreiben zu helfen Code, der in minimaler Zeit oder mit minimalem Ressourcenverbrauch ausgeführt wird.
Lassen Sie mich Ihnen ein Beispiel für eine enorme Optimierung in einem einfachen Skript zeigen, das von einem meiner Kollegen geschrieben wurde.
Wir skalieren viel in der Klimatologie. Wir nehmen Temperatur- und Niederschlagswerte aus einem großen globalen Klimamodell und vergleichen sie mit einem feinskaligen lokalen Gitter. Angenommen, das globale Raster ist 50 x 25 und das lokale Raster ist 1000 x 500. Für jede Gitterzelle im lokalen Gitter möchten wir wissen, welcher Gitterzelle im globalen Gitter sie entspricht.
Eine einfache Möglichkeit, das Problem darzustellen, besteht darin, den Abstand zwischen L [n] und G [n] zu minimieren. Es stellt sich eine solche Suche heraus:
L[i]:
G[j]:
L[i] G[j]
L[i] * G
Scheint einfach genug. Wenn Sie genau hinschauen, leisten wir jedoch viel zusätzliche Arbeit. Betrachten Sie den Algorithmus in Bezug auf die Größe der Eingabe.
L[i]: # L
G[j]: # L x G
L[i] G[j] # L x G
d[i*j] # G L (L x G)
, # G L (L x G)Der Code sieht ungefähr so aus:
obs.lon <- ncvar_get(nc.obs, 'lon')
obs.lat <- ncvar_get(nc.obs, 'lat')
n.lon <- length(obs.lon)
n.lat <- length(obs.lat)
obs.lats <- matrix(obs.lat, nrow=n.lon, ncol=n.lat, byrow=TRUE)
obs.lons <- matrix(obs.lon, nrow=n.lon, ncol=n.lat)
obs.time <- netcdf.calendar(nc.obs)
gcm.lon <- ncvar_get(nc.gcm, 'lon')-360
gcm.lat <- ncvar_get(nc.gcm, 'lat')
gcm.lats <- matrix(gcm.lat, ncol=length(gcm.lat), nrow=length(gcm.lon),
byrow=TRUE)
gcm.lons <- matrix(gcm.lon, ncol=length(gcm.lat), nrow=length(gcm.lon))
gcm.lons.lats <- cbind(c(gcm.lons), c(gcm.lats))
# Figure out which GCM grid boxes are associated with each fine-scale grid point
# Confine search to 10 deg. x 10 deg. neighbourhood
dxy <- 10
mdist <- function(x, y)
apply(abs(sweep(data.matrix(y), 2, data.matrix(x), '-')), 1, sum)
nn <- list()
for (i in seq_along(obs.lons)) {
if((i %% 500)==0) cat(i, '')
gcm.lims <- ((gcm.lons.lats[,1] >= (obs.lons[i]-dxy)) &
(gcm.lons.lats[,1] <= (obs.lons[i]+dxy))) &
((gcm.lons.lats[,2] >= (obs.lats[i]-dxy)) &
(gcm.lons.lats[,2] <= (obs.lats[i]+dxy)))
gcm.lims <- which(gcm.lims)
nn.min <- which.min(mdist(c(obs.lons[i], obs.lats[i]),
gcm.lons.lats[gcm.lims,]))
nn[[i]] <- gcm.lims[nn.min]
}
nn <- unlist(nn)Es sieht aus wie ein einfacher Algorithmus. Es ist „einfach“, die Entfernungen zu berechnen und dann das Minimum zu finden. Bei einer solchen Implementierung steigen jedoch mit zunehmender Anzahl lokaler Zellen unsere Rechenkosten um das Produkt mit der Anzahl der Zellen im globalen Raster. Die kanadischen ANUSPLIN-Daten enthalten 1068 × 510 Zellen (insgesamt 544 680). Angenommen, unser GCM enthält 50 x 25 Zellen (insgesamt 1250). Somit betragen die Kosten des inneren Zyklus in "einigen Recheneinheiten":
wo Mitglieder Entsprechen Konstanten den Kosten für die Berechnung des Abstands zwischen zwei Punkten, die Ermittlung des Mindestpunkts und die Ermittlung des Array-Index? Konstante Mitglieder interessieren uns nicht wirklich (sehr), da sie nicht von der Größe der Eingabe abhängen. Sie können sie also einfach addieren und die Berechnungskosten schätzen.
Für diese Reihe von Eingaben sind unsere Kosten also ...
680 Millionen.
Es scheint viel ... obwohl, wer weiß? Computer sind schnell, oder? Wenn wir eine naive Implementierung ausführen, läuft sie in Wirklichkeit etwas schneller als 1668 Sekunden, was etwas weniger als einer halben Stunde entspricht.
> source('BCCA/naive.implementation.R')
500 1000 1500 2000 2500 3000 ... 543000 543500 544000 544500 [1] "Elapsed Time"
user system elapsed
1668.868 8.926 1681.728 Aber sollte das Programm 30 Minuten laufen? Das ist das Problem. Wir vergleichen zwei Gitter, von denen jedes eine Menge Strukturen aufweist, die wir in keiner Weise verwendet haben. Zum Beispiel sind Breiten- und Längengrade in beiden Gittern in sortierter Reihenfolge. Um eine Nummer zu finden, müssen Sie daher nicht das gesamte Array durchgehen. Sie können den Halbierungsalgorithmus verwenden - schauen Sie sich den Punkt in der Mitte an und entscheiden Sie, welche Hälfte des Arrays wir möchten. Wenn Sie dann den gesamten Bereich durchsuchen, wird der Basislogarithmus des gesamten Suchraums verwendet.
Eine weitere wichtige Struktur, die wir nicht verwendet haben, ist die Tatsache, dass die Breiten in die Dimension gehenund Längengrade - in der Dimension ... Also anstatt die Operation durchzuführen da können wir es machen Zeit. Dies ist eine enorme Optimierung.
Wie sieht es im Pseudocode aus?
local[x]:
bisect_search(local[x], Global[x])
local[y]:
bisect_search(local[y], Global[y])
2d In Code:
## Perform a binary search on the *sorted* vector v
## Return the array index of the element closest to x
find.nearest <- function(x, v) {
if (length(v) == 1) {
return(1)
}
if (length(v) == 2) {
return(which.min(abs(v - x)))
}
mid <- ceiling(length(v) / 2)
if (x == v[mid]) {
return(mid)
} else if (x < v[mid]) {
return(find.nearest(x, v[1:mid]))
}
else {
return((mid - 1) + find.nearest(x, v[mid:length(v)]))
}
}
regrid.one.dim <- function(coarse.points, fine.points) {
return(sapply(fine.points, find.nearest, coarse.points))
}
## Take a fine scale (e.g. ANUSPLINE) grid of latitudes and longitudes
## and find the indicies that correspond to a coarse scale (e.g. a GCM) grid
## Since the search is essentially a minimizing distance in 2 dimensions
## We can actually search independently in each dimensions separately (which
## is a huge optimization, making the run time x + y instead of x * y) and
## then reconstruct the indices to create a full grid
regrid.coarse.to.fine <- function(coarse.lats, coarse.lons, fine.lats, fine.lons) {
xi <- regrid.one.dim(gcm.lon, obs.lon)
yi <- regrid.one.dim(gcm.lat, obs.lat)
## Two dimensional grid of indices
xi <- matrix(xi, ncol=length(fine.lats), nrow=length(fine.lons), byrow=F)
yi <- matrix(yi, ncol=length(fine.lats), nrow=length(fine.lons), byrow=T)
return(list(xi=xi, yi=yi))
}Die Kosten für jede Halbierungssuche sind ein Protokoll der Eingabegröße. Dieses Mal ist unsere Eingabegröße in X- und Y-Raum aufgeteilt, also werden wir verwenden und für Global, Local, X und Y.
Die Kosten liegen bei 553.076. Nun, 553k klingt viel besser als 680m. Wie wirkt sich das auf die Laufzeit aus?
> ptm <- proc.time(); rv <- regrid.coarse.to.fine(gcm.lat, gcm.lon, obs.lat, obs.lon); print('Elapsed Time'); print(proc.time() - ptm)[1] "Elapsed Time"
user system elapsed
0.117 0.000 0.117
> str(rv)
List of 2
$ xi: num [1:1068, 1:510] 15 15 15 15 15 15 15 15 15 15 ...
$ yi: num [1:1068, 1:510] 13 13 13 13 13 13 13 13 13 13 ...
> 0,117 Sekunden. Was früher fast eine halbe Stunde dauerte, dauert jetzt etwas mehr als eine Zehntelsekunde.
> 1668.868 / .117
[1] 14263.83Soooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo, aber auch ich überrascht und beeindruckt , wie viel die Beschleunigung. Ungefähr 14 Tausend Mal .
Bisher war das Skript so langsam, dass das Ergebnis zur manuellen Überprüfung durch Wissenschaftler auf der Festplatte gespeichert wurde, bevor es fortgesetzt wurde. Jetzt ist alles im Handumdrehen berechnet. Wir führen solche Berechnungen hunderte Male durch, so dass wir am Ende Tage und sogar Wochen Rechenzeit sparen. Und wir haben die Möglichkeit, besser mit dem System zu interagieren, damit die Arbeitszeit der Wissenschaftler rentabler wird. Sie sitzen nicht untätig und warten auf das Ende der Berechnungen. Alles ist auf einmal fertig.
Ich muss betonen, dass diese epischen Leistungsverbesserungen nicht den Kauf großer Computersysteme, Parallelisierung oder erhöhte Komplexität erfordern. Tatsächlich ist der schnellere Algorithmuscode noch einfacher und vielseitiger! Dieser vollständige Sieg wurde einfach durch sorgfältiges Lesen des Codes und einige Kenntnisse über die Komplexität der Berechnungen erreicht.