R:Измерение времени выполнения выражений

 Поделиться 

	Материал «R:Измерение времени выполнения выражений», созданный автором Артём Клевцов, публикуется на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
	Вы можете свободно: делиться произведением – копировать, распространять и передавать данное произведение. создавать производные – переделывать данное произведение. При соблюдении следующих условий: указание авторства - Вы должны указывать авторство (источник) данного произведения в виде, установленном автором или лицензиаром (но ни в коем случае не таким образом, который наводит на мысль, что автор поддерживает вас или ваше использование данного произведения). http://creativecommons.org/licenses/by/4.0 CC-BY-4.0 Creative Commons Attribution 4.0 true true

Для измерения времени выполнения выражений используют следующие инструменты:

• Функция Шаблон:Inline-code из базового пакета;
• Cпециализированные функции (benchmarks, бенчмарки);
• Функция профилирования времени выполнения кода Шаблон:Inline-code.

Функция system.time()

Самый простой инструмент для измерения времени выполнения кода - функция Шаблон:Inline-code из пакета Шаблон:Inline-code. В качестве аргумента функция Шаблон:Inline-code принимает выражения и возвращает время выполнения данного выражения. Измерим время выполнения функции Шаблон:Inline-code, которая останавливает выполнение кода на заданный интервал времени (в секундах):

<syntaxhighlight lang="rsplus"> > system.time(Sys.sleep(1)) пользователь система прошло

      0.003        0.004        1.000

</syntaxhighlight>

Как видим, на выполнение данной операции заняло ровно одну секунду.

Приведём ещё один пример. Сравним время вычисления встроенной в R функции Шаблон:Inline-code и среднего, вычисленного по формуле [math]\frac{1}{n}\sum_{i=1}^{n}x_{i}[/math]. на сгенерированном массиве нормально распределенных значений:

<syntaxhighlight lang="rsplus"> > x <- rnorm(10^7L) > system.time(mean(x)) пользователь система прошло

      0.020        0.000        0.023

> system.time(sum(x) / length(x)) пользователь система прошло

      0.013        0.000        0.012

</syntaxhighlight>

Функция возвращает 3 значения:

• user - время CPU, которое занял пользователь;
• system - время CPU, которое заняла система;
• elapsed - реальное время, которое заняло выполнение команды.

Соответственно, в выводе функции нас интересует значение Шаблон:Inline-code, который показывает время выполнения функции (выражения) в секундах. Как мы видим, внешне более сложное выражение Шаблон:Inline-code выполняется быстрее стандартной функции Шаблон:Inline-code.

К сожалению, подобный способ достаточно ненадежен, так как для оценки времени выполнения выражения функция Шаблон:Inline-code обращается к системным значениям времени. Следовательно, если во время выполнения кода параллельно производятся и другие операции на компьютере (а такое случается практически в ста процентах случаев), то возможно увеличение времени выполнения R-кода. Некоторую вариативность результатов можно увидеть, даже если выполнить функцию Шаблон:Inline-code несколько раз подряд. Подобной неточности оценки можно избежать путём многократного повторения выполняемых выражений и вычислением среднего времени, что позволит сгладить часть вариаций.

Проиллюстрируем вышесказанное на примере:

<syntaxhighlight lang="rsplus"> > replicate(10, system.time(mean(x))"elapsed")

[1] 0.024 0.020 0.019 0.018 0.017 0.016 0.015 0.015 0.015 0.015

</syntaxhighlight>

В этом примере с помощью функции Шаблон:Inline-code мы повторили выражение Шаблон:Inline-code 10 раз, отфильтровав вывод функции Шаблон:Inline-code так, чтобы нам выводилось только время выполнения команды, дописав Шаблон:Inline-code. Как мы видим, время выполнения при повторном выполнении выражения может отличаться.

Базовый пакет позволяет реализовать процедуру многократного повторения выражения функции как минимум двумя способами. Первый - функция Шаблон:Inline-code. Приведенное выше сопоставление времени выполнения двух выражений при использовании функции Шаблон:Inline-code будет выглядеть следующим образом:

<syntaxhighlight lang="rsplus"> > system.time(replicate(100, mean(x))) пользователь система прошло

      1.580        0.000        1.586

> system.time(replicate(100, sum(x) / length(x))) пользователь система прошло

      0.817        0.016        0.835

</syntaxhighlight>

Тот же самый эффект можно получить и с помощью обычного цикла Шаблон:Inline-code:

<syntaxhighlight lang="rsplus"> > system.time(for (i in seq_len(100)) mean(x)) пользователь система прошло

      1.583        0.000        1.590

> system.time(for (i in seq_len(100)) sum(x) / length(x)) пользователь система прошло

      0.797        0.000        0.800

</syntaxhighlight>

Можно также использовать описательные статистики в сочетании с множественными повторениями:

<syntaxhighlight lang="rsplus"> > median(replicate(100, system.time(mean(x))"elapsed")) [1] 0.0155 </syntaxhighlight>

В примере выше мы взяли только значения Шаблон:Inline-code и рассчитали медиану .

Вместо подобных решений можно использовать специальные пакеты, предназначенные для измерения производительности кода, в частности, пакеты Шаблон:Inline-code и Шаблон:Inline-code. Основной принцип работы этих пакетов заключается в многократном выполнении выражений и расчёта ряда интегральных показателей, в частности, суммы, среднего значения или медианы времени выполнения всех попыток.

Пакет rbenchmark

Основа пакета Шаблон:Inline-code - функция Шаблон:Inline-code. Данная функция работает следующим образом: указанные в качестве аргументов выражения выполняются заданное количество раз (по умолчанию 100) и вычисляется время, затраченное на выполнение всех попыток. В качестве аргументов функции Шаблон:Inline-code необходимо передать выражения или функции, а также количество повторений, передаваемых аргументом replications.

Для примера возьмём несколько способов расчёта среднего арифметического для сгенерированного массива данных.

<syntaxhighlight lang="rsplus"> > x <- replicate(10, rnorm(10^6L)) </syntaxhighlight>

Использованные нами способы - функции векторизованных вычислений (Шаблон:Inline-code, Шаблон:Inline-code), стандартный цикл и специальная функция вычисления средних по столбцам Шаблон:Inline-code. Представим эти способы в виде самостоятельных функций для удобства их вызова при работе с Шаблон:Inline-code:

<syntaxhighlight lang="rsplus"> colMeansApply <- function(x) {

 apply(x, 2, mean)

}

colMeansVapply <- function(x) {

 vapply(seq_len(ncol(x)), function(i) mean(x[, i]), FUN.VALUE = numeric(1))

}

colMeansLoop <- function(x) {

 n.vars <- ncol(x)
 res <- double(n.vars)
 for (i in seq_len(n.vars))
   res[i] <- mean(x[, i])
 return(res)

}

colMeansLoopVec <- function(x) {

 n.vars <- ncol(x)
 n <- nrow(x)
 res <- double(n.vars)
 for (i in seq_len(n.vars))
   res[i] <- sum(x[, i]) / n
 return(res)

} </syntaxhighlight>

Убедимся, что функции возвращают одинаковый результат. Сделать это можно с помощью функций Шаблон:Inline-code или Шаблон:Inline-code:

<syntaxhighlight lang="rsplus"> > identical(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x)) [1] TRUE </syntaxhighlight>

Теперь, подключив пакет rbenchmark, мы можем сравнить время работы каждого из выбранных нами способов вычисления средних по столбцам:

<syntaxhighlight lang="rsplus"> > library(rbenchmark) > benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), + colMeansLoopVec(x), colMeans(x), replications = 100)

         test replications elapsed relative user.self sys.self user.child sys.child

1 colMeansApply(x) 100 13.206 16.802 11.893 1.260 0 0 4 colMeansLoopVec(x) 100 6.931 8.818 6.793 0.113 0 0 3 colMeansLoop(x) 100 7.729 9.833 7.583 0.113 0 0 2 colMeansVapply(x) 100 7.724 9.827 7.630 0.067 0 0 5 colMeans(x) 100 0.786 1.000 0.784 0.000 0 0 </syntaxhighlight>

Наиболее важны для нас в выводе функции Шаблон:Inline-code столбцы elapsed и relative. Столбец elapsed показывает время, затраченное на выполнение интересующей нас функции. Как видим из примера, самыми медленными оказались функции Шаблон:Inline-code и Шаблон:Inline-code, а самой быстрой Шаблон:Inline-code, причём превосходит остальные по скорости выполнения как минимум в 7 раз.

Показатель relative дает информацию о разнице во времени относительно самого быстрого выражения (в нашем случае это Шаблон:Inline-code), т.е. время самого быстрого выражения берётся за единицу, и рассчитывается относительное время для остальных выражений.

Для более удобного просмотра можно отфильтровать вывод функции Шаблон:Inline-code с помощью аргумента columns. Также может быть полезен аргумент order, позволяющий отсортировать вывод по любому из столбцов. Для примера зададим набор показателей, которые мы хотим включить в таблицу (в данном случае это «test», «replications», «elapsed», «relative»), и отсортируем выдачу по столбцу «elapsed» по возрастанию значений:

<syntaxhighlight lang="rsplus"> > benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x), + replications = 100, order = "relative", + columns = c("test", "replications", "elapsed", "relative")) 5 colMeans(x) 100 0.782 1.000 4 colMeansLoopVec(x) 100 6.890 8.811 3 colMeansLoop(x) 100 7.684 9.826 2 colMeansVapply(x) 100 7.716 9.867 1 colMeansApply(x) 100 13.142 16.806 </syntaxhighlight>

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

Чтобы не указывать нужные столбцы каждый раз, когда используется функция Шаблон:Inline-code, можно закрепить заданный формат выдачи результатов (далее используется именно такой формат вывода, с сортировкой по столбцу «relative»). Для этого следует воспользоваться функцией Шаблон:Inline-code:

<syntaxhighlight lang="rsplus"> > formals(benchmark)$columns <- c("test", "replications", "elapsed", "relative") > formals(benchmark)$order <- "relative" </syntaxhighlight>

Пакет microbenchmark

Функция Шаблон:Inline-code одноименного пакета работает сходным с функцией Шаблон:Inline-code образом, но предоставляет более гибкие средства по управлению процессом выполнения выражений. Также с помощью функции Шаблон:Inline-code можно получить исходную информацию о времени выполнения каждой попытки, что даёт достаточно широкие возможности по обработке и анализу полученных результатов. В таблице ниже представлено время выполнения пяти функций вычисления среднего значения из предыдущего примера, полученное с помощью функции Шаблон:Inline-code:

<syntaxhighlight lang="rsplus"> > library(microbenchmark) > res <- microbenchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), + colMeansLoopVec(x), colMeans(x), times = 100) > print(res, unit = "ms", order = "median") Unit: milliseconds

              expr     min      lq median      uq     max neval
       colMeans(x)   7.796   7.828   7.87   7.943   8.063   100
colMeansLoopVec(x)  67.495  68.524  75.11  81.684 101.999   100
 colMeansVapply(x)  75.791  76.648  85.47  90.325  94.803   100
   colMeansLoop(x)  75.632  76.920  85.65  90.346  99.707   100
  colMeansApply(x) 102.908 127.148 132.24 136.095 144.833   100

</syntaxhighlight>

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

Вся полученная информация о попытках применения функций вычисления средних записана в отдельную переменную Шаблон:Inline-code. С помощью функции Шаблон:Inline-code можно увидеть структуру переменной:

<syntaxhighlight lang="rsplus"> > str(res) Classes ‘microbenchmark’ and 'data.frame': 500 obs. of 2 variables:

$ expr: Factor w/ 5 levels "colMeansApply(x)",..: 4 2 1 1 1 3 3 5 5 1 ...
$ time: num  1.02e+08 8.55e+07 1.04e+08 1.10e+08 1.29e+08 ...

</syntaxhighlight>

Переменная Шаблон:Inline-code, как можно увидеть в выводе функции Шаблон:Inline-code, представляет собой список (list) и включает в себя две переменные: Шаблон:Inline-code (выражение) и Шаблон:Inline-code (время выполнения). На основе этой информации и рассчитываются описательные статистики, приведённые в примере применения функции Шаблон:Inline-code. Наличие исходных данных о каждой попытке позволяет самостоятельно выбирать, рассчитывать и сравнивать предпочтитаемые показатели. Например, расчет медианного времени выполнения попытки и общего времени выполнения всех попыток для каждого выражения выглядит следующим образом:

<syntaxhighlight lang="rsplus"> > aggregate(time ~ expr, data = res, function(x) median(x) * 10^-6L)

               expr   time

1 colMeansApply(x) 132.24 2 colMeansVapply(x) 85.47 3 colMeansLoop(x) 85.65 4 colMeansLoopVec(x) 75.11 5 colMeans(x) 7.87 > aggregate(time ~ expr, data = res, function(x) sum(x) * 10^-6L)

               expr    time

1 colMeansApply(x) 13015.8 2 colMeansVapply(x) 8400.4 3 colMeansLoop(x) 8447.8 4 colMeansLoopVec(x) 7576.8 5 colMeans(x) 788.8 </syntaxhighlight>

Умножение на [math]10^{-6}[/math] --- это перевод в миллисекунды. Чтобы получить секунды, нужно, соответственно, умножить на [math]10^{-9}[/math].

Помимо настройки формата вывода, выбора показателей, наличие информации о времени выполнения выражения в каждой попытке позволяет визуализировать результаты оценки времени выполнения выражения. Например, с помощью функции Шаблон:Inline-code из пакета Шаблон:Inline-code, можно получить следующий график:

<syntaxhighlight lang="rsplus"> > library(ggplot2) > autoplot(res) </syntaxhighlight>

600px

Ещё один довольно интересный способ графического представления результатов измерения скорости выполнения кода с помощью функции Шаблон:Inline-code представлен ниже:

<syntaxhighlight lang="rsplus"> > qplot(y = time, data = res, colour = expr) </syntaxhighlight>

600px

Так же можно, если возникнет необходимость, оценить статистическую значимость различий во времени выполнения выражений. Благодаря тому, что в переменной Шаблон:Inline-code хранятся данные о времени выполнения каждой попытки из заданного числа, становится возможным использование статистических критериев. Выбор критерия - на усмотрение аналитика, в примере ниже использовался параметрический критерий сравнения групп t-Стьюдента с поправкой уровня статистической значимости Холма для множественных сравнений:

<syntaxhighlight lang="rsplus"> > pairwise.t.test(res$time, res$expr)

Pairwise comparisons using t tests with pooled SD

data: res$time and res$expr

                  colMeansApply(x) colMeansVapply(x) colMeansLoop(x) colMeansLoopVec(x)

colMeansVapply(x) <2e-16 - - - colMeansLoop(x) <2e-16 0.62 - - colMeansLoopVec(x) <2e-16 <2e-16 <2e-16 - colMeans(x) <2e-16 <2e-16 <2e-16 <2e-16

P value adjustment method: holm </syntaxhighlight>

Из вышеприведённого вывода видно, что скорость выполнения всех функций статистически значимо разлиается у всех функций, за исключением пары Шаблон:Inline-code - Шаблон:Inline-code (p-уровень = 0.62).