Dlaczego pętle są wolne w R?

Wiem, że pętle są powolne Ri że zamiast tego powinienem spróbować robić rzeczy w sposób zwektoryzowany.

Ale dlaczego? Dlaczego pętle są wolne i applyszybkie? applywywołuje kilka podfunkcji - to nie wydaje się szybkie.

Aktualizacja: przepraszam, pytanie było źle postawione. Mylę wektoryzację z apply. Moje pytanie powinno brzmieć:

„Dlaczego wektoryzacja jest szybsza?”

Pętle w R są powolne z tego samego powodu, dla którego każdy język interpretowany jest powolny: każda operacja niesie ze sobą dużo dodatkowego bagażu.

Spójrz na R_execClosureweval.c (jest to funkcja o nazwie wywołać funkcję zdefiniowaną przez użytkownika). Ma prawie 100 linii i wykonuje różnego rodzaju operacje - tworzenie środowiska do wykonywania, przypisywanie argumentów do środowiska itp.

Pomyśl, o ile mniej się dzieje, gdy wywołujesz funkcję w C (wstawiaj argumenty do stosu, przeskakuj, zmieniaj argumenty).

Dlatego otrzymujesz takie czasy (jak zauważył joran w komentarzu, tak naprawdę nie applyjest to szybkie; to wewnętrzna pętla C mean jest szybka. applyTo zwykły stary kod R):

A = matrix(as.numeric(1:100000))

Korzystanie z pętli: 0,342 sekundy:

system.time({
    Sum = 0
    for (i in seq_along(A)) {
        Sum = Sum + A[[i]]
    }
    Sum
})

Korzystanie z sumy: niewymiernie małe:

sum(A)

To trochę niepokojące, ponieważ asymptotycznie pętla jest tak samo dobra jak sum; nie ma praktycznego powodu, dla którego powinno być wolne; po prostu robi więcej dodatkowej pracy w każdej iteracji.

Więc rozważ:

# 0.370 seconds
system.time({
    I = 0
    while (I < 100000) {
        10
        I = I + 1
    }
})

# 0.743 seconds -- double the time just adding parentheses
system.time({
    I = 0
    while (I < 100000) {
        ((((((((((10))))))))))
        I = I + 1
    }
})

(Ten przykład odkrył Radford Neal )

Ponieważ (w R jest operatorem i faktycznie wymaga wyszukiwania nazwy za każdym razem, gdy go używasz:

> `(` = function(x) 2
> (3)
[1] 2

Lub, ogólnie rzecz biorąc, operacje interpretowane (w dowolnym języku) mają więcej kroków. Oczywiście te kroki również przynoszą korzyści: nie można zrobić tej (sztuczki w C.

Nie zawsze jest tak, że pętle są powolne i applyszybkie. Jest miło omówione w majowym numerze R News z 2008 roku :

Uwe Ligges i John Fox. R Help Desk: Jak uniknąć tej pętli lub ją przyspieszyć? R News, 8 (1): 46-50, maj 2008.

W sekcji „Pętle!” (zaczynając od str. 48), mówią:

Wiele komentarzy na temat języka R stwierdza, że ​​używanie pętli jest szczególnie złym pomysłem. To niekoniecznie jest prawdą. W niektórych przypadkach trudno jest napisać kod wektoryzowany lub kod wektoryzowany może zużywać ogromną ilość pamięci.

Ponadto sugerują:

• Zainicjuj nowe obiekty do pełnej długości przed pętlą, zamiast zwiększać ich rozmiar w pętli.
• Nie rób w pętli rzeczy, które można wykonać poza pętlą.
• Nie unikaj pętli tylko ze względu na ich unikanie.

Mają prosty przykład, w którym forpętla trwa 1,3 sekundy, ale applyzabrakło pamięci.

Jedyną odpowiedzią na postawione pytanie jest; pętle nie są powolne, jeśli to, co musisz zrobić, to iterować po zestawie danych wykonujących jakąś funkcję, a ta funkcja lub operacja nie jest wektoryzowana. for()Pętla będzie tak szybkie, w ogóle, jak apply(), ale prawdopodobnie trochę wolniej niż lapply()rozmowy. Ostatni punkt jest dobrze omówiony w SO, na przykład w tej odpowiedzi , i ma zastosowanie, jeśli kod zaangażowany w tworzenie i obsługę pętli jest znaczącą częścią ogólnego obciążenia obliczeniowego pętli .

Wiele osób uważa, że for()pętle są powolne, ponieważ to oni, jako użytkownicy, piszą zły kod. Ogólnie (choć jest kilka wyjątków), jeśli musisz rozwinąć / powiększyć obiekt, będzie to również wymagało kopiowania, abyś miał zarówno narzut kopiowania, jak i powiększania obiektu. Nie ogranicza się to tylko do pętli, ale jeśli kopiujesz / rozwijasz w każdej iteracji pętli, oczywiście pętla będzie powolna, ponieważ będziesz ponosić wiele operacji kopiowania / powiększania.

Ogólnym idiomem używania for()pętli w R jest przydzielenie wymaganej pamięci przed rozpoczęciem pętli, a następnie wypełnienie tak przydzielonego obiektu. Jeśli zastosujesz się do tego idiomu, pętle nie będą powolne. To właśnie apply()Ci służy, ale jest po prostu niewidoczne.

Oczywiście, jeśli istnieje funkcja zwektoryzowana dla operacji, którą implementujesz za pomocą for()pętli, nie rób tego . Podobnie, nie używaj apply()etc, jeśli istnieje funkcja wektoryzowana (np. apply(foo, 2, mean)Jest lepiej wykonywana przez colMeans(foo)).

Dla porównania (nie czytaj zbyt wiele!): Uruchomiłem (bardzo) prostą pętlę for w R i JavaScript w Chrome i IE 8. Zauważ, że Chrome kompiluje do kodu natywnego, a R z kompilatorem pakiet kompiluje się do kodu bajtowego.

# In R 2.13.1, this took 500 ms
f <- function() { sum<-0.5; for(i in 1:1000000) sum<-sum+i; sum }
system.time( f() )

# And the compiled version took 130 ms
library(compiler)
g <- cmpfun(f)
system.time( g() )

@Gavin Simpson: Przy okazji, zajęło to 1162 ms w S-Plus ...

I „ten sam” kod co JavaScript:

// In IE8, this took 282 ms
// In Chrome 14.0, this took 4 ms
function f() {
    var sum = 0.5;
    for(i=1; i<=1000000; ++i) sum = sum + i;
    return sum;
}

var start = new Date().getTime();
f();
time = new Date().getTime() - start;