Русский
Русский
English
Статистика
Реклама

Запросить 100 серверов нельзя оптимизировать код. Ставим запятую

Можно выделить ряд алгоритмов, которые являются базовыми и лежат в основе практически каждой строчки программ, написанных на языках высокого уровня. Хорошо иметь под руками классический многотомный труд Дональда Кнута "The Art of Computer Programming", там детально разобраны многие базовые алгоритмы. Но прочесть и усвоить все задача, требующая много усилий и времени, которая должна как-то быть мотивирована.


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


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


Является продолжением серии предыдущих публикаций.


Введение


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


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


  • case_id уникальный идентификатор кейса/прецедента;
  • record журнальная запись события в кейсе;
  • start время регистрации.

Используемые библиотеки


library(tidyverse)library(data.table)library(rTRNG)

Наиболее интересной задачей является генерация временных меток. События должны идти последовательно во времени для каждого кейса в отдельности. Сначала подготовим простую "рыбу". В частном случае мы возьмем для демонстрации малое число кейсов. В продуктиве их может быть 10^5-10^n, что определяется задачами.


Пример кода
# определим число кейсовnn <- 100# создаем первичный набор кейсовrecords <- c("first", "one and a half", "second", "third", "fourth",              "fifth", "sixth")# готовим два варианта для экспериментовdf <- tibble(case_id = 1:nn, recs = list(records)) %>%  unnest(recs)dt <- as.data.table(df)[, case_id := as.numeric(case_id)]# указание ключа приводит к физической сортировке данныхsetkey(dt, case_id)head(df, 10)

  # A tibble: 10 x 2     case_id recs                 <int> <chr>            1       1 first            2       1 one and a half   3       1 second           4       1 third            5       1 fourth           6       1 fifth            7       1 sixth            8       2 first            9       2 one and a half  10       2 second  

Теперь приступим к интересному блоку генерации временных меток. Для простоты задачи сведем ее к распределению долей в интервале [0; 1] в рамках каждого кейса. Перевод в реальный unixtimestamp оставим за пределами, это неинтересно. Варианты с явными циклами также за пределами. Времена исполнения приведены на условном компьютере, главное, что выполняется все на одном.


Создание одной временнОй метки


Вариант 1. Прямолинейный


Этот вариант предлагается в большинстве случаев. А что, все просто и понятно.


Пример кода
f1 <- function(df) {  df %>%    group_by(case_id) %>%    mutate(t_idx = sort(runif(n(), 0, 1))) %>%    ungroup()}

Получаем такие условные показатели. Наверное, неплохо. Но не забываем, что тут всего 100 кейсов.


  median `itr/sec` mem_alloc 15.38ms      63.2   284.9KB

Подумаем, что можно улучшить?


Вариант 1+1/2. Прямолинейный + быстрый генератор чисел


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


Пример кода
f1_5 <- function(df) {  df %>%    group_by(case_id) %>%    mutate(t_idx = sort(runif_trng(n(), 0, 1))) %>%    ungroup()}

  median `itr/sec` mem_alloc 29.34ms      29.5   284.9KB

На малых объемах не получили никакого выигрыша. Это все? Конечно же нет. Мы знаем, что tidyverse медленнее data.table, попробуем применить его. Но здесь мы попробуем применить первую хитрость отсортировать вектор времен по индексам, а потом его переприсвоить.


Вариант 2. Однопроходный, через индексы data.table


Пример кода
f2 <- function(dt) {  # здесь полагаемся на то, что мы заранее отсортировали уже по `case_id``  # формируем случайные числа и сортируем их по кейсам  vec <- dt[, t_idx := runif_trng(.N, 0, 1)][order(case_id, t_idx), t_idx]  # возвращаем сортированный   dt[, t_idx := vec]}

Получается вполне неплохо, ускорение раз в 15-20 и памяти требуется почти в три раза меньше.


  median `itr/sec` mem_alloc   1.69ms     554.      109KB 

Останавливаемся? А почему да?


Вариант 3. Однопроходный, через композитный индекс


На самом деле, как только мы сваливаемся в цикл, явный, или через by, мы резко просаживаемся в производительности. Попробуем сделать все за один проход. Идея следующая сделать композитный индекс, который позволил бы нам отсортировать все события одним махом. Используем трюк. Поскольку у нас внутри кейса все временные метки будут в диапазоне [0; 1], то мы можем разделить индекс на две части. Целочисленная часть будет содержать case_id, дробная часть временнУю долю. Однократная сортировка одного такого индекса сохранит принадлежность строчек case_id, при этом мы одним махом отсортируем значения внутри каждого кейса


Пример кода
f3 <- function(dt) {  # делаем трюк, формируем композитный индекс из case_id, который является монотонным, и смещением по времени  # поскольку случайные числа генерятся в диапазоне [0, 1], мы их утаскиваем в дробную часть (за запятую)  # сначала просто генерируем случайные числа от 0 до 1 для каждой записи отдельно   # и масштабируем одним вектором  dt[, t_idx := sort(case_id + runif_trng(.N, 0, 1, parallelGrain = 10000L)) - case_id]}

Запускаем и получаем выигрыш еще в 2 раза против предыдущего варианта, как по времени, так и по памяти.


  median `itr/sec` mem_alloc 826.7us    1013.     54.3KB

Вариант 3+1/2. Однопроходный, через композитный индекс, используем set


Останавливаемся? Можно и остановиться, хотя поле для сжатия еще есть. Дело в том, что при таких малых временах исполнения накладные расходы на NSE становятся весьма ощутимыми. Если использовать прямые функции, то можно получить куда лучший результат.


Пример кода
f3_5 <- function(dt) {  set(dt, j = "t_idx",       value = sort(dt$case_id + runif(nrow(dt), 0, 1)) - dt$case_id)}

Ускорение еще в 5 раз, памяти потребляем в 4 раза меньше


  median `itr/sec` mem_alloc 161.5us    5519.     16.3KB

Промежуточное подведение итогов


Соберем все вместе.


Тестируем
bench::mark(  f1(df),  f1_5(df),  f2(dt),  f3(dt),  f3_5(dt),  check = FALSE)

  expression      min   median `itr/sec` mem_alloc  <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>1 f1(df)       14.3ms  15.38ms      63.2   284.9KB2 f1_5(df)    24.43ms  29.34ms      29.5   284.9KB3 f2(dt)       1.55ms   1.69ms     554.      109KB4 f3(dt)        722us  826.7us    1013.     54.3KB5 f3_5(dt)    142.5us  161.5us    5519.     16.3KB

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


Создание временнОй метки начала записи и окончания


Усложним немного задачу. Теперь для каждой записи надо сформировать время начала и время окончания ("прием у врача"). При этом все записи должны соблюдать исходный порядок следования во времени и время окончания для каждой записи должно быть не раньше времени начала.


Количество рассматриваемых сценариев сократим, оставим только наиболее интересные. И всякие варианты с явными циклами тоже даже не упоминаем.


Вариант 1. Прямолинейный


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


Пример кода
# Cоздание ЧЕТРЕХ колонок -- case_id, record, start, finish# Все как в предыдущем, только для каждого записи finish > start # и для двух последовательных записей 1, 2 в одном кейсе start_2 > finish_1 dt[, t_idx := NULL] # очистим хвосты предыдущего упражненияf1 <- function(df) {  df %>%    group_by(case_id) %>%    mutate(ts_idx = sort(runif(n(), 0, 1))) %>%    ungroup() %>%    # еще раз пройдемся генератором, используя время начала следующей записи как границу    # чтобы избежать NaN при переходе между кейсами (в случае max < min),     # принудительно выставим порог 1 в таких переходах, NA в последней строке тоже заменим на 1    mutate(tf_idx = {lead(ts_idx, default = 1) %>% if_else(. > ts_idx, ., 1)}) %>%    mutate(tf_idx = map2_dbl(ts_idx, tf_idx, ~runif(1, .x, .y)))}

В целом меньше секунды, но, очевидно, что это ОЧЕНЬ далеко от оптимальности.


  median `itr/sec` mem_alloc  28.16ms      30.7    2.06MB 

Вариант 2. Однопроходный, через композитный индекс и матрицы


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


Пример кода
f2 <- function(dt){  dt[, c("ts_idx", "tf_idx") := {    # используем принцип vector recycling    x <- case_id + runif(2 * .N, 0, 1);    m <- matrix(sort(x), ncol = 2, byrow = TRUE) - case_id;    list(m[, 1], m[, 2])  }]}

В легкую сократили время и память почти в 30 раз! Да и код стал существенно проще и прямолинейнее.


  median `itr/sec` mem_alloc   1.04ms     733.    74.38KB 

Вариант 2+1/2. Однопроходный, через композитный индекс, матрицы и set


Пример кода
f2_5 <- function(dt){  x <- dt$case_id + runif(2 * nrow(dt), 0, 1)  m <- matrix(sort(x), ncol = 2, byrow = TRUE) - dt$case_id  set(dt, j = "ts_idx", value = m[, 1])  set(dt, j = "tf_idx", value = m[, 2])}

Перфекционизм в действии. Еще в 4 раза ускорили.


  median `itr/sec` mem_alloc  278.1us    2781.    57.55KB 

Промежуточное подведение итогов


Соберем все вместе.


Тестируем
bench::mark(  f1(df),  f2(dt),  f2_5(dt),  check = FALSE)

  median `itr/sec` mem_alloc  28.16ms      30.7    2.06MB   1.04ms     733.    74.38KB  278.1us    2781.    57.55KB 

Первичный наивный вариант также удалось бесплатно улучшить по производительности в 90 раз, а потребление памяти сократить в 35 раз.


Заключение


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


Поэтому, когда представители BigData запрашивают немалые вычислительные ресурсы и требуемое время для относительно небольшой задачи, всегда терзает смутное сомнение, что под капотом что-то не то.


Предыдущая публикация Оценка структуры кредитного портфеля с помощью R.

Источник: habr.com
К списку статей
Опубликовано: 15.06.2021 20:16:32
0

Сейчас читают

Комментариев (0)
Имя
Электронная почта

Python

Алгоритмы

Big data

R

Data engineering

Data science

Категории

Последние комментарии

© 2006-2021, personeltest.ru