Por que os loops são lentos em R?

86

Eu sei que os loops são lentos Re que, em vez disso, devo tentar fazer as coisas de maneira vetorial.

Mas por que? Por que os loops são lentos e applysão rápidos? applychama várias subfunções - isso não parece rápido.

Atualização: sinto muito, a pergunta foi mal colocada. Eu estava confundindo vetorização com apply. Minha pergunta deveria ter sido,

"Por que a vetorização é mais rápida?"

isomorfismos
fonte
3
Fiquei com a impressão de que "aplicar é muito mais rápido do que loops for" em R é um pouco um mito . Que as system.timeguerras nas respostas comecem ...
joran
1
Muitas informações boas aqui sobre o tópico: stackoverflow.com/questions/2275896/…
Chase
7
Para o registro: Aplicar NÃO é vetorização. Aplicar é uma estrutura de loop com efeitos colaterais diferentes (como em: não). Veja os links de discussão @Chase para.
Joris Meys
4
Os loops em S ( S-Plus ?) Eram tradicionalmente lentos. Este não é o caso com R ; como tal, sua pergunta não é realmente relevante. Não sei qual é a situação do S-Plus hoje.
Gavin Simpson
4
não está claro para mim por que a questão foi rejeitada fortemente - essa questão é muito comum entre aqueles que vêm de outras áreas para R e deve ser adicionada ao FAQ.
patrickmdnet de

Respostas:

69

Os loops em R são lentos pela mesma razão que qualquer linguagem interpretada é lenta: cada operação carrega consigo uma grande quantidade de bagagem extra.

Observe R_execClosureemeval.c (esta é a função chamada para chamar uma função definida pelo usuário). Tem quase 100 linhas de comprimento e executa todos os tipos de operações - criando um ambiente para execução, atribuindo argumentos ao ambiente, etc.

Pense no quanto menos acontece quando você chama uma função em C (empurre args para empilhar, pule, pop args).

É por isso que você obtém tempos como estes (como joran apontou no comentário, não está realmente applysendo rápido; é o loop C interno mean que está sendo rápido. applyÉ apenas um código R antigo normal):

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

Usando um loop: 0,342 segundos:

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

Usando soma: incomensuravelmente pequena:

sum(A)

É um pouco desconcertante porque, assintoticamente, o loop é tão bom quanto sum; não há razão prática para que seja lento; está apenas fazendo mais trabalho extra a cada iteração.

Portanto, 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
    }
})

(Esse exemplo foi descoberto por Radford Neal )

Porque (em R é um operador e, na verdade, requer uma pesquisa de nome toda vez que você o usa:

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

Ou, em geral, as operações interpretadas (em qualquer idioma) têm mais etapas. Claro, essas etapas também oferecem benefícios: você não poderia fazer esse (truque em C.

Owen
fonte
10
Então, qual é o objetivo do último exemplo? Não faça coisas estúpidas em R e espere que isso aconteça rapidamente?
Chase de
6
@Chase Eu acho que é uma maneira de dizer isso. Sim, eu quis dizer que uma linguagem como C não teria nenhuma diferença de velocidade com parênteses aninhados, mas R não otimiza ou compila.
Owen
1
Também (), ou o {} no corpo do loop - todas essas coisas envolvem pesquisas de nome. Ou em geral, em R quando você escreve mais, o intérprete faz mais.
Owen
1
Não tenho certeza de que ponto você está tentando fazer com os for()loops? Eles não estão fazendo a mesma coisa de forma alguma. O for()loop está iterando sobre cada elemento Ae somando-os. A apply()chamada está passando o vetor inteiro A[,1](você Atem uma única coluna) para uma função vetorizada mean(). Não vejo como isso ajuda a discussão e apenas confunde a situação.
Gavin Simpson
3
@Owen, concordo com seu ponto geral, e é importante; não usamos R porque está batendo recordes de velocidade, usamos porque é fácil de usar e muito poderoso. Esse poder vem com o preço da interpretação. Não estava claro o que você estava tentando mostrar no exemplo for()vs. apply()Acho que você deve remover esse exemplo, pois embora a soma seja a grande parte do cálculo da média, tudo o que seu exemplo realmente mostra é a velocidade de uma função vetorizada mean(), sobre a iteração do tipo C sobre os elementos.
Gavin Simpson
78

Nem sempre os loops são lentos e applyrápidos. Há uma boa discussão sobre isso na edição de maio de 2008 da R News :

Uwe Ligges e John Fox. R Help Desk: Como posso evitar esse loop ou torná-lo mais rápido? R News, 8 (1): 46-50, maio de 2008.

Na seção "Loops!" (começando na página 48), eles dizem:

Muitos comentários sobre R afirmam que usar loops é uma ideia particularmente ruim. Isto não é necessariamente verdade. Em certos casos, é difícil escrever código vetorizado, ou o código vetorizado pode consumir uma grande quantidade de memória.

Eles ainda sugerem:

  • Inicialize novos objetos com o comprimento total antes do loop, em vez de aumentar seu tamanho dentro do loop.
  • Não faça coisas em um loop que podem ser feitas fora dele.
  • Não evite loops simplesmente para evitar loops.

Eles têm um exemplo simples em que um forloop leva 1,3 segundos, mas applyfica sem memória.

Karl
fonte
35

A única resposta à pergunta colocada é; os loops não são lentos se o que você precisa fazer é iterar sobre um conjunto de dados executando alguma função e essa função ou operação não é vetorizada. Um for()loop será tão rápido, em geral, quanto apply(), mas possivelmente um pouco mais lento do que uma lapply()chamada. O último ponto é bem abordado no SO, por exemplo, nesta resposta , e se aplica se o código envolvido na configuração e operação do loop for uma parte significativa da carga computacional geral do loop .

O motivo pelo qual muitas pessoas pensam que os for()loops são lentos é porque eles, o usuário, estão escrevendo um código incorreto. Em geral (embora haja várias exceções), se você precisar expandir / aumentar um objeto, isso também envolverá a cópia, de modo que você tem a sobrecarga de copiar e aumentar o objeto. Isso não se restringe apenas a loops, mas se você copiar / aumentar a cada iteração de um loop, é claro, o loop ficará lento porque você está incorrendo em muitas operações de copiar / aumentar.

O idioma geral para usar for()loops em R é que você aloca o armazenamento necessário antes do início do loop e, em seguida, preenche o objeto assim alocado. Se você seguir esse idioma, os loops não serão lentos. Isso é o que apply()gerencia para você, mas está apenas oculto.

Obviamente, se existir uma função vetorizada para a operação que você está implementando com o for()loop, não faça isso . Da mesma forma, não use apply()etc. se existir uma função vetorizada (por exemplo, apply(foo, 2, mean)é melhor executada via colMeans(foo))

Gavin Simpson
fonte
9

Apenas como uma comparação (não leia muito sobre isso!): Eu executei um loop for (muito) simples em R e em JavaScript no Chrome e IE 8. Observe que o Chrome compila para código nativo e R com o compilador pacote compila em bytecode.

# 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: A propósito, demorou 1162 ms no S-Plus ...

E o "mesmo" código do 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
fonte