Dlaczego pętle są wolne w R?


86

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?”


3
Odniosłem wrażenie, że „zastosowanie jest o wiele szybsze niż w przypadku pętli” w R to trochę mit . Niech system.timewojny w odpowiedziach się zaczną ...
joran

1
Wiele dobrych informacji na ten temat: stackoverflow.com/questions/2275896/ ...
Chase

7
Dla przypomnienia: Apply to NIE wektoryzacja. Zastosuj to struktura pętli z różnymi (np. Nie) efektami ubocznymi. Zobacz dyskusję @Chase, do której prowadzą linki.
Joris Meys

4
Pętle w S ( S-Plus ?) Były tradycyjnie powolne. Tak nie jest w przypadku R ; jako takie, twoje pytanie nie jest naprawdę istotne. Nie wiem, jaka jest dzisiaj sytuacja z S-Plus .
Gavin Simpson

4
nie jest dla mnie jasne, dlaczego to pytanie zostało mocno odrzucone - to pytanie jest bardzo częste wśród osób przybywających do R z innych obszarów i powinno zostać dodane do FAQ.
patrickmdnet

Odpowiedzi:


69

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.


10
Jaki jest więc sens ostatniego przykładu? Nie rób głupstw w R i spodziewasz się, że zrobią to szybko?
Chase

6
@Chase Myślę, że to jeden ze sposobów, aby to powiedzieć. Tak, miałem na myśli, że język taki jak C nie miałby różnicy prędkości z zagnieżdżonymi nawiasami, ale R nie optymalizuje ani nie kompiluje.
Owen

1
Również () lub {} w treści pętli - wszystkie te rzeczy obejmują wyszukiwanie nazw. Lub ogólnie rzecz biorąc, w R kiedy piszesz więcej, tłumacz robi więcej.
Owen

1
Nie jestem pewien, do czego zmierzasz z for()pętlami? W ogóle nie robią tego samego. for()Pętli kolejno po każdym elemencie Ai ich sumowanie. apply()Rozmowa przechodzi całą wektor A[,1](imię Ama jedną kolumnę) do wektoryzowane funkcji mean(). Nie rozumiem, jak to pomaga w dyskusji i po prostu myli sytuację.
Gavin Simpson

3
@Owen Zgadzam się z twoją ogólną uwagą i jest ona ważna; nie używamy R, ponieważ bije rekordy prędkości, używamy go, ponieważ jest łatwy w użyciu i bardzo potężny. Ta moc wiąże się z ceną interpretacji. Po prostu nie było jasne, co próbujesz pokazać w przykładzie z for()vs. apply()Myślę, że powinieneś usunąć ten przykład, ponieważ podczas gdy sumowanie jest dużą częścią obliczania średniej, cały twój przykład naprawdę pokazuje prędkość funkcji wektoryzowanej mean(), nad iteracją podobną do C po elementach.
Gavin Simpson,

78

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.


35

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)).


9

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;
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.