R:Измерение времени выполнения выражений — различия между версиями
м (→Функция system.time) |
м (Загрузка 2693-time-measure.wiki) |
||
(не показано 6 промежуточных версий этого же участника) | |||
Строка 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)) |
− | + | #> user system elapsed | |
− | + | #> 0.000 0.000 1.001 | |
− | </nowiki> | + | </nowiki>}} |
− | }} | + | |
Как видим, на выполнение данной операции заняло ровно одну секунду. | Как видим, на выполнение данной операции заняло ровно одну секунду. | ||
Строка 22: | Строка 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) |
− | + | 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 значения: | ||
Строка 43: | Строка 45: | ||
Проиллюстрируем вышесказанное на примере: | Проиллюстрируем вышесказанное на примере: | ||
− | {{r-code|code=<nowiki | + | {{r-code|code=<nowiki>replicate(10, system.time(mean(x))[["elapsed"]]) |
− | [1] 0. | + | #> [1] 0.016 0.016 0.016 0.016 0.016 0.017 0.016 0.017 0.017 0.017 |
− | </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>. Как мы видим, время выполнения при повторном выполнении выражения может отличаться. | ||
Строка 52: | Строка 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))) |
− | + | #> 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)) |
− | + | #> 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"]])) |
− | [1] 0. | + | #> [1] 0.016 |
− | </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) | ||
} | } | ||
Строка 121: | Строка 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 раз. | ||
Строка 153: | Строка 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>}} |
− | }} | + | |
Таким образом, сравнив несколько альтернатив решения нашей задачи, мы можем сделать обоснованный выбор в пользу наиболее эффективного варианта. | Таким образом, сравнив несколько альтернатив решения нашей задачи, мы можем сделать обоснованный выбор в пользу наиболее эффективного варианта. | ||
Строка 169: | Строка 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}} являются: |
* Возможность измерения времени выполнения выражения вплоть до наносекунд; | * Возможность измерения времени выполнения выражения вплоть до наносекунд; | ||
Строка 187: | Строка 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, который показывает медиану времени выполнения выражения для всех попыток. | ||
Строка 205: | Строка 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.