Как rnorm и runif работают так быстро?

Вопрос или проблема

edm1_rnorm1 <- function(mean_inpt, 
                            sd_inpt, 
                            n_inpt,
                            offset_proba = 0.00001,
                            cur_step = "auto",
                            accuracy_factor = 10){
  offset_val <- abs(log(offset_proba * sd_inpt * (2 * pi) ** 0.5) * 2) ** 0.5 * sd_inpt 
  rtn_v <- rep(x = "NULL", times = n_inpt * accuracy_factor)
  if (cur_step == "auto"){
    cur_step <- (2 * offset_val) / n_inpt
  }
  cnt1 = 1
  for (i in seq(from = (-offset_val + cur_step), to = offset_val, by = cur_step)){
    cur_rep <- ((1 / (sd_inpt * ((2 * pi) ** 0.5))) * exp(-0.5 * ((i / sd_inpt) ** 2))) * n_inpt * accuracy_factor
    cur_value <- i + mean_inpt
    lst_idx <- round(x = cur_rep, digits = 0)
    rtn_v[cnt1:(cnt1 + lst_idx)] <- cur_value    
    cnt1 = cnt1 + lst_idx + 1 
  }
  rtn_v <- rtn_v[1:(cnt1 - lst_idx)]
  rtn_v <- rtn_v[round(x = runif(n = n_inpt, min = 1, max = length(rtn_v)), digits = 0)]
  return(rtn_v)
}

x <- edm1_rnorm1(mean_inpt = 100,
                      sd_inpt = 15,
                      n_inpt = 50000,
                      offset_proba = 0.00001,
                      cur_step = 0.05,
                      accuracy_factor = 10)

datf <- data.frame("x" = c(1:length(x)), 
                   "y" = sort(as.numeric(x)))

ggplot(data = datf, mapping = aes(x = x, y = y)) +
  geom_line() + 
  theme_minimal()

rtn_v[cnt1:(cnt1 + lst_idx)] <- cur_value

Ответ или решение

Почему функции rnorm и runif такие быстрые?

Функции rnorm и runif, доступные в базе R, используются для генерации случайных чисел из нормального и равномерного распределения соответственно. Одна из основных причин, по которой они работают так быстро, заключается в их реализации на языке C, что позволяет значительно снизить накладные расходы, связанные с интерпретацией кода, по сравнению с реализацией на чистом R.

Оптимизация производительности в rnorm и runif

1. Компиляция и эффективность C-кода: C является языком более низкого уровня по сравнению с R. Функции, написанные на C, компилируются, что делает их исполнение более эффективным и быстрым. В отличие от R, компилируемый код выполняется напрямую, что позволяет избежать дополнительных накладных расходов на интерпретацию каждого оператора.

2. Векторизация: В функции rnorm и runif используется векторизация, что позволяет выполнять операции над целыми массивами данных одновременно. V язык R ориентирован на работу с векторами, и векторные операции выполняются гораздо быстрее, чем последовательные итерации в циклах. Это основной принцип, который стоит за высокой производительностью встроенных функций.

3. Математические преобразования: Внутри функций rnorm и runif применяются предварительно оптимизированные алгоритмы генерации случайных чисел. Например, для нормального распределения часто используется метод Бокс-Мюллера или его модификации, которые обеспечивают быстрое генерирование значений с высокой скоростью и низкой вычислительной сложностью.

4. Использование низкоуровневых библиотек: rnorm и runif могут использовать низкоуровневые библиотеки, такие как BLAS или LAPACK, для выполнения операций, связанных с линейной алгеброй, что обеспечивает еще большую оптимизацию и скорость выполнения.

Ваш код: В чем проблемы?

Ваша реализация функции edm1_rnorm1, хотя и написана с вниманием к деталям, сталкивается с проблемой производительности, в первую очередь из-за цикла и частых операций присвоения значений в вектор:

rtn_v[cnt1:(cnt1 + lst_idx)] <- cur_value

Каждое присвоение в цикле вызывает перераспределение памяти для вектора rtn_v, что является дорогой операцией. Данный подход может значительно замедлить выполнение функции при больших объемах данных.

Рекомендации по оптимизации

1. Предварительное выделение памяти: Вместо динамического увеличения размера rtn_v, постарайтесь заранее выделить достаточный объем памяти для хранения результата, что минимизирует накладные расходы.

   rtn_v <- numeric(n_inpt * accuracy_factor)

2. Устранение циклов: Попробуйте избегать циклов, где это возможно. Вместо этого можно использовать векторизованные операции или функции, такие как sapply, которые автоматически оптимизируют обработку данных:

   cur_rep <- (1 / (sd_inpt * sqrt(2 * pi))) * exp(-0.5 * ((seq(-offset_val, offset_val, by = cur_step) / sd_inpt) ** 2))

3. Параллельные вычисления: Рассмотрите использование параллельных вычислений, чтобы строить массивы более эффективно, используя библиотеки, такие как parallel или foreach.

4. Анализ и оптимизация алгоритма: Проверьте выбор алгоритма генерации чисел. Если ваш метод не оптимален, рассмотрите возможность использования других подходов, основанных на аппаратных или статистических методах.

Заключение

Хотя R предоставляет мощные инструменты для работы с данными, применение низкоуровневых языков, таких как C, для реализации критически важных функций, таких как rnorm и runif, обеспечивает их высокую производительность. Оптимизация вашей реализации также потребует пересмотра подходов к распределению памяти и использования векторизации для достижения более эффективного кода.