Можно выделить ряд алгоритмов, которые являются базовыми и лежат в основе практически каждой строчки программ, написанных на языках высокого уровня. Хорошо иметь под руками классический многотомный труд Дональда Кнута "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.
