Как стать автором
Обновить
2340.96
Рейтинг
RUVDS.com
VDS/VPS-хостинг. Скидка 10% по коду HABR10

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

Блог компании RUVDS.comPythonАлгоритмыBig DataR

Можно выделить ряд алгоритмов, которые являются базовыми и лежат в основе практически каждой строчки программ, написанных на языках высокого уровня. Хорошо иметь под руками классический многотомный труд Дональда Кнута "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.9KB
2 f1_5(df)    24.43ms  29.34ms      29.5   284.9KB
3 f2(dt)       1.55ms   1.69ms     554.      109KB
4 f3(dt)        722us  826.7us    1013.     54.3KB
5 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 запрашивают немалые вычислительные ресурсы и требуемое время для относительно небольшой задачи, всегда терзает смутное сомнение, что под капотом что-то не то.


P.S.
Как обычно, пожелание к читателям. Если есть возражения и вопросы и хотите поставить - — пишите комментарий. Продуктивная дискуссия интересна.
Снобы молчуны-минусовщики скушны до оскомины.


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


ruvds


ruvds

Теги:data sciencebigdataruvds_статьиpythonrалгоритмы
Хабы: Блог компании RUVDS.com Python Алгоритмы Big Data R
Всего голосов 52: ↑51 и ↓1+50
Просмотры4.9K

Похожие публикации

Лучшие публикации за сутки

Информация

Дата основания
Местоположение
Россия
Сайт
ruvds.com
Численность
11–30 человек
Дата регистрации
Представитель
ruvds

Блог на Хабре