Effiziente Umsetzung summiert Bereich Tisch - /integral-Bild in R

Ich versuche zu konstruieren, ein summiert Bereich Tisch-oder integral-Bild ein Bild-matrix. Für diejenigen von Euch, die nicht wissen, was es ist, aus wikipedia:

Einem summierenden Bereich Tabelle (auch bekannt als ein integraler Bild) ist eine Datenstruktur und Algorithmus, um schnell und effizient die Erzeugung der Summe der Werte in einem rechteckigen Teil eines grid

In anderen Worten, es wird benutzt, um die Summe bis-Werte für alle rechteckigen Bereich im Bild/matrix in konstanter Zeit.

Ich versuche, dies umzusetzen, in R. Aber mein code scheint zu lange dauert.

Hier ist der pseudo-code aus dieser link. in ist die input-matrix oder Bild-und intImg ist, was zurückgegeben

for i=0 to w do 
Summe←0 

for j=0 to h do 
Summe ← Summe + in[i, j] 

wenn i = 0 dann 
intImg[i, j] ← Summe 
sonst 
intImg[i, j] ← intImg[i − 1, j] + Summe 
end if 
Ende für 
Ende für

Und hier ist meine Umsetzung

w = ncol(im) 
h = nrow(im) 
intImg = c(NA) 
Länge(intImg) = w*h 

for(i in 1:B){ #x 
Summe = 0; 
for(j in 1:r){ #y 
ind = (j-1)*w)+ (i-1) + 1 #index 
Summe = Summe + im[ind] 
if(i == 1){ 
intImg[ind] = Summe 
}else{ 
intImg[ind] = intImg[ind-1]+Summe 
} 
} 
} 
intImg = matrix(intImg, h, w, byrow=T)

Beispiel von input-und output-matrix:

Effiziente Umsetzung summiert Bereich Tisch - /integral-Bild in R

Jedoch auf eine 480x640 matrix, das dauert ~ 4 Sekunden. In dem Papier, das Sie beschreiben, es zu nehmen auf die Reihenfolge der Millisekunden, die für diese Dimensionen.

Mache ich etwas ineffizient in meine loops oder Indizierung?

Als ich das schreiben in C++ und wickelte Sie in R, aber ich bin nicht sehr vertraut mit C++.

Danke

  • ein link zu im würde, machen diese reproduzierbar. es ist schwer für mich zu analysieren, was Sie tun, ohne ein Beispiel, aber Sie können wahrscheinlich verwenden colSums() und rowSums() oder andere vektorisierte Funktion(en).
  • im ist nur irgendeine matrix. Ich habe ein Beispiel für die input-und output-in der Frage
  • Wie viel Verbesserung bekommt man durch ändern intImg = c(NA) zu intImg <- rep(NA, 480*460)?
  • Hi joran, ich habe versucht. Ändert sich nicht viel. Was ist der Unterschied?
  • Sie brauchen zum starten viel mehr spezifischen. "Nicht viel ändern" und bietet Bilder von Beispiel-Matrizen ist nicht sehr hilfreich.
  • es bezieht sich darauf, wie R hat, (wieder -) Zuweisung von Arbeitsspeicher für jede iteration einer Schleife.
  • Ändert sich nicht viel, das heißt noch etwa 4 Sekunden. 4.02 Sekunden um genau zu sein. Hier können Sie einfach kopieren, fügen Sie diese in Ihrem R-Konsole ein Beispiel für eine matrix, nicht ein Bild: m = matrix(c(4,1,2,2,0,4,1,3,3,1,0,4,2,1,3,2), 4,4,byrow=T)

InformationsquelleAutor by0 | 2013-05-14
  1. 5

    Könnten Sie versuchen, zu verwenden apply (ist nicht schneller als die for-Schleifen, wenn Sie vor der Zuteilung von Speicherplatz):

    areaTable <- function(x) {
  return(apply(apply(x, 1, cumsum), 1, cumsum))
}

areaTable(m)
#      [,1] [,2] [,3] [,4]
# [1,]    4    5    7    9
# [2,]    4    9   12   17
# [3,]    7   13   16   25
# [4,]    9   16   22   33
    • Es wird schneller sein - wenn auch wahrscheinlich nicht durch eine riesige Marge - wie Sie tun 8 cumsum Anrufe (plus die Schleife bilden-code und-Zuweisung etc) in der Erwägung, dass die OP ' s code tut viele Anrufe zu + zu geben, die äquivalent zu Ihrem cumsum Anrufe. Wie es interpretiert wird code alle diejenigen Funktionsaufrufe, addieren sich.
    • Ich bin eigentlich überrascht, wie viel schneller es wird, basierend auf einem schnellen timing von 500x500 Beispiel.
    • Ja, das geht erheblich schneller. Ich gab das warten für zwei geschachtelte for loops, die doppelt gelten, dauerte weniger als eine Sekunde.
    • Sollte ich steckte mein Erster Gedanke - ich ging zurück und hat den Nachteil, bevor der Kommentar in einem moment der Selbstzweifel. cumsum sehr effizienten code und alle, die + Anrufe sich häufen, wie die Dimension der Eingabe zu erhöhen. Profilierung der OP-code wird zeigen, dass.
    • du hast Recht, ich habe nicht darüber nachgedacht, diese Tatsache interpretiert code.
    • erklären Sie, wie können wir es schnell in c++?

    InformationsquelleAutor sgibb
Schreibe einen Kommentar