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