Se pueden distinguir varios algoritmos que son básicos y subyacen en casi todas las lĂneas de programas escritos en lenguajes de alto nivel. Es bueno tener a mano la clásica obra multivolumen de Donald Knuth "El arte de la programaciĂłn informática" , donde se analizan en detalle muchos algoritmos básicos. Pero leer y asimilar todo es una tarea que requiere mucho esfuerzo y tiempo, que de alguna manera debe estar motivado.
Muchos pueden suponer que era necesario conocer los matices hace 50 años, pero ahora puede usar paquetes y funciones listos para usar y no sumergirse en detalles. Sin embargo, éste no es el caso. Asimismo, nadie ha cancelado la importancia de comprender la representación de los métodos para almacenar datos en la memoria y procesarlos en el procesador.
. . .
, . , , .
, , :
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».