Почему циклы в R медленные?

86

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

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

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

"Почему векторизация быстрее?"

изоморфизмы
источник
3
У меня создалось впечатление, что фраза «применять намного быстрее, чем циклы for» в R - это своего рода миф . Пусть system.timeначнутся войны в ответах ...
джоран
1
Здесь много полезной информации по теме: stackoverflow.com/questions/2275896/…
Чейз
7
Для справки: Apply НЕ является векторизацией. Apply - это циклическая структура с различными (например, нет) побочными эффектами. Смотрите обсуждение ссылок @Chase на.
Джорис Мейс,
4
Петли в S ( S-Plus ?) Были традиционно медленными. Это не относится к R ; как таковой, ваш вопрос не имеет отношения к делу. Я не знаю, какая сейчас ситуация с S-Plus .
Гэвин Симпсон
4
Мне неясно, почему этот вопрос был отклонен - ​​этот вопрос очень распространен среди тех, кто приходит в R из других областей, и его следует добавить в FAQ.
patrickmdnet

Ответы:

69

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

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

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

Вот почему вы получаете такие моменты времени (как указал Джоран в комментарии, на самом деле 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.

Оуэн
источник
10
Так в чем же смысл последнего примера? Не делаете глупостей в R и не ждете, что он сделает их быстро?
Чейз
6
@ Чейз, я думаю, это один из способов сказать это. Да, я имел в виду, что такой язык, как C, не будет иметь разницы в скорости с вложенными круглыми скобками, но R не оптимизирует и не компилирует.
Оуэн
1
Также () или {} в теле цикла - все это связано с поиском имени. Или вообще в R, когда вы пишете больше, интерпретатор делает больше.
Оуэн
1
Я не уверен, какой смысл вы пытаетесь донести до for()петель? Они вообще не делают то же самое. for()Цикл итерации по каждому элементу Aи их суммирования. apply()Вызов проходит весь вектор A[,1](ваш Aимеет один столбец) в vectorised функции mean(). Я не вижу, как это помогает дискуссии и просто запутывает ситуацию.
Гэвин Симпсон
3
@Owen Я согласен с вашей общей точкой зрения, и это очень важно; мы не используем R, потому что он бьет рекорды скорости, мы используем его, потому что он прост в использовании и очень мощный. Эта сила требует интерпретации. Было просто непонятно, что вы пытались показать в примере for()vs. apply()Я думаю, вам следует удалить этот пример, поскольку, хотя суммирование является большой частью вычисления среднего, все, что действительно показывает ваш пример, - это скорость векторизованной функции mean()по C-подобной итерации по элементам.
Гэвин Симпсон
78

Не всегда петли бывают медленными и applyбыстрыми. Об этом есть хорошее обсуждение в выпуске R News за май 2008 года :

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

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

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

Далее они предлагают:

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

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

Карл
источник
35

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

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

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

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

Гэвин Симпсон
источник
9

Просто для сравнения (не вдавайтесь в подробности!): Я запустил (очень) простой цикл 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;
Томми
источник