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

 

Режиссерская версия

По согласованию со Станиславом мы публикуем обновленную версию статьи про циклы в R — в авторской редакции, со сравнительными тестами и со слегка измененной структурой. Не волнуйся, никаких багов в старой статье не было, а при написании этой версии материала не пострадал ни один программист :).

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

 

О циклах

Начнем с того, что часто бывает неприятным сюрпризом для тех, кто переходит на R с классических языков программирования: если вы хотите написать цикл, то прежде чем это делать, стоит на секунду задуматься. Дело в том, что в языках для работы с большим объемом данных циклы, как правило, уступают по эффективности специализированным функциям запросов, фильтрации, агрегации и трансформации данных. Это легко запомнить, если вспомнить о базах данных, где большинство операций производится с помощью языка запросов SQL, а не с помощью циклов.

Посмотрим в цифрах, насколько это важное правило. Допустим, у нас есть очень простая таблица из двух столбцов a и b. Первый столбец растет от 1 до 100 000, второй — уменьшается со 100 000 до 1:

testDF <- data.frame(a = 1:100000, b = 100000:1)

Если мы хотим посчитать третий столбец c, который будет суммой a и b, то вы удивитесь, как много начинающих R-разработчиков могут написать код такого вида:

for(row in 1:nrow(testDF))
    testDF[row, "c"] <- testDF[row, "a"] + testDF[row, "b"] # Ужас!!!

На моем ноутбуке расчеты занимают 44,942 секунды, хотя того же результата можно достичь за 0,002 секунды, воспользовавшись базовым функционалом работы с таблицами:

testDF$c <- testDF$a + testDF$b

Или можно воспользоваться специальными функциями для работы с таблицами из пакета dplyr:

testDF <- testDF %>% mutate(c = a + b)

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

Сегодня рассмотрим:

  1. Классические циклы (for, while, repeat).
  2. Циклы на основе apply (apply, lapply, sapply, vapply).
  3. Foreach.
 

Классические циклы (for, while, repeat)

R поддерживает основные классические способы написания циклов — for, while и repeat. В некоторых источниках к циклам в R относят только эту группу функций, считая все остальное «конструкциями для написания повторяющихся операций», но я принадлежу к многочисленным сторонникам того, что классические циклы являются просто отдельной группой циклов. Кроме знакомого синтаксиса, эту группу циклов отличает то, что они всегда возвращают NULL, и если в результате цикла необходимо получить какое-то значение, то это надо реализовывать самому с помощью создания нужной переменной.

 

for

for — самый распространенный тип циклов, и его синтаксис знаком разработчикам на различных языках программирования. for выполняет переданную ему функцию для каждого элемента. Например:

# Напечатаем номера от 1 до 10
for(i in 1:10)
    print(i)

# Напечатаем все строки из вектора strings
strings <- c("Один", "Два", "Три")
for(str in strings)
    print(str)

Мы уже пробовали воспользоваться for в самом начале статьи, хотя и получили ужасные результаты. Напомню, что пример работал 44,942 секунды. Попробуем улучшить этот результат.

Главное правило при написании цикла состоит в том, что если что-то можно вынести за цикл, то лучше так и сделать. Для начала вынесем операции записи в таблицу из цикла. Создадим новую переменную result и сразу выделим нужный ей объем памяти:

result <- integer(100000)

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

result <- integer(100000)
for(row in 1:nrow(testDF))
    result[row] <- testDF[row, "a"] + testDF[row, "b"]
testDF[, "c"] <- result

Время выполнения упало до 2,783 секунды, то есть стало меньше на порядок.

Дальше можно уйти от передачи названия колонок в виде строковых параметров. То есть заменим обращения вида testDF[row, "a"] на testDF$a[row]:

result <- integer(100000)
for(row in 1:nrow(testDF))
    result[row] <- testDF$a[row] + testDF$b[row]
testDF$c <- result

Время выполнения упало до 1,668.

Пойдем дальше и уйдем вообще от обращения к таблице в цикле. Сохраним значения столбцов a и b в отдельные переменные перед циклом и в итерациях будем работать именно с ними:

result <- integer(100000)
a <- testDF$a
b <- testDF$b
for(row in 1:nrow(testDF))
result[row] <- a[row] + b[row]
testDF$c <- result

Время выполнения упало до 0,130 секунды, то есть почти в 350 раз быстрее первой версии, но все еще на пару порядков медленнее функций работы с таблицами, да и код стал менее читаемый.

Построим график зависимости времени выполнения от количества строчек в таблице:

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

Впрочем, последний график все равно показывает, насколько использование цикла, пусть даже и сильно оптимизированного, не подходит для этой задачи:

 

while

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

while(cond)
    expr
 

repeat

repeat — наименее встречаемый из классических циклов. Цикл повторяется до тех пор, пока в явном виде не будет вызван оператор break:

repeat
    expr

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

 

Циклы на основе apply

apply, eapply, lapply, mapply, rapply, sapply, tapply, vapply — достаточно большой список функций-циклов, объединенных одной идеей. Основным отличием циклов, основанных на apply, от классических является то, что возвращается результат работы цикла, состоящий из результатов, полученных на каждой итерации.

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

 

apply

Начнем с базового apply, который применяется к матрицам:

apply(X, MARGIN, FUN, ...)

В первом параметре, X, указываем исходную матрицу, во втором параметре, MARGIN, уточняем способ обхода матрицы (1 — по строкам, 2 — по столбцам, с(1,2) — по строкам и столбцам), третьим параметром указываем функцию FUN, которая будет вызвана для каждого элемента. Результаты всех вызовов будут объединены в один вектор или матрицу, которую функция apply и вернет в качестве результирующего значения.

Например, создадим матрицу m размером 3 х 3.

m <- matrix(1:9, nrow = 3, ncol = 3)

print(m)
         [,1] [,2] [,3]
 [1,]       1    4    7
 [2,]       2    5    8
 [3,]       3    6    9

Попробуем функцию apply в действии:

apply(m, MARGIN = 1, FUN = sum) # Сумма ячеек для каждой строчки
[1] 12 15 18

apply(m, MARGIN = 2, FUN = sum) # Сумма ячеек для каждого столбца
[1]  6 15 24

Для простоты я передал в apply существующую функцию sum, но вы можете использовать свои собственные функции, собственно поэтому apply и является полноценной реализацией цикла. Например, заменим сумму на нашу функцию, которая сначала производит суммирование, и если сумма равна 15, то заменяет возвращаемое значение на 100.

apply(m, MARGIN = 1, # Вызов нашей функции для каждой строчки
  FUN = function(x)  # Определяем нашу функцию прямо в вызове apply
  {
    s <- sum(x)   # Считаем сумму
    if (s == 15)  # Если сумма равна 15, то заменяем ее на 100
      s <- 100
    (s)
  }
)
[1]  12 100  18

Если в apply можно делать операции над каждой строчкой, то, значит, можно использовать apply для решения нашей первой задачи и сравнить результаты с тем, что получилось в for.

Применим apply к первоначальной таблице, выбрав обработку по строчкам, и в качестве применяемой функции укажем базовую суммирующую функцию sum. В итоге apply вернет вектор, где для каждой строки будет указана сумма ее колонок. Добавим этот вектор в качестве нового столбца первоначальной таблице и получим искомый результат:

a_plus_b <- apply(testDF, 1,sum)
testDF$c <- a_plus_b

Замер времени выполнения показывает 0,152 секунды, что достаточно неплохо. Посмотрим на графике, как это соотносится с временем выполнения for:

Видно, что apply за счет отсутствия записей в таблицу на каждой итерации и быстрого чтения данных показывает хорошее время и работает гораздо быстрее третьей версии нашего for-скрипта, но при этом финальная версия for все равно выигрывает за счет отсутствия чтения из исходной таблицы во время цикла.

 

lapply (sapply, vapply)

Другой распространенной функцией из семейства apply является lapply.

lapply(X, FUN, ...)

Первым параметром передается список или вектор, а вторым — функция, которую надо вызвать для каждого элемента. Функции sapply и vapply являются обертками вокруг lapply. Первая пытается привести результат к вектору, матрице или массиву. Вторая добавляет проверку типов возвращаемого значения.

Достаточно распространенным способом применения sapply является работа с колонками. Например, возьмем таблицу:

data <- data.frame(co1_num = 1, col2_num = 2, col3_char = "a", col4_char = "b")

Если в sapply передать таблицу, то она будет рассматриваться как список колонок (векторов). Поэтому применив sapply к нашему data.frame и указав в качестве вызываемой функции is.numeric, мы проверим, какие столбцы являются числовыми:

sapply(data, is.numeric)
co1_num  col2_num col3_char col4_char
   TRUE      TRUE     FALSE     FALSE

Выведем на экран только столбцы с числовыми значениями:

data[,sapply(data, is.numeric)]
  co1_num col2_num
1       1        2

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

Реализуем наш пример с использованием lapply, а так как нам нужен вектор значений (колонка с суммой a и b), то сразу воспользуемся оберткой sapply, которая приводит результат к вектору. Возьмем за основу наш лучший вариант на for и переделаем его под sapply:

a <- testDF$a
b <- testDF$b
result <- sapply(1:nrow(testDF), function(row)
  {
   (a[row] + b[row])
  })
testDF$c <- result

Так как мы заранее знаем возвращаемый тип для каждой итерации, то можно также попробовать заменить sapply на vapply, указав в параметре FUN.VALUE, что каждая итерация возвращает одно целое число integer(1):

a <- testDF$a
b <- testDF$b
result <- vapply(1:nrow(testDF), FUN.VALUE = integer(1), function(row)
{
  (a[row] + b[row])
})
testDF$c <- result

Результаты сравнения скорости выполнения приведены на графике:

Заметно, что vapply чуть быстрее, чем sapply, так как мы заранее указали тип, возвращаемый на каждой итерации. Получился хороший результат, но все равно оптимальный for отрабатывает намного быстрее.

 

foreach

foreach не является базовой для языка R функцией. Соответствующий пакет необходимо установить и подключить перед вызовом:

install.packages("foreach")  # Установка пакета на компьютер (один раз)
library(foreach)             # Подключение пакета

Несмотря на то что foreach является сторонней функцией, на сегодняшний день это очень популярный подход к написанию циклов. foreach был разработан одной из самых уважаемых в мире R компанией — Revolution Analytics, создавшей свой коммерческий дистрибутив R. В 2015 году компания была куплена Microsoft, и сейчас все ее наработки входят в состав Microsoft SQL Server R Services. Впрочем, foreach является обычным open source проектом под лицензией Apache License 2.0.

Основные причины популярности foreach:

  • синтаксис похож на for, который, как я уже говорил, является самым популярным видом циклов;
  • foreach возвращает значения, которые собираются из результатов каждой итерации, при этом можно определить свою функцию и реализовать любую логику сбора финального значения цикла из результатов итераций;
  • возможность использовать многопоточность и запускать итерации параллельно.

Начнем c простого. Для чисел от 1 до 10 на каждой итерации число умножается на 2. Результаты всех итераций записываются в переменную result в виде списка:

result <- foreach(i = 1:10) %do%
    (i*2)

Если мы хотим, чтобы результатом был не список, а вектор, то необходимо указать c в качестве функции для объединения результатов:

result <- foreach(i = 1:10, .combine = "c") %do%
    (i*2)

Можно даже просто сложить все результаты, объединив их с помощью оператора +, и тогда в переменную result будет просто записано число 110:

result <- foreach(i = 1:10, .combine = "+") %do%
    (i*2)

При этом в foreach можно указывать одновременно несколько переменных для обхода. Пусть переменная a растет от 1 до 10, а b уменьшается от 10 до 1. Тогда мы получим в result вектор из десяти чисел 11:

result <- foreach(a = 1:10, b = 10:1, .combine = "c") %do%
    (a+b)

Итерации циклов могут возвращать не только простые значения. Допустим, у нас есть функция, которая возвращает data.frame:

customFun <- function(param)
{
    data.frame(param = param, result1 = sample(1:100, 1), result2 = sample(1:100, 1))
}

Если мы хотим вызвать эту функцию 100 раз и объединить результаты в один data.frame, то в .combine для объединения можно использовать функцию rbind:

result <- foreach(param = 1:100,.combine = "rbind") %do%
    customFun(param)

В результате в переменной result у нас собрана единая таблица результатов.

В .combine можно также использовать свою собственную функцию, причем с помощью дополнительных параметров можно оптимизировать производительность, если ваша функция умеет принимать больше чем два параметра за один раз (в документации foreach можно почитать описание параметров .multicombine и .maxcombine).

При этом стоит понимать, что для совсем простых операций, вроде нашего примера, foreach приспособлен плохо — слишком много накладных расходов на инициализацию каждой транзакции. foreach хорош, когда каждая итерация занимает достаточно много времени и требуется агрегировать результаты выполнения всех итераций. В этом случае код с использованием foreach получается хорошо читаемый.

Однако главное преимущество foreach заключается в легкости перехода от последовательной обработки к параллельной. Фактически этот переход осуществляется заменой %do% на %dopar%, но при этом есть несколько нюансов.

Во-первых, до вызова foreach у вас уже должен быть зарегистрирован parallel backend. В R есть несколько популярных реализаций parallel backend: doParallel, doSNOW, doMC, и у каждого есть свои особенности, но предлагаю для простоты выбрать первый и написать несколько строчек кода для его подключения:

library(doParallel)     # Загружаем библиотеку в память
cl <- makeCluster(8)    # Создаем «кластер» на восемь потоков
registerDoParallel(cl)  # Регистрируем «кластер»

Если сейчас вызвать цикл из восьми итераций, каждая из которых просто ждет секунду, то будет видно, что цикл отработает за одну секунду, так как все итерации будут запущены параллельно:

system.time({
    foreach(i=1:8) %dopar% Sys.sleep(1) #
})

user  system elapsed
0.008   0.005   1.014

После использования parallel backend можно остановить:

stopCluster(cl)

Нет никакой необходимости каждый раз перед foreach создавать, а затем удалять parallel backend. Как правило, он создается один раз в программе и используется всеми функциями, которые могут с ним работать.

Во-вторых, вам надо явно указать, какие пакеты необходимо загрузить в рабочие потоки с помощью параметра .packages.

Например, вы хотите на каждой итерации создавать файл с помощью пакета readr, который загрузили в память перед вызовом foreach. В случае последовательного цикла (%do%) все отработает без ошибок:

library(readr)
foreach(i=1:8) %do%
    write_csv(data.frame(id = 1), paste0("file", i, ".csv"))

При переходе на параллельную обработку (%dopar%) цикл закончится с ошибкой:

library(readr)
foreach(i=1:8) %do%
    write_csv(data.frame(id = 1), paste0("file", i, ".csv"))

Error in write_csv(data.frame(id = 1), paste0("file", i, ".csv")) :
task 1 failed - "could not find function "write_csv""

Ошибка возникает, так как внутри параллельного потока не загружен пакет readr. Исправим ее с помощью параметра .packages:

foreach(i=1:8, .packages = "readr") %dopar%
    write_csv(data.frame(id = 1), paste0("file", i, ".csv"))

В-третьих, вывод на консоль в параллельном потоке не отображается на экране. Иногда это может здорово усложнить отладку, поэтому обычно сложный код сначала пишут без параллельности, а потом заменяют %do% на %dopar%. Вывод на экран из параллельных потоков возможно настроить в parallel backend doSNOW. Для этого необходимо при создании кластера указать дополнительный параметр outfile="":

library(doSNOW)
cl <- makeCluster(4, outfile="")
registerDoSNOW(cl)

На текущий момент, к сожалению, этот трюк работает не на всех платформах — есть поддержка Mac и Linux, но на Windows вывод на экран не поддерживается.

Хочу напомнить, что параллельность вычислений не всегда означает увеличение скорости выполнения. Например, если на каждой итерации все процессорное время занимается на 100%, то, запустив эту операцию на этом же процессоре в несколько потоков, мы увеличим общее время выполнения, так как процессор будет переключаться между задачами. Кроме того, каждый поток создаст свою копию данных, и загрузка оперативной памяти резко возрастет. Этот пример подчеркивает, что надо заранее понимать, какого эффекта планируется достигнуть при использовании параллельной обработки.

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

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

Возьмем внешний веб-сервис http://md5.jsontest.com, который считает MD5 для переданной строки. Создадим вектор тестовых строк:

string_list <- sapply(1:size, function(x) sprintf("string %2d", x))

Напишем цикл, который для каждой строчки из этого списка вызывает веб-сервис:

library(RCurl)
library(jsonlite)

results_do <- foreach(str = string_list, .combine = c) %do%
{
    out = getURL(url = sprintf("http://md5.jsontest.com/?text=%s", URLencode(str)),
                 postfields = "{}",
                 httpheader = "Content-Type: application/json;charset=utf-8",
                 verbose=FALSE)
    checkResult <- fromJSON(out)
    (checkResult$md5)
}

Большую часть времени этого цикла займет обмен данными между веб-сервисом, поэтому если переписать его на параллельную обработку, то общее время выполнения может существенно сократиться:

library(doParallel)     # Загружаем библиотеку в память
cl <- makeCluster(8)    # Создаем «кластер» на восемь потоков
registerDoParallel(cl)  # Регистрируем «кластер»

results_dopar <- foreach(str = string_list, .combine = c, .packages = c("RCurl", "jsonlite")) %dopar%
{
  out = getURL(url = sprintf("http://md5.jsontest.com/?text=%s", URLencode(str)),
               postfields = "{}",
               httpheader = "Content-Type: application/json;charset=utf-8",
               verbose=FALSE)
  checkResult <- fromJSON(out)
  (checkResult$md5)
}
stopCluster(cl)

Ниже приведен график зависимости времени выполнения от общего количества обрабатываемых строк для последовательной обработки, обработки в четыре и восемь потоков:

 

Выводы

  • При работе с большим объемом данных циклы не всегда являются лучшим выбором. Использование специализированных функций для выборки, агрегации и трансформации данных всегда эффективнее циклов.
  • R предлагает множество вариантов реализации циклов. Основное отличие классических for, while и repeat от группы функций на основе apply заключается в том, что последние возвращают значение.
  • Использование циклов foreach из одноименного внешнего пакета позволяет упростить написание циклов, гибко оперировать с возвращаемыми итерациями значениями, а за счет подключения многопоточной обработки еще и здорово увеличить производительность решения.

1 комментарий

  1. baragoz

    24.01.2017 at 12:54

    Таак, отпишитесь кто что понял? )

Оставить мнение

Check Also

Что можно сделать с iPhone, зная пасскод. Как сливают данные, уводят iCloud и блокируют остальные устройства

Последние несколько месяцев мы много писали о нововведениях в iOS 11. «Теперь-то заживем!»…