data.table: Vektor-Scan v binäre Suche mit numerischen Spalten - super-langsame setkey

Question

Ich versuche, den schnellsten Weg zu finden, einen großen Datensatz durch mehrere numerische Spalten zu unterteilen. Wie von data.table versprochen, ist die für die binäre Suche benötigte Zeit viel schneller als beim Vektor-Scannen. Die binäre Suche erfordert jedoch, dass zuvor ein setkey ausgeführt wird. Wie Sie in diesem Code sehen, dauert es außergewöhnlich lange! Sobald Sie diese Zeit berücksichtigen, ist das Vektor-Scannen viel viel schneller:

set.seed(1) 
n=10^7 
nums <- round(runif(n,0,10000)) 
DT = data.table(s=sample(nums,n), exp=sample(nums,n), 
     init=sample(nums,n), contval=sample(nums,n)) 
this_s = DT[0.5*n,s] 
this_exp = DT[0.5*n,exp] 
this_init = DT[0.5*n,init] 
system.time(ans1<-DT[s==this_s&exp==this_exp&init==this_init,4,with=FALSE]) 
# user system elapsed 
# 0.65 0.01 0.67 
system.time(setkey(DT,s,exp,init)) 
# user system elapsed 
# 41.56 0.03 41.59 
system.time(ans2<-DT[J(this_s,this_exp,this_init),4,with=FALSE]) 
# user system elapsed 
# 0  0  0 
identical(ans1,ans2) 
# [1] TRUE 

Mache ich etwas falsch? Ich habe die data.table FAQs usw. durchgelesen. Jede Hilfe würde sehr geschätzt werden.

Vielen Dank.

Answer 1

Die Linie:

nums <- round(runif(n,0,10000)) 

Blätter nums als Typ numeric nicht integer. Das macht einen großen Unterschied. Die data.table FAQs und die Einführung sind auf integer und character Spalten ausgerichtet; Sie werden setkey nicht langsam auf diesen Typen sehen. Zum Beispiel: wenn

nums <- as.integer(round(runif(n,0,10000))) 
... 
setkey(DT,s,exp,init) # much faster now 

Zwei weitere Punkte ...

Zuerst wird die Bestellung/Sortiervorgänge sind viel schneller in der aktuellen Entwicklungsversion von data.table v1.8.11. @jihoward geht damit richtig um, dass das Sortieren nach numerischen Spalten viel zeitaufwendiger ist. Aber in 1.8.11 ist es immer noch 5-8x schneller (wegen einer 6-Pass-Radix-Order-Implementierung, überprüfen Sie this post). Es ist eine 8.5x Verbesserung auf meinem System

# v 1.8.11 
system.time(setkey(DT,s,exp,init)) 
# user system elapsed 
# 8.358 0.375 8.844 

# v 1.8.10 
system.time(setkey(DT,s,exp,init)) 
# user system elapsed 
# 66.609 0.489 75.216 

: die Zeit für die setkey zwischen 1.8.10 und 1.8.11 genommen zu vergleichen. Also, ich schätze, das würde ungefähr 4,9 Sekunden dauern.

Zweitens, wie @Roland erwähnt, wenn Ihr Ziel ein paar subsetting auszuführen ist und das ist alles, Sie gehen zu tun, dann natürlich macht es keinen Sinn machen, eine setkey zu tun wie es muss die Reihenfolge der Spalten finden und dann die gesamte data.table neu anordnen (durch Referenz, so dass der Speicherbedarf minimal ist, überprüfen Sie this post für mehr auf setkey).