В этом материале я попытался собрать известные мне способы ускорения работы циклов. Основные способы, описанные здесь:

  • предварительное создание результирующей переменной с указанием типа и размера;
  • замена цикла на функции, поддерживающие работу с векторами или списками;
  • вынесение операций из тела цикла;
  • компиляция цикла в байт-код;
  • параллелизация выполнения цикла;

Предварительное выделение памяти

Частой задачей, решаемой с помощью циклов, является выполнение расчётов и занесение результатов в переменную. Таким образом, результирующая переменная будет заполняться данными по мере работы цикла. Предварительное выделение памяти (preallocate) позволяет ускорить работу циклов, работающих с Переменными, постепенно заполняемыми данными. Суть данного метода заключается в том, чтобы заранее выделить место в оперативной памяти, в которую будут записываться данные во время работы цикла. Выделение памяти осуществляется путём указания типа и размера переменной. Если этого не сделать, то при каждой новой итерации необходимо выделять новое место в памяти и производить туда запись.

Обратите внимание, что переменные, участвующие в цикле, должны быть объявлены до того, как будут использоваться, т.к. если вы попробуете присвоить значение индексу несуществующей переменной, то получите ошибку. Объявим функции, которые будут выполнять цикл. В первой мы объявляем пустую (NULL) переменную, во второй мы указываем размер и тип переменной.

no_alloc <- function(n) {
    x <- NULL # объявляем пустую переменную
    for (i in seq_len(n))
        x[i] <- i * i
    x
}

alloc <- function(n) {
    x <- integer(n) # объявляем переменную нужного типа и размера
    for (i in seq_len(n))
        x[i] <- i * i
    x
}

Теперь сравним время выполнения объявленных функций. Для этого используем функцию microbenchmark() из одноимённого пакета. Не забудем предварительно загрузить пакет microbenchmark.

library(microbenchmark)
microbenchmark(no_alloc(10^4), alloc(10^4))
#> Unit: milliseconds
#>            expr    min     lq   mean median     uq   max neval cld
#>  no_alloc(10^4) 52.698 53.548 62.721 55.047 77.508 87.69   100   b
#>     alloc(10^4)  5.745  5.791  6.437  5.839  6.884 31.90   100  a

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

Векторизация

Другим приёмом для ускорения работы циклов является векторизация вычисления, т.е. использование функций, которые поддерживают операции над векторами. Т.е. лучшим способ ускорить цикл является отказ от цикла.

Наш предыдущий пример с произведение элементов вектора может быть записан следующим образом:

vect1 <- function(n) {
    x <- seq_len(n)
    x * x
}

vect2 <- function(n) {
    x <- seq_len(n)
    x^2
}

Сравним производительность нашим функций:

microbenchmark(no_alloc(10^4), alloc(10^4), vect1(10^4), vect2(10^4))
#> Unit: microseconds
#>            expr      min       lq     mean   median       uq   max neval cld
#>  no_alloc(10^4) 56190.40 57117.97 68902.15 59314.60 85011.95 91744   100   c
#>     alloc(10^4)  5700.49  5737.28  6072.44  6165.08  6355.83  7081   100  b 
#>     vect1(10^4)    33.52    34.67    44.81    38.96    41.82   654   100 a  
#>     vect2(10^4)    21.57    22.82    33.61    28.77    30.93   642   100 a

Выносим код за пределы цикла

Очевидно, что чем больше операций выполняется внутри тела цикла, тем больше времени занимает цикл. Поэтому одним из направлений оптимизации цикла может быть вынесение за пределы цикла всего, что может быть вынесено. Отчасти, это можно осуществить путём векторизации вычислений, т.к. в цикле мы выполняет только те операции, которые не возможно заменить векторизованными вариантами.

Одним из частых примеров повторений кода внутри тела цикла, которое можно избежать, является условия, которые проверяются на каждой итерации цикла. Если мы вынесем условие за пределы цикла, или заменим я его векторизованной функцией, то мы сможем ускорить наш цикл.

Приведём пример функции, в которой если результат произведения чётное число, то мы записываем 1, если нечётное, то 0.

if_loop <- function(n) {
    x <- integer(n)
    for (i in seq_len(n)) {
        res <- i * i
        if (res %% 2)
            x[i] <- 1
        else
            x[i] <- 0
    }
}

Ту же саму функцию можно реализовать следующим образом:

if_vect1 <- function(n) {
    x <- integer(n)
    for (i in seq_len(n)) {
        x[i] <- i * i
    }
    ifelse(x %% 2, 1, 0)
}

if_vect2 <- function(n) {
    x <- integer(n)
    for (i in seq_len(n)) {
        x[i] <- i * i
    }
    x %% 2
}

В первом варианте мы вынесли условие за пределе цикла, и объединили конструкцию if else в вызов функции ifelse для компактности записи. Во второй функции мы использовали оператор %% напрямую, т.к. он поддерживает операции над векторами.

Сравним результат работы наших функций:

microbenchmark(if_loop(10^4), if_vect1(10^4), if_vect2(10^4))
#> Unit: milliseconds
#>            expr   min    lq  mean median    uq    max neval cld
#>   if_loop(10^4) 8.694 9.042 9.386  9.470 9.696 10.360   100   b
#>  if_vect1(10^4) 8.123 8.337 9.034  8.777 9.151 37.958   100   b
#>  if_vect2(10^4) 6.311 6.471 6.901  6.822 7.316  8.044   100  a

Компиляция в байт-код

Для оптимизации скорости выполнения в R разработан инструмент, позволяющий компилировать выражения, функции и целые скрипты в байт-код. Наиболее эффективно данный способ проявляется себя как раз при работе с циклами. Подробному описанию данного способа ускорения работы цикла посвящён отдельный материал.