Почему петли медленно в R?

Question

Я знаю, что циклы медленны в R и что вместо этого я должен попытаться сделать что-то векторизованным образом.

Но почему?Почему петли медленные, а apply быстрые?apply вызывает несколько подфункций - это не кажется быстрым.

Обновление: Извините, вопрос был некорректным.Я путал векторизацию с apply.Мой вопрос должен был звучать так:

«Почему векторизация происходит быстрее?»

Answer 1

Не всегда бывает так, что петли медленные, а apply быстрые.Хорошее обсуждение этого в выпуске R News : *1003*:

Уве Лиггеса и Джона Фокса.R Help Desk: Как я могу избежать этого цикла или сделать его быстрее?R News, 8 (1): 46-50, май 2008 г.

В разделе «Петли!»(начиная со стр. 48), они говорят:

Во многих комментариях о R говорится, что использование циклов является особенно плохой идеей.Это не обязательно правда.В некоторых случаях трудно писать векторизованный код, или векторизованный код может занимать огромный объем памяти.

Они также предлагают:

• Инициализировать новыйобъекты до полной длины перед циклом, а не увеличивая их размер внутри цикла.
• Не делайте в цикле того, что можно сделать вне цикла.
• Не избегайте петель просто ради того, чтобы избегать петель.

У них есть простой пример, когда цикл for занимает 1,3 с, но apply не хватает памяти.

Answer 2

Циклы в R медленные по той же причине, что и любой интерпретируемый язык медленный: каждая операция влечет за собой много дополнительного багажа.

Посмотрите на R_execClosure в eval.c (это функция, вызываемая для вызова пользовательской функции).Он длиной почти 100 строк и выполняет все виды операций - создание среды для выполнения, назначение аргументов в среду и т. Д.

Подумайте, насколько меньше будет происходить, когда вы вызываете функцию в C (выдвигайте аргументы наstack, jump, pop args).

Вот почему вы получаете такие моменты времени (как указывал Джоран в комментарии, на самом деле это не apply, это быстро, это внутренний цикл C в mean это быстро. apply это просто обычный старый код R):

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

Использование цикла: 0,342 секунды:

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

Использование суммы: неизмеримо мало:

sum(A)

Это немного сбивает с толку, потому что, асимптотически, цикл так же хорош, как sum;нет никакой практической причины, это должно быть медленным;это просто делает больше дополнительной работы каждую итерацию.

Итак, рассмотрим:

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

(Этот пример был обнаружен Рэдфорд Нил )

Потому что ( в R является оператором и фактически требует поиска имени каждый раз, когда вы его используете:

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

Или, как правило, интерпретируемые операции (на любом языке) имеют больше шагов.Конечно, эти шаги также дают преимущества: вы не можете сделать этот ( трюк в C.

Answer 3

Единственный ответ на поставленный вопрос:циклы не медленные , если , то вам нужно выполнить итерацию по набору данных, выполняющих некоторую функцию, и эта функция или операция не векторизована.Цикл for() в целом будет таким же быстрым, как apply(), но, возможно, немного медленнее, чем вызов lapply().Последний пункт хорошо освещен в SO, например, в этом Ответе , и применяется, если код, участвующий в настройке и работе цикла , является значительной частью общей вычислительной нагрузкицикл .

Почему многие думают, что циклы for() медленные, потому что они, пользователь, пишут плохой код.В общем случае (хотя есть несколько исключений), если вам нужно расширить / увеличить объект, это также будет включать копирование, поэтому у вас будут и накладные расходы на копирование и увеличения объекта.Это не ограничивается только циклами, но если вы копируете / увеличиваете на каждой итерации цикла, конечно, цикл будет медленным, потому что вы выполняете много операций копирования / увеличения.

Общая идиомаиспользование циклов for() в R заключается в том, что вы выделяете требуемое хранилище перед началом цикла, а затем заполняете выделенный таким образом объект.Если вы будете следовать этой идиоме, петли не будут медленными.Это то, чем apply() управляет для вас, но оно просто скрыто от глаз.

Конечно, если существует векторизованная функция для операции, которую вы реализуете с помощью цикла for(), don 'сделать это .Аналогично, не используйте apply() и т. Д., Если существует векторизованная функция (например, apply(foo, 2, mean) лучше выполнять с помощью colMeans(foo)).

Answer 4

Просто для сравнения (не читайте слишком много!): Я запустил (очень) простой цикл for в R и в JavaScript в Chrome и IE 8. Обратите внимание, что Chrome выполняет компиляцию в собственный код, а R с пакетом компилятора компилируется в байт-код.

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

@ Гэвин Симпсон: Кстати, в S-Plus это заняло 1162 мс ...

И тот же код, что и в 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;