r - tablas - tecnicas de hashing
Subconjunto de una tabla de datos por rango haciendo uso de búsqueda binaria (2)
¿Cómo se hace para subordinar una tabla de datos por un rango numérico, con la intención de usar la búsqueda binaria?
Por ejemplo:
require(data.table)
set.seed(1)
x<-runif(10000000,min=0,max=10)
y<-runif(10000000,min=0,max=10)
DF<-data.frame(x,y)
DT<-data.table(x,y)
system.time(DFsub<-DF[DF$x>5 & DF$y<7,])
# user system elapsed
# 1.529 0.250 1.821
#subset DT
system.time(DTsub<-DT[x>5 & y<7])
# user system elapsed
#0.716 0.119 0.841
Lo anterior no usa una tecla (escaneo vectorial), y la aceleración no es tan dramática. ¿Cuál es la sintaxis para subcontratar un rango numérico de una tabla de datos, haciendo uso de la búsqueda binaria? No puedo encontrar un buen ejemplo en la documentación; sería útil si alguien pudiera proporcionar un ejemplo utilizando la tabla de datos de juguetes anterior.
EDITAR: Esta pregunta es similar, pero aún no muestra cómo subconjuntar por un rango: data.table: vector scan v búsqueda binaria con columnas numéricas - tecla de configuración muy lenta
Interesante pregunta. Primero veamos los datos de ejemplo:
> print(DT)
x y
1: 2.607703e-07 5.748127
2: 8.894131e-07 5.233994
3: 1.098961e-06 9.834267
4: 1.548324e-06 2.016585
5: 1.569279e-06 7.957730
---
9999996: 9.999996e+00 9.977782
9999997: 9.999998e+00 2.666575
9999998: 9.999999e+00 6.869967
9999999: 9.999999e+00 1.953145
10000000: 1.000000e+01 4.001616
> length(DT$x)
[1] 10000000
> length(unique(DT$x))
[1] 9988478
> length(DT$y)
[1] 10000000
> length(unique(DT$y))
[1] 9988225
> DT[,.N,by=x][,table(N)]
N
1 2 3
9976965 11504 9
> DT[,.N,by="x,y"][,table(N)]
N
1
10000000
>
Así que hay casi 10 millones de valores de punto flotante únicos en la primera columna: algunos grupos de tamaño 2 y 3 filas, pero en su mayoría grupos de 1 fila. Una vez que se incluye la segunda columna, hay 10 millones de grupos únicos de tamaño 1 fila. Este es un problema bastante difícil, ya que data.table está diseñado más para datos agrupados en mente; por ejemplo, (id, fecha), (id1, id2, fecha, hora) etc.
Sin embargo, data.table y setkey admiten datos de punto flotante en las claves, así que vamos a setkey .
En mi netbook lento:
> system.time(setkey(DT,x,y))
user system elapsed
7.097 0.520 7.650
> system.time(DT[x>5 & y<7])
user system elapsed
2.820 0.292 3.122
Por lo tanto, el método de escaneo vectorial es más rápido que configurar la clave (y aún no hemos usado la clave). Dado que los datos son de punto flotante y casi únicos, esto no es demasiado sorprendente, pero creo que es un momento bastante rápido para que setkey 10 millones de dobles totalmente aleatorios y casi únicos.
Compara con la base, por ejemplo, simplemente clasificando x ni siquiera y también:
> system.time(base::order(x))
user system elapsed
72.445 0.292 73.072
Asumiendo que estos datos son representativos de sus datos reales, y no desea hacer esto solo una vez sino varias veces, por lo que están dispuestos a pagar el precio de setkey , el primer paso es bastante claro:
system.time(w <- DT[.(5),which=TRUE,roll=TRUE])
user system elapsed
0.004 0.000 0.003
> w
[1] 4999902
Pero aquí estamos atrapados. Un siguiente paso como DT[(w+1):nrow(DT)] es feo y se copia. No puedo pensar en una forma decente de usar la tecla desde aquí para hacer la parte y<7 también. En otros datos de ejemplo, hacemos algo como DT[.(unique(x), 7), which=TRUE, roll=TRUE] pero en este caso los datos son tan únicos y de punto flotante que van a ser lentos.
Idealmente, esta tarea necesita una combinación de rangos (FR # 203) para su implementación. La sintaxis en este ejemplo podría ser:
DT[.( c(5,Inf), c(-Inf,7) )]
o para hacerlo más fácil, DT[x>5 & y<7] podría optimizarse para hacerlo bajo el capó. Permitir un rango de dos columnas en i que se una a las columnas x correspondientes podría ser bastante útil y ha surgido varias veces.
Las aceleraciones en v1.9.2 debían hacerse primero antes de que pudiéramos pasar a cosas como esas. Si prueba setkey en estos datos en v1.8.10 encontrará que v1.9.2 es significativamente más rápido.
Ver también :
Cómo unirse automáticamente a una tabla de datos en una condición
Según lo solicitado por Matt Dowle, volví a ejecutar el código y los tiempos para incluir una comparación con la función between ahora incluida en el paquete data.table. Parece que el escaneo vectorial de una columna de punto flotante sigue siendo el enfoque más eficiente.
#OP''s example data
require(data.table)
set.seed(1)
x<-runif(10000000,min=0,max=10)
y<-runif(10000000,min=0,max=10)
DF<-data.frame(x,y)
DT<-data.table(x,y)
Subconjunto como un data.frame
system.time(DFsub<-DF[DF$x>5 & DF$y<7,])
# user system elapsed
# 0.506 0.062 0.576
Subconjunto como data.table con escaneo vectorial.
system.time(DTsub<-DT[x>5 & y<7])
# user system elapsed
# 0.213 0.024 0.238
Subconjunto de DT con entre (tanto para x como para y)
system.time(DTsub<-DT[between(x ,5, max(x)) & between(y, 0,7), ])
# user system elapsed
# 0.242 0.036 0.279
Alternativa de escaneo vectorial mixta y entre
system.time(DTsub<-DT[x > 5 & between(y, 0,7), ])
# user system elapsed
# 0.203 0.017 0.221
Alternativa entre sintaxis
system.time(DTsub<-DT[x %between% c(5, max(x)) & y %between% c(0, 7)])
# user system elapsed
# 0.227 0.016 0.244
Escaneo vectorial mixto y entre (con sintaxis alternativa)
system.time(DTsub<-DT[x>5 & y %between% c(0, 7)])
# user system elapsed
# 0.203 0.017 0.221
Evaluación un poco más completa
library(microbenchmark)
mbm<-microbenchmark(
"DFsub"={b1<-DF[DF$x>5 & DF$y<7,]},
"DTsub1"={b2<-DT[x>5 & y<7]},
"DTsub2"={b3<-DT[between(x ,5, max(x)) & between(y, 0, 7), ]},
"DTsub3"={b4<-DT[x > 5 & between(y, 0,7), ]},
"DTsub4"={b5<-DT[x %between% c(5, max(x)) & y %between% c(0, 7)]},
"DTsub5"={b5<-DT[x>5 & y %between% c(0, 7)]}
)
mbm
Unit: milliseconds
Unit: milliseconds
# expr min lq mean median uq max neval
# DFsub 527.6842 582.3235 635.8846 622.1641 664.3243 1101.2365 100
# DTsub1 220.5086 245.7509 279.5451 263.5527 296.5736 411.5833 100
# DTsub2 249.2093 283.2025 325.4845 304.2361 333.6894 660.5021 100
# DTsub3 215.5454 243.3255 281.3596 270.1108 300.8462 491.8837 100
# DTsub4 250.9431 282.1896 330.0688 305.2094 352.9604 736.2690 100
# DTsub5 218.5458 238.8931 276.7932 262.6675 293.3524 467.5082 100
library(ggplot2)
autoplot(mbm)
