R:Измерение времени выполнения выражений — различия между версиями
м |
м (Загрузка 2693-time-measure.wiki) |
||
| (не показано 7 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| + | <!-- R:Измерение времени выполнения выражений --> | ||
| + | |||
| + | |||
| + | |||
{{CC-BY-4.0|author=автором Артём Клевцов}} | {{CC-BY-4.0|author=автором Артём Клевцов}} | ||
| Строка 10: | Строка 14: | ||
== Функция <code>system.time</code> == | == Функция <code>system.time</code> == | ||
| − | Самый простой инструмент для измерения времени выполнения кода - функция <code>system.time()</code> из пакета | + | Самый простой инструмент для измерения времени выполнения кода - функция <code>system.time()</code> из пакета {{r-package|base|core=true}}. В качестве аргумента функция <code>system.time()</code> принимает выражения и возвращает время выполнения данного выражения. Измерим время выполнения функции <code>Sys.sleep()</code>, которая останавливает выполнение кода на заданный интервал времени (в секундах): |
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>system.time(Sys.sleep(1)) |
| − | > system.time(Sys.sleep(1)) | + | #> user system elapsed |
| − | + | #> 0.000 0.000 1.001 | |
| − | + | </nowiki>}} | |
| − | </nowiki> | + | |
| − | }} | + | |
Как видим, на выполнение данной операции заняло ровно одну секунду. | Как видим, на выполнение данной операции заняло ровно одну секунду. | ||
| Строка 23: | Строка 25: | ||
Приведём ещё один пример. Сравним время вычисления встроенной в R функции <code>mean()</code> и среднего, вычисленного по формуле <math>\frac{1}{n}\sum_{i=1}^{n}x_{i}</math>. на сгенерированном массиве нормально распределенных значений: | Приведём ещё один пример. Сравним время вычисления встроенной в R функции <code>mean()</code> и среднего, вычисленного по формуле <math>\frac{1}{n}\sum_{i=1}^{n}x_{i}</math>. на сгенерированном массиве нормально распределенных значений: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>x <- rnorm(10^7L) |
| − | > x <- rnorm(10^7L) | + | system.time(mean(x)) |
| − | + | #> user system elapsed | |
| − | + | #> 0.013 0.003 0.016 | |
| − | + | system.time(sum(x) / length(x)) | |
| − | + | #> user system elapsed | |
| − | + | #> 0.010 0.000 0.008 | |
| − | + | </nowiki>}} | |
| − | </nowiki> | + | |
| − | }} | + | |
Функция возвращает 3 значения: | Функция возвращает 3 значения: | ||
| Строка 45: | Строка 45: | ||
Проиллюстрируем вышесказанное на примере: | Проиллюстрируем вышесказанное на примере: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>replicate(10, system.time(mean(x))[["elapsed"]]) |
| − | > replicate(10, system.time(mean(x))[["elapsed"]]) | + | #> [1] 0.016 0.016 0.016 0.016 0.016 0.017 0.016 0.017 0.017 0.017 |
| − | [1] 0. | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
В этом примере с помощью функции <code>replicate()</code> мы повторили выражение <code>system.time(mean(x))</code> 10 раз, отфильтровав вывод функции <code>system.time()</code> так, чтобы нам выводилось только время выполнения команды, дописав <code>[["elapsed"]]</code>. Как мы видим, время выполнения при повторном выполнении выражения может отличаться. | В этом примере с помощью функции <code>replicate()</code> мы повторили выражение <code>system.time(mean(x))</code> 10 раз, отфильтровав вывод функции <code>system.time()</code> так, чтобы нам выводилось только время выполнения команды, дописав <code>[["elapsed"]]</code>. Как мы видим, время выполнения при повторном выполнении выражения может отличаться. | ||
| Строка 55: | Строка 53: | ||
Базовый пакет позволяет реализовать процедуру многократного повторения выражения функции как минимум двумя способами. Первый - функция <code>replicate()</code>. Приведенное выше сопоставление времени выполнения двух выражений при использовании функции <code>replicate()</code> будет выглядеть следующим образом: | Базовый пакет позволяет реализовать процедуру многократного повторения выражения функции как минимум двумя способами. Первый - функция <code>replicate()</code>. Приведенное выше сопоставление времени выполнения двух выражений при использовании функции <code>replicate()</code> будет выглядеть следующим образом: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>system.time(replicate(100, mean(x))) |
| − | > system.time(replicate(100, mean(x))) | + | #> user system elapsed |
| − | + | #> 1.586 0.027 1.621 | |
| − | + | system.time(replicate(100, sum(x) / length(x))) | |
| − | + | #> user system elapsed | |
| − | + | #> 0.806 0.020 0.832 | |
| − | + | </nowiki>}} | |
| − | </nowiki> | + | |
| − | }} | + | |
Тот же самый эффект можно получить и с помощью обычного цикла <code>for()</code>: | Тот же самый эффект можно получить и с помощью обычного цикла <code>for()</code>: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>system.time(for (i in seq_len(100)) mean(x)) |
| − | > system.time(for (i in seq_len(100)) mean(x)) | + | #> user system elapsed |
| − | + | #> 1.563 0.050 1.620 | |
| − | + | system.time(for (i in seq_len(100)) sum(x) / length(x)) | |
| − | + | #> user system elapsed | |
| − | + | #> 0.806 0.020 0.830 | |
| − | + | </nowiki>}} | |
| − | </nowiki> | + | |
| − | }} | + | |
Можно также использовать описательные статистики в сочетании с множественными повторениями: | Можно также использовать описательные статистики в сочетании с множественными повторениями: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>median(replicate(100, system.time(mean(x))[["elapsed"]])) |
| − | > median(replicate(100, system.time(mean(x))[["elapsed"]])) | + | #> [1] 0.016 |
| − | [1] 0. | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
В примере выше мы взяли только значения <code>elapsed</code> и рассчитали медиану <ref>Медиана является более устойчивой мерой центральной тенденции при асимметрии распределения, что, как правило, характерно для измерения времени.</ref>. | В примере выше мы взяли только значения <code>elapsed</code> и рассчитали медиану <ref>Медиана является более устойчивой мерой центральной тенденции при асимметрии распределения, что, как правило, характерно для измерения времени.</ref>. | ||
| − | Вместо подобных решений можно использовать специальные пакеты, предназначенные для измерения производительности кода, в частности, пакеты | + | Вместо подобных решений можно использовать специальные пакеты, предназначенные для измерения производительности кода, в частности, пакеты {{r-package|rbenchmark}} и {{r-package|microbenchmark}}. Основной принцип работы этих пакетов заключается в многократном выполнении выражений и расчёта ряда интегральных показателей, в частности, суммы, среднего значения или медианы времени выполнения всех попыток. |
| − | == Пакет | + | == Пакет {{r-package|rbenchmark}} == |
| − | Основа пакета | + | Основа пакета {{r-package|rbenchmark}} - функция <code>benchmark()</code>. Данная функция работает следующим образом: указанные в качестве аргументов выражения выполняются заданное количество раз (по умолчанию 100) и вычисляется время, затраченное на выполнение всех попыток. В качестве аргументов функции <code>benchmark()</code> необходимо передать выражения или функции, а также количество повторений, передаваемых аргументом replications<ref>Анализ функции <code>benchmark()</code> показал, что, данная функция использует <code>system.time()</code> и <code>replicate()</code>, рассмотренные в предыдущем разделе.</ref>. |
Для примера возьмём несколько способов расчёта среднего арифметического для сгенерированного массива данных. | Для примера возьмём несколько способов расчёта среднего арифметического для сгенерированного массива данных. | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>x <- replicate(10, rnorm(10^6L)) |
| − | > x <- replicate(10, rnorm(10^6L)) | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
Использованные нами способы - функции векторизованных вычислений (<code>apply()</code>, <code>vapply()</code>), стандартный цикл и специальная функция вычисления средних по столбцам <code>ColMeans()</code>. Представим эти способы в виде самостоятельных функций для удобства их вызова при работе с <code>benchmark()</code>: | Использованные нами способы - функции векторизованных вычислений (<code>apply()</code>, <code>vapply()</code>), стандартный цикл и специальная функция вычисления средних по столбцам <code>ColMeans()</code>. Представим эти способы в виде самостоятельных функций для удобства их вызова при работе с <code>benchmark()</code>: | ||
| − | {{r-code|code=<nowiki> | + | {{r-code|code=<nowiki>colMeansApply <- function(x) { |
| − | colMeansApply <- function(x) { | + | |
apply(x, 2, mean) | apply(x, 2, mean) | ||
} | } | ||
| Строка 127: | Строка 116: | ||
return(res) | return(res) | ||
} | } | ||
| − | </nowiki> | + | </nowiki>}} |
| − | }} | + | |
Убедимся, что функции возвращают одинаковый результат. Сделать это можно с помощью функций <code>identical()</code> или <code>all.equal()</code>: | Убедимся, что функции возвращают одинаковый результат. Сделать это можно с помощью функций <code>identical()</code> или <code>all.equal()</code>: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>identical(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x)) |
| − | > identical(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x)) | + | #> [1] TRUE |
| − | [1] TRUE | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
| − | Теперь, подключив пакет rbenchmark, мы можем сравнить время работы каждого из выбранных нами способов вычисления средних по столбцам: | + | Теперь, подключив пакет {{r-package|rbenchmark}}, мы можем сравнить время работы каждого из выбранных нами способов вычисления средних по столбцам: |
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), |
| − | + | colMeansLoopVec(x), colMeans(x), replications = 100) | |
| − | > benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), | + | #> test replications elapsed relative user.self sys.self user.child sys.child |
| − | + | #> 1 colMeansApply(x) 100 14.974 18.328 13.380 1.540 0 0 | |
| − | + | #> 4 colMeansLoopVec(x) 100 7.088 8.676 6.793 0.270 0 0 | |
| − | 1 colMeansApply(x) 100 | + | #> 3 colMeansLoop(x) 100 8.004 9.797 7.630 0.340 0 0 |
| − | 4 colMeansLoopVec(x) 100 | + | #> 2 colMeansVapply(x) 100 7.851 9.610 7.407 0.417 0 0 |
| − | 3 colMeansLoop(x) 100 | + | #> 5 colMeans(x) 100 0.817 1.000 0.787 0.026 0 0 |
| − | 2 colMeansVapply(x) 100 7. | + | </nowiki>}} |
| − | 5 colMeans(x) 100 0. | + | |
| − | </nowiki> | + | |
| − | }} | + | |
Наиболее важны для нас в выводе функции <code>benchmark()</code> столбцы <code>elapsed</code> и <code>relative</code>. Столбец <code>elapsed</code> показывает время в секундах, затраченное на выполнение интересующей нас функции. Как видим из примера, самыми медленными оказались функции <code>colMeansApply()</code> и <code>colMeansLoop()</code>, а самой быстрой <code>colMeans()</code>, причём превосходит остальные по скорости выполнения как минимум в 7 раз. | Наиболее важны для нас в выводе функции <code>benchmark()</code> столбцы <code>elapsed</code> и <code>relative</code>. Столбец <code>elapsed</code> показывает время в секундах, затраченное на выполнение интересующей нас функции. Как видим из примера, самыми медленными оказались функции <code>colMeansApply()</code> и <code>colMeansLoop()</code>, а самой быстрой <code>colMeans()</code>, причём превосходит остальные по скорости выполнения как минимум в 7 раз. | ||
| Строка 159: | Строка 142: | ||
Для более удобного просмотра можно отфильтровать вывод функции <code>benchmark()</code> с помощью аргумента <code>columns</code>. Также может быть полезен аргумент <code>order</code>, позволяющий отсортировать вывод по любому из столбцов. Для примера зададим набор показателей, которые мы хотим включить в таблицу (в данном случае это «test», «replications», «elapsed», «relative»), и отсортируем выдачу по столбцу «elapsed» по возрастанию значений: | Для более удобного просмотра можно отфильтровать вывод функции <code>benchmark()</code> с помощью аргумента <code>columns</code>. Также может быть полезен аргумент <code>order</code>, позволяющий отсортировать вывод по любому из столбцов. Для примера зададим набор показателей, которые мы хотим включить в таблицу (в данном случае это «test», «replications», «elapsed», «relative»), и отсортируем выдачу по столбцу «elapsed» по возрастанию значений: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x), |
| − | > benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x), | + | replications = 100, order = "relative", |
| − | + | columns = c("test", "replications", "elapsed", "relative")) | |
| − | + | #> test replications elapsed relative | |
| − | 5 colMeans(x) 100 0. | + | #> 5 colMeans(x) 100 0.797 1.000 |
| − | 4 colMeansLoopVec(x) 100 6. | + | #> 4 colMeansLoopVec(x) 100 6.856 8.602 |
| − | 3 colMeansLoop(x) 100 7. | + | #> 3 colMeansLoop(x) 100 7.633 9.577 |
| − | 2 colMeansVapply(x) 100 7. | + | #> 2 colMeansVapply(x) 100 7.722 9.689 |
| − | 1 colMeansApply(x) 100 | + | #> 1 colMeansApply(x) 100 15.167 19.030 |
| − | </nowiki> | + | </nowiki>}} |
| − | }} | + | |
Таким образом, сравнив несколько альтернатив решения нашей задачи, мы можем сделать обоснованный выбор в пользу наиболее эффективного варианта. | Таким образом, сравнив несколько альтернатив решения нашей задачи, мы можем сделать обоснованный выбор в пользу наиболее эффективного варианта. | ||
| Строка 175: | Строка 157: | ||
Чтобы не указывать нужные столбцы каждый раз, когда используется функция <code>benchmark()</code>, можно закрепить заданный формат выдачи результатов (далее используется именно такой формат вывода, с сортировкой по столбцу «relative»). Для этого следует воспользоваться функцией <code>formals()</code>: | Чтобы не указывать нужные столбцы каждый раз, когда используется функция <code>benchmark()</code>, можно закрепить заданный формат выдачи результатов (далее используется именно такой формат вывода, с сортировкой по столбцу «relative»). Для этого следует воспользоваться функцией <code>formals()</code>: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>formals(benchmark)$columns <- c("test", "replications", "elapsed", "relative") |
| − | > formals(benchmark)$columns <- c("test", "replications", "elapsed", "relative") | + | formals(benchmark)$order <- "relative" |
| − | + | </nowiki>}} | |
| − | </nowiki> | + | |
| − | }} | + | |
| − | == Пакет | + | == Пакет {{r-package|microbenchmark}} == |
| − | Функция <code>microbenchmark()</code> одноименного пакета работает сходным с функцией <code>benchmark()</code> образом, но предоставляет более гибкие средства по управлению процессом выполнения выражений<ref>Но в отличии от функции benchmark() использует собственную реализацию измерения времени выполнения и организацию повторных испытаний.</ref>. Особенностями реализованных в пакете | + | Функция <code>microbenchmark()</code> одноименного пакета работает сходным с функцией <code>benchmark()</code> образом, но предоставляет более гибкие средства по управлению процессом выполнения выражений<ref>Но в отличии от функции benchmark() использует собственную реализацию измерения времени выполнения и организацию повторных испытаний.</ref>. Особенностями реализованных в пакете {{r-package|microbenchmark}} являются: |
* Возможность измерения времени выполнения выражения вплоть до наносекунд; | * Возможность измерения времени выполнения выражения вплоть до наносекунд; | ||
| Строка 193: | Строка 173: | ||
В таблице ниже представлено время выполнения пяти функций вычисления среднего значения из предыдущего примера, полученное с помощью функции <code>microbenchmark()</code>: | В таблице ниже представлено время выполнения пяти функций вычисления среднего значения из предыдущего примера, полученное с помощью функции <code>microbenchmark()</code>: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>res <- microbenchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), |
| − | > res <- microbenchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), | + | colMeansLoopVec(x), colMeans(x), times = 100) |
| − | + | print(res, unit = "ms", order = "median") | |
| − | + | #> Unit: milliseconds | |
| − | Unit: milliseconds | + | #> expr min lq median uq max neval |
| − | expr min lq median uq max neval | + | #> colMeans(x) 7.805 7.824 7.841 7.865 8.295 100 |
| − | colMeans(x) 7. | + | #> colMeansLoopVec(x) 65.429 67.680 77.083 79.558 95.667 100 |
| − | colMeansLoopVec(x) 67. | + | #> colMeansVapply(x) 73.158 74.701 83.481 87.724 102.963 100 |
| − | colMeansVapply(x) | + | #> colMeansLoop(x) 73.163 75.355 85.780 87.986 110.389 100 |
| − | colMeansLoop(x) | + | #> colMeansApply(x) 103.357 138.125 145.323 148.876 180.600 100 |
| − | colMeansApply(x) | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
Все результаты представлены в виде описательных статистик, рассчитанных из времени выполнения каждой попытки. Наиболее информативный столбец - это столбец median, который показывает медиану времени выполнения выражения для всех попыток. | Все результаты представлены в виде описательных статистик, рассчитанных из времени выполнения каждой попытки. Наиболее информативный столбец - это столбец median, который показывает медиану времени выполнения выражения для всех попыток. | ||
| Строка 211: | Строка 189: | ||
Вся полученная информация о попытках применения функций вычисления средних записана в отдельную переменную <code>res</code>. С помощью функции <code>str()</code> можно увидеть структуру переменной: | Вся полученная информация о попытках применения функций вычисления средних записана в отдельную переменную <code>res</code>. С помощью функции <code>str()</code> можно увидеть структуру переменной: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>str(res) |
| − | > str(res) | + | #> Classes 'microbenchmark' and 'data.frame': 500 obs. of 2 variables: |
| − | Classes | + | #> $ expr: Factor w/ 5 levels "colMeansApply(x)",..: 3 2 4 2 2 2 3 5 4 1 ... |
| − | $ expr: Factor w/ 5 levels "colMeansApply(x)",..: 4 2 | + | #> $ time: num 86781202 81161181 65429189 74434388 74424478 ... |
| − | $ time: num | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
Переменная <code>res</code>, как можно увидеть в выводе функции <code>str()</code>, представляет собой список (list) и включает в себя две переменные: <code>expr</code> (выражение) и <code>time</code> (время выполнения). На основе этой информации и рассчитываются описательные статистики, приведённые в примере применения функции <code>microbenchmark()</code>. Наличие исходных данных о каждой попытке позволяет самостоятельно выбирать, рассчитывать и сравнивать предпочтитаемые показатели. Например, расчет медианного времени выполнения попытки и общего времени выполнения всех попыток для каждого выражения выглядит следующим образом: | Переменная <code>res</code>, как можно увидеть в выводе функции <code>str()</code>, представляет собой список (list) и включает в себя две переменные: <code>expr</code> (выражение) и <code>time</code> (время выполнения). На основе этой информации и рассчитываются описательные статистики, приведённые в примере применения функции <code>microbenchmark()</code>. Наличие исходных данных о каждой попытке позволяет самостоятельно выбирать, рассчитывать и сравнивать предпочтитаемые показатели. Например, расчет медианного времени выполнения попытки и общего времени выполнения всех попыток для каждого выражения выглядит следующим образом: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>aggregate(time ~ expr, data = res, function(x) median(x) * 10^-6L) |
| − | > aggregate(time ~ expr, data = res, function(x) median(x) * 10^-6L) | + | #> expr time |
| − | expr | + | #> 1 colMeansApply(x) 145.323 |
| − | 1 colMeansApply(x) | + | #> 2 colMeansVapply(x) 83.481 |
| − | 2 colMeansVapply(x) | + | #> 3 colMeansLoop(x) 85.780 |
| − | 3 colMeansLoop(x) 85. | + | #> 4 colMeansLoopVec(x) 77.083 |
| − | 4 colMeansLoopVec(x) | + | #> 5 colMeans(x) 7.841 |
| − | 5 colMeans(x) 7. | + | aggregate(time ~ expr, data = res, function(x) sum(x) * 10^-6L) |
| − | + | #> expr time | |
| − | expr time | + | #> 1 colMeansApply(x) 14224.3 |
| − | 1 colMeansApply(x) | + | #> 2 colMeansVapply(x) 8193.4 |
| − | 2 colMeansVapply(x) | + | #> 3 colMeansLoop(x) 8309.6 |
| − | 3 colMeansLoop(x) | + | #> 4 colMeansLoopVec(x) 7483.0 |
| − | 4 colMeansLoopVec(x) | + | #> 5 colMeans(x) 785.7 |
| − | 5 colMeans(x) | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
Умножение на <math>10^{-6}</math> --- это перевод в миллисекунды. Чтобы получить секунды, нужно, соответственно, умножить на <math>10^{-9}</math>. | Умножение на <math>10^{-6}</math> --- это перевод в миллисекунды. Чтобы получить секунды, нужно, соответственно, умножить на <math>10^{-9}</math>. | ||
| − | Помимо настройки формата вывода, выбора показателей, наличие информации о времени выполнения выражения в каждой попытке позволяет визуализировать результаты оценки времени выполнения выражения. Например, с помощью функции <code>autoplot()</code> из пакета | + | Помимо настройки формата вывода, выбора показателей, наличие информации о времени выполнения выражения в каждой попытке позволяет визуализировать результаты оценки времени выполнения выражения. Например, с помощью функции <code>autoplot()</code> из пакета {{r-package|ggplot2}}, можно получить следующий график: |
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>autoplot(res) |
| − | + | </nowiki>}} | |
| − | > autoplot(res) | + | |
| − | </nowiki> | + | |
| − | }} | + | |
| − | [[Файл:Microbenchmark-autoplot-colMeans. | + | [[Файл:Microbenchmark-autoplot-colMeans.svg|600px|центр]] |
Ещё один довольно интересный способ графического представления результатов измерения скорости выполнения кода с помощью функции <code>qplot()</code> представлен ниже: | Ещё один довольно интересный способ графического представления результатов измерения скорости выполнения кода с помощью функции <code>qplot()</code> представлен ниже: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>qplot(y = time, data = res, colour = expr) |
| − | > qplot(y = time, data = res, colour = expr) | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
| − | [[Файл:Microbenchmark-dotplot-colMeans. | + | [[Файл:Microbenchmark-dotplot-colMeans.svg|600px|центр]] |
Так же можно, если возникнет необходимость, оценить статистическую значимость различий во времени выполнения выражений. Благодаря тому, что в переменной <code>res</code> хранятся данные о времени выполнения каждой попытки из заданного числа, становится возможным использование статистических критериев. Выбор критерия - на усмотрение аналитика, в примере ниже использовался параметрический критерий сравнения групп t-Стьюдента с поправкой уровня статистической значимости Холма для множественных сравнений: | Так же можно, если возникнет необходимость, оценить статистическую значимость различий во времени выполнения выражений. Благодаря тому, что в переменной <code>res</code> хранятся данные о времени выполнения каждой попытки из заданного числа, становится возможным использование статистических критериев. Выбор критерия - на усмотрение аналитика, в примере ниже использовался параметрический критерий сравнения групп t-Стьюдента с поправкой уровня статистической значимости Холма для множественных сравнений: | ||
| − | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>pairwise.t.test(res$time, res$expr) |
| − | > pairwise.t.test(res$time, res$expr) | + | #> |
| − | + | #> Pairwise comparisons using t tests with pooled SD | |
| − | Pairwise comparisons using t tests with pooled SD | + | #> |
| − | + | #> data: res$time and res$expr | |
| − | data: res$time and res$expr | + | #> |
| − | + | #> colMeansApply(x) colMeansVapply(x) colMeansLoop(x) colMeansLoopVec(x) | |
| − | colMeansApply(x) colMeansVapply(x) colMeansLoop(x) colMeansLoopVec(x) | + | #> colMeansVapply(x) < 2e-16 - - - |
| − | colMeansVapply(x) <2e-16 | + | #> colMeansLoop(x) < 2e-16 0.31 - - |
| − | colMeansLoop(x) <2e-16 | + | #> colMeansLoopVec(x) < 2e-16 2.6e-09 6.9e-12 - |
| − | colMeansLoopVec(x) <2e-16 | + | #> colMeans(x) < 2e-16 < 2e-16 < 2e-16 < 2e-16 |
| − | colMeans(x) <2e-16 | + | #> |
| − | + | #> P value adjustment method: holm | |
| − | P value adjustment method: holm | + | </nowiki>}} |
| − | </nowiki> | + | |
| − | }} | + | |
Из вышеприведённого вывода видно, что скорость выполнения всех функций статистически значимо разлиается у всех функций, за исключением пары <code>colMeansLoop(x)</code> - <code>colMeansVapply(x)</code> (p-уровень = 0.62). | Из вышеприведённого вывода видно, что скорость выполнения всех функций статистически значимо разлиается у всех функций, за исключением пары <code>colMeansLoop(x)</code> - <code>colMeansVapply(x)</code> (p-уровень = 0.62). | ||
Текущая версия на 17:45, 28 мая 2014
 
|
Материал «R:Измерение времени выполнения выражений», созданный автором Артём Клевцов, публикуется на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная. | |
|
 |
Перед использованием функций из пакетов их необходимо предварительно установить и загрузить: КодR <syntaxhighlight lang="r">> install.packages(pkgs = "pkgname") > library(package = "pkgname")</syntaxhighlight> |
Для измерения времени выполнения выражений используют следующие инструменты:
- Функция
system.time()из базового пакета; - Cпециализированные функции (benchmarks, бенчмарки);
- Функция профилирования времени выполнения кода
Rprof().
Функция system.time
Самый простой инструмент для измерения времени выполнения кода - функция system.time() из пакета base. В качестве аргумента функция system.time() принимает выражения и возвращает время выполнения данного выражения. Измерим время выполнения функции Sys.sleep(), которая останавливает выполнение кода на заданный интервал времени (в секундах):
<syntaxhighlight lang="r">system.time(Sys.sleep(1)) #> user system elapsed #> 0.000 0.000 1.001 </syntaxhighlight>
Как видим, на выполнение данной операции заняло ровно одну секунду.
Приведём ещё один пример. Сравним время вычисления встроенной в R функции mean() и среднего, вычисленного по формуле [math]\frac{1}{n}\sum_{i=1}^{n}x_{i}[/math]. на сгенерированном массиве нормально распределенных значений:
<syntaxhighlight lang="r">x <- rnorm(10^7L) system.time(mean(x)) #> user system elapsed #> 0.013 0.003 0.016 system.time(sum(x) / length(x)) #> user system elapsed #> 0.010 0.000 0.008 </syntaxhighlight>
Функция возвращает 3 значения:
-
user- время CPU, которое занял пользователь; -
system- время CPU, которое заняла система; -
elapsed- реальное время, которое заняло выполнение команды.
Соответственно, в выводе функции нас интересует значение elapsed, который показывает время выполнения функции (выражения) в секундах. Как мы видим, внешне более сложное выражение sum(x) / length(x) выполняется быстрее стандартной функции mean(x).
К сожалению, подобный способ достаточно ненадежен, так как для оценки времени выполнения выражения функция system.time() обращается к системным значениям времени. Следовательно, если во время выполнения кода параллельно производятся и другие операции на компьютере (а такое случается практически в ста процентах случаев), то возможно увеличение времени выполнения R-кода. Некоторую вариативность результатов можно увидеть, даже если выполнить функцию system.time() несколько раз подряд. Подобной неточности оценки можно избежать путём многократного повторения выполняемых выражений и вычислением среднего времени, что позволит сгладить часть вариаций.
Проиллюстрируем вышесказанное на примере:
<syntaxhighlight lang="r">replicate(10, system.time(mean(x))[["elapsed"]]) #> [1] 0.016 0.016 0.016 0.016 0.016 0.017 0.016 0.017 0.017 0.017 </syntaxhighlight>
В этом примере с помощью функции replicate() мы повторили выражение system.time(mean(x)) 10 раз, отфильтровав вывод функции system.time() так, чтобы нам выводилось только время выполнения команды, дописав "elapsed". Как мы видим, время выполнения при повторном выполнении выражения может отличаться.
Базовый пакет позволяет реализовать процедуру многократного повторения выражения функции как минимум двумя способами. Первый - функция replicate(). Приведенное выше сопоставление времени выполнения двух выражений при использовании функции replicate() будет выглядеть следующим образом:
<syntaxhighlight lang="r">system.time(replicate(100, mean(x))) #> user system elapsed #> 1.586 0.027 1.621 system.time(replicate(100, sum(x) / length(x))) #> user system elapsed #> 0.806 0.020 0.832 </syntaxhighlight>
Тот же самый эффект можно получить и с помощью обычного цикла for():
<syntaxhighlight lang="r">system.time(for (i in seq_len(100)) mean(x)) #> user system elapsed #> 1.563 0.050 1.620 system.time(for (i in seq_len(100)) sum(x) / length(x)) #> user system elapsed #> 0.806 0.020 0.830 </syntaxhighlight>
Можно также использовать описательные статистики в сочетании с множественными повторениями:
<syntaxhighlight lang="r">median(replicate(100, system.time(mean(x))[["elapsed"]])) #> [1] 0.016 </syntaxhighlight>
В примере выше мы взяли только значения elapsed и рассчитали медиану [1].
Вместо подобных решений можно использовать специальные пакеты, предназначенные для измерения производительности кода, в частности, пакеты rbenchmark и microbenchmark. Основной принцип работы этих пакетов заключается в многократном выполнении выражений и расчёта ряда интегральных показателей, в частности, суммы, среднего значения или медианы времени выполнения всех попыток.
Пакет rbenchmark
Основа пакета rbenchmark - функция benchmark(). Данная функция работает следующим образом: указанные в качестве аргументов выражения выполняются заданное количество раз (по умолчанию 100) и вычисляется время, затраченное на выполнение всех попыток. В качестве аргументов функции benchmark() необходимо передать выражения или функции, а также количество повторений, передаваемых аргументом replications[2].
Для примера возьмём несколько способов расчёта среднего арифметического для сгенерированного массива данных.
<syntaxhighlight lang="r">x <- replicate(10, rnorm(10^6L)) </syntaxhighlight>
Использованные нами способы - функции векторизованных вычислений (apply(), vapply()), стандартный цикл и специальная функция вычисления средних по столбцам ColMeans(). Представим эти способы в виде самостоятельных функций для удобства их вызова при работе с benchmark():
<syntaxhighlight lang="r">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>
Убедимся, что функции возвращают одинаковый результат. Сделать это можно с помощью функций identical() или all.equal():
<syntaxhighlight lang="r">identical(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x)) #> [1] TRUE </syntaxhighlight>
Теперь, подключив пакет rbenchmark, мы можем сравнить время работы каждого из выбранных нами способов вычисления средних по столбцам:
<syntaxhighlight lang="r">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 14.974 18.328 13.380 1.540 0 0 #> 4 colMeansLoopVec(x) 100 7.088 8.676 6.793 0.270 0 0 #> 3 colMeansLoop(x) 100 8.004 9.797 7.630 0.340 0 0 #> 2 colMeansVapply(x) 100 7.851 9.610 7.407 0.417 0 0 #> 5 colMeans(x) 100 0.817 1.000 0.787 0.026 0 0 </syntaxhighlight>
Наиболее важны для нас в выводе функции benchmark() столбцы elapsed и relative. Столбец elapsed показывает время в секундах, затраченное на выполнение интересующей нас функции. Как видим из примера, самыми медленными оказались функции colMeansApply() и colMeansLoop(), а самой быстрой colMeans(), причём превосходит остальные по скорости выполнения как минимум в 7 раз.
Показатель relative дает информацию о разнице во времени относительно самого быстрого выражения (в нашем случае это ColMeans()), т.е. время самого быстрого выражения берётся за единицу, и рассчитывается относительное время для остальных выражений.
Для более удобного просмотра можно отфильтровать вывод функции benchmark() с помощью аргумента columns. Также может быть полезен аргумент order, позволяющий отсортировать вывод по любому из столбцов. Для примера зададим набор показателей, которые мы хотим включить в таблицу (в данном случае это «test», «replications», «elapsed», «relative»), и отсортируем выдачу по столбцу «elapsed» по возрастанию значений:
<syntaxhighlight lang="r">benchmark(colMeansApply(x), colMeansVapply(x), colMeansLoop(x), colMeansLoopVec(x), colMeans(x), replications = 100, order = "relative", columns = c("test", "replications", "elapsed", "relative")) #> test replications elapsed relative #> 5 colMeans(x) 100 0.797 1.000 #> 4 colMeansLoopVec(x) 100 6.856 8.602 #> 3 colMeansLoop(x) 100 7.633 9.577 #> 2 colMeansVapply(x) 100 7.722 9.689 #> 1 colMeansApply(x) 100 15.167 19.030 </syntaxhighlight>
Таким образом, сравнив несколько альтернатив решения нашей задачи, мы можем сделать обоснованный выбор в пользу наиболее эффективного варианта.
Чтобы не указывать нужные столбцы каждый раз, когда используется функция benchmark(), можно закрепить заданный формат выдачи результатов (далее используется именно такой формат вывода, с сортировкой по столбцу «relative»). Для этого следует воспользоваться функцией formals():
<syntaxhighlight lang="r">formals(benchmark)$columns <- c("test", "replications", "elapsed", "relative") formals(benchmark)$order <- "relative" </syntaxhighlight>
Пакет microbenchmark
Функция microbenchmark() одноименного пакета работает сходным с функцией benchmark() образом, но предоставляет более гибкие средства по управлению процессом выполнения выражений[3]. Особенностями реализованных в пакете microbenchmark являются:
- Возможность измерения времени выполнения выражения вплоть до наносекунд;
- Возможность контролировать последовательность выполнения выражений: случайно или последовательно;
- Возможность проведения предварительных испытаний до начала процесса измерений.
Также с помощью функции microbenchmark() можно получить исходную информацию о времени выполнения каждой попытки, что даёт достаточно широкие возможности по обработке и анализу полученных результатов.
В таблице ниже представлено время выполнения пяти функций вычисления среднего значения из предыдущего примера, полученное с помощью функции microbenchmark():
<syntaxhighlight lang="r">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.805 7.824 7.841 7.865 8.295 100 #> colMeansLoopVec(x) 65.429 67.680 77.083 79.558 95.667 100 #> colMeansVapply(x) 73.158 74.701 83.481 87.724 102.963 100 #> colMeansLoop(x) 73.163 75.355 85.780 87.986 110.389 100 #> colMeansApply(x) 103.357 138.125 145.323 148.876 180.600 100 </syntaxhighlight>
Все результаты представлены в виде описательных статистик, рассчитанных из времени выполнения каждой попытки. Наиболее информативный столбец - это столбец median, который показывает медиану времени выполнения выражения для всех попыток.
Вся полученная информация о попытках применения функций вычисления средних записана в отдельную переменную res. С помощью функции str() можно увидеть структуру переменной:
<syntaxhighlight lang="r">str(res) #> Classes 'microbenchmark' and 'data.frame': 500 obs. of 2 variables: #> $ expr: Factor w/ 5 levels "colMeansApply(x)",..: 3 2 4 2 2 2 3 5 4 1 ... #> $ time: num 86781202 81161181 65429189 74434388 74424478 ... </syntaxhighlight>
Переменная res, как можно увидеть в выводе функции str(), представляет собой список (list) и включает в себя две переменные: expr (выражение) и time (время выполнения). На основе этой информации и рассчитываются описательные статистики, приведённые в примере применения функции microbenchmark(). Наличие исходных данных о каждой попытке позволяет самостоятельно выбирать, рассчитывать и сравнивать предпочтитаемые показатели. Например, расчет медианного времени выполнения попытки и общего времени выполнения всех попыток для каждого выражения выглядит следующим образом:
<syntaxhighlight lang="r">aggregate(time ~ expr, data = res, function(x) median(x) * 10^-6L) #> expr time #> 1 colMeansApply(x) 145.323 #> 2 colMeansVapply(x) 83.481 #> 3 colMeansLoop(x) 85.780 #> 4 colMeansLoopVec(x) 77.083 #> 5 colMeans(x) 7.841 aggregate(time ~ expr, data = res, function(x) sum(x) * 10^-6L) #> expr time #> 1 colMeansApply(x) 14224.3 #> 2 colMeansVapply(x) 8193.4 #> 3 colMeansLoop(x) 8309.6 #> 4 colMeansLoopVec(x) 7483.0 #> 5 colMeans(x) 785.7 </syntaxhighlight>
Умножение на [math]10^{-6}[/math] --- это перевод в миллисекунды. Чтобы получить секунды, нужно, соответственно, умножить на [math]10^{-9}[/math].
Помимо настройки формата вывода, выбора показателей, наличие информации о времени выполнения выражения в каждой попытке позволяет визуализировать результаты оценки времени выполнения выражения. Например, с помощью функции autoplot() из пакета ggplot2, можно получить следующий график:
<syntaxhighlight lang="r">autoplot(res) </syntaxhighlight>
Ещё один довольно интересный способ графического представления результатов измерения скорости выполнения кода с помощью функции qplot() представлен ниже:
<syntaxhighlight lang="r">qplot(y = time, data = res, colour = expr) </syntaxhighlight>
Так же можно, если возникнет необходимость, оценить статистическую значимость различий во времени выполнения выражений. Благодаря тому, что в переменной res хранятся данные о времени выполнения каждой попытки из заданного числа, становится возможным использование статистических критериев. Выбор критерия - на усмотрение аналитика, в примере ниже использовался параметрический критерий сравнения групп t-Стьюдента с поправкой уровня статистической значимости Холма для множественных сравнений:
<syntaxhighlight lang="r">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.31 - - #> colMeansLoopVec(x) < 2e-16 2.6e-09 6.9e-12 - #> colMeans(x) < 2e-16 < 2e-16 < 2e-16 < 2e-16 #> #> P value adjustment method: holm </syntaxhighlight>
Из вышеприведённого вывода видно, что скорость выполнения всех функций статистически значимо разлиается у всех функций, за исключением пары colMeansLoop(x) - colMeansVapply(x) (p-уровень = 0.62).
Примечания
- ↑ Медиана является более устойчивой мерой центральной тенденции при асимметрии распределения, что, как правило, характерно для измерения времени.
- ↑ Анализ функции
benchmark()показал, что, данная функция используетsystem.time()иreplicate(), рассмотренные в предыдущем разделе. - ↑ Но в отличии от функции benchmark() использует собственную реализацию измерения времени выполнения и организацию повторных испытаний.
Ссылки
- Olaf Mersmann (2013). microbenchmark: Sub microsecond accurate timing functions.. R package version 1.3-0.
- Wacek Kusnierczyk (2012). rbenchmark: Benchmarking routine for R. R package version 1.0.0.
