¿Por qué los bucles son lentos en R?

86

Sé que los bucles son lentos Ry que debería intentar hacer las cosas de manera vectorizada.

¿Pero por qué? ¿Por qué los bucles son lentos y applyrápidos? applyllama a varias subfunciones, eso no parece rápido.

Actualización: lo siento, la pregunta estaba mal planteada. Confundía vectorización con apply. Mi pregunta debería haber sido,

"¿Por qué la vectorización es más rápida?"

isomorfismos
fuente
3
Tenía la impresión de que "aplicar es mucho más rápido que los bucles for" en R es un mito . Que system.timecomiencen las guerras en las respuestas ...
joran
1
Mucha buena información aquí sobre el tema: stackoverflow.com/questions/2275896/…
Chase
7
Para el registro: Aplicar NO es vectorización. Apply es una estructura de bucle con diferentes (como en: no) efectos secundarios. Vea los enlaces de discusión de @Chase a.
Joris Meys
4
Los bucles en S (¿ S-Plus ?) Eran tradicionalmente lentos. Este no es el caso de R ; como tal, su pregunta no es realmente relevante. No sé cuál es la situación con S-Plus hoy.
Gavin Simpson
4
No me queda claro por qué la pregunta ha sido rechazada en gran medida; esta pregunta es muy común entre los que vienen a R de otras áreas y debe agregarse a las preguntas frecuentes.
patrickmdnet

Respuestas:

69

Los bucles en R son lentos por la misma razón que cualquier lenguaje interpretado es lento: cada operación conlleva mucho equipaje adicional.

Mire R_execClosureeneval.c (esta es la función llamada para llamar a una función definida por el usuario). Tiene casi 100 líneas de largo y realiza todo tipo de operaciones: crear un entorno de ejecución, asignar argumentos al entorno, etc.

Piense en cuánto menos sucede cuando llama a una función en C (presione args para apilar, saltar, hacer pop args).

Entonces, es por eso que obtienes tiempos como estos (como Joran señaló en el comentario, en realidad no es applyque sea rápido; es el bucle C interno lo mean que es rápido. applyEs solo un código R antiguo normal):

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

Usando un bucle: 0.342 segundos:

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

Usando sum: inmensurablemente pequeño:

sum(A)

Es un poco desconcertante porque, asintóticamente, el bucle es tan bueno como sum; no hay ninguna razón práctica para que sea lento; solo está haciendo más trabajo extra en cada iteración.

Así que considere:

# 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
    }
})

(Ese ejemplo fue descubierto por Radford Neal )

Porque (en R es un operador, y en realidad requiere una búsqueda de nombre cada vez que lo usa:

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

O, en general, las operaciones interpretadas (en cualquier idioma) tienen más pasos. Por supuesto, esos pasos también brindan beneficios: no podría hacer ese (truco en C.

Owen
fuente
10
Entonces, ¿cuál es el punto del último ejemplo? ¿No haces cosas estúpidas en R y esperas que las haga rápidamente?
Chase
6
@Chase Supongo que es una forma de decirlo. Sí, quise decir que un lenguaje como C no tendría diferencia de velocidad con paréntesis anidados, pero R no optimiza ni compila.
Owen
1
También (), o el {} en el cuerpo del bucle; todas estas cosas implican búsquedas de nombres. O en general, en R cuando escribes más, el intérprete hace más.
Owen
1
No estoy seguro de qué punto estás tratando de hacer con los for()bucles. No están haciendo lo mismo en absoluto. El for()ciclo itera sobre cada elemento Ay los suma. La apply()llamada pasa todo el vector A[,1]( Atiene una sola columna) a una función vectorizada mean(). No veo cómo esto ayuda a la discusión y solo confunde la situación.
Gavin Simpson
3
@Owen Estoy de acuerdo con su punto general, y es importante; no usamos R porque está rompiendo récords de velocidad, lo usamos porque es fácil de usar y muy potente. Ese poder viene con el precio de la interpretación. Simplemente no estaba claro qué estaba tratando de mostrar en el ejemplo de for()vs. apply()Creo que debería eliminar ese ejemplo, ya que si bien la suma es la mayor parte del cálculo de la media, todo lo que su ejemplo realmente muestra es la velocidad de una función vectorizada mean(), sobre la iteración similar a C sobre los elementos.
Gavin Simpson
78

No siempre es el caso de que los bucles sean lentos y applyrápidos. Hay una buena discusión sobre esto en la edición de mayo de 2008 de R News :

Uwe Ligges y John Fox. R Help Desk: ¿Cómo puedo evitar este bucle o hacerlo más rápido? R News, 8 (1): 46-50, mayo de 2008.

En la sección "¡Bucles!" (a partir de la página 48), dicen:

Muchos comentarios sobre R afirman que usar bucles es una idea particularmente mala. Esto no necesariamente es cierto. En ciertos casos, es difícil escribir código vectorizado o el código vectorizado puede consumir una gran cantidad de memoria.

Sugieren además:

  • Inicialice nuevos objetos en su longitud completa antes del bucle, en lugar de aumentar su tamaño dentro del bucle.
  • No hagas cosas en un ciclo que se puedan hacer fuera del ciclo.
  • No evite los bucles simplemente por evitar bucles.

Tienen un ejemplo simple en el que un forbucle tarda 1,3 segundos pero se applyqueda sin memoria.

Karl
fuente
35

La única respuesta a la pregunta planteada es; Los bucles no son lentos si lo que necesita hacer es iterar sobre un conjunto de datos que realizan alguna función y esa función o la operación no está vectorizada. Un for()bucle será tan rápido, en general, como apply(), pero posiblemente un poco más lento que una lapply()llamada. El último punto está bien cubierto en SO, por ejemplo en esta Respuesta , y se aplica si el código involucrado en la configuración y operación del bucle es una parte significativa de la carga computacional general del bucle .

La for()razón por la que mucha gente piensa que los bucles son lentos es porque ellos, el usuario, están escribiendo un código incorrecto. En general (aunque hay varias excepciones), si necesita expandir / hacer crecer un objeto, eso también implicará copiar para que tenga la sobrecarga de copiar y hacer crecer el objeto. Esto no solo está restringido a los bucles, sino que si copia / crece en cada iteración de un bucle, por supuesto, el bucle será lento porque está incurriendo en muchas operaciones de copia / crecimiento.

El lenguaje general para usar for()bucles en R es que usted asigna el almacenamiento que necesita antes de que comience el bucle y luego completa el objeto así asignado. Si sigue ese modismo, los bucles no serán lentos. Esto es lo que funciona apply()por ti, pero simplemente está oculto a la vista.

Por supuesto, si existe una función vectorizada para la operación que está implementando con el for()ciclo, no haga eso . Del mismo modo, no use apply()etc si existe una función vectorizada (por ejemplo, apply(foo, 2, mean)se realiza mejor a través de colMeans(foo)).

Gavin Simpson
fuente
9

Solo como una comparación (¡no lea demasiado!): Ejecuté un bucle for (muy) simple en R y en JavaScript en Chrome e IE 8. Tenga en cuenta que Chrome compila en código nativo y R con el compilador. el paquete se compila en código de bytes.

# 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: Por cierto, tomó 1162 ms en S-Plus ...

Y el "mismo" código que 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;
Tommy
fuente