Mat*_*ews 10 hash r data.table
我经常遇到的一个问题是需要从data.table中查找任意行.昨天我遇到了一个问题,我试图加速循环并使用profvis我发现从中查找data.table是循环中最昂贵的部分.然后我决定尝试找到在R中进行单项查找的最快方法.
数据通常采用data.table带有字符类型的键列的a形式.其余列通常是数值.我试图创建一个随机表,其特征与我经常处理的相似,这意味着> 100K行.我比较了本机列表,data.table包和hash包.本机列表与data.table单个项目查找性能相当.Hash似乎快了两个数量级.测试由随机抽样的10组10,000个密钥组成,以提供访问行为的变化.每种查找方法都使用相同的密钥集.
最终我的首选是要让data.table的行查找更快,而不是必须创建我的数据的哈希表,或者确定它不能完成,只需在我必须快速查找时使用哈希包.我不知道是否可能,但是你可以创建一个对data.table中行的引用的哈希表,以允许使用哈希包快速查找吗？我知道在C++中可以使用这种类型的东西,但据我所知,由于缺少指针,R不允许这种事情.
总结一下:1)我是否正确地使用data.table进行查找,因此这是单行查找所需的速度？2)是否可以创建指向data.table行的指针散列,以便以这种方式快速查找？
Windows 10 Pro x64
R 3.2.2
data.table 1.9.6
哈希2.2.6
Intel Core i7-5600U,16 GB RAM
library(microbenchmarkCore) # install.packages("microbenchmarkCore", repos="http://olafmersmann.github.io/drat")
library(data.table)
library(hash)
# Set seed to 42 to ensure repeatability
set.seed(42)
# Setting up test ------
# Generate product ids
product_ids <- as.vector(
outer(LETTERS[seq(1, 26, 1)],
outer(outer(LETTERS[seq(1, 26, 1)], LETTERS[seq(1, 26, 1)], paste, sep=""),
LETTERS[seq(1, 26, 1)], paste, sep = ""
), paste, sep = ""
)
)
# Create test lookup data
test_lookup_list <- lapply(product_ids, function(id){
return_list <- list(
product_id = id,
val_1 = rnorm(1),
val_2 = rnorm(1),
val_3 = rnorm(1),
val_4 = rnorm(1),
val_5 = rnorm(1),
val_6 = rnorm(1),
val_7 = rnorm(1),
val_8 = rnorm(1)
)
return(return_list)
})
# Set names of items in list
names(test_lookup_list) <- sapply(test_lookup_list, function(elem) elem[['product_id']])
# Create lookup hash
lookup_hash <- hash(names(test_lookup_list), test_lookup_list)
# Create data.table from list and set key of data.table to product_id field
test_lookup_dt <- rbindlist(test_lookup_list)
setkey(test_lookup_dt, product_id)
test_lookup_env <- list2env(test_lookup_list)
# Generate sample of keys to be used for speed testing
lookup_tests <- lapply(1:10, function(x){
lookups <- sample(test_lookup_dt$product_id, 10000)
return(lookups)
})
# Native list timing
native_list_timings <- sapply(lookup_tests, function(lookups){
timing <- system.nanotime(
for(lookup in lookups){
return_value <- test_lookup_list[[lookup]]
}
)
return(timing[['elapsed']])
})
# Data.table timing
datatable_timings <- sapply(lookup_tests, function(lookups){
timing <- system.nanotime(
for(lookup in lookups){
return_value <- test_lookup_dt[lookup]
}
)
return(timing[['elapsed']])
})
# Hashtable timing
hashtable_timings <- sapply(lookup_tests, function(lookups){
timing <- system.nanotime(
for(lookup in lookups){
return_value <- lookup_hash[[lookup]]
}
)
return(timing[['elapsed']])
})
# Environment timing
environment_timings <- sapply(lookup_tests, function(lookups){
timing <- system.nanotime(
for(lookup in lookups){
return_value <- test_lookup_env[[lookup]]
}
)
return(timing[['elapsed']])
})
# Summary of timing results
summary(native_list_timings)
summary(datatable_timings)
summary(hashtable_timings)
summary(environment_timings)
这些是结果:
> # Summary of timing results
> summary(native_list_timings)
Min. 1st Qu. Median Mean 3rd Qu. Max.
35.12 36.20 37.28 37.05 37.71 39.24
> summary(datatable_timings)
Min. 1st Qu. Median Mean 3rd Qu. Max.
49.13 51.51 52.64 52.76 54.39 55.13
> summary(hashtable_timings)
Min. 1st Qu. Median Mean 3rd Qu. Max.
0.1588 0.1857 0.2107 0.2213 0.2409 0.3258
> summary(environment_timings)
Min. 1st Qu. Median Mean 3rd Qu. Max.
0.09322 0.09524 0.10680 0.11850 0.13760 0.17140
看起来hash查找比本机列表或data.table在此特定方案中快大约两个数量级.
我收到了Neal Fultz的反馈,建议使用本机Environment对象.这是我得到的代码和结果:
test_lookup_env <- list2env(test_lookup_list)
# Environment timing
environment_timings <- sapply(lookup_tests, function(lookups){
timing <- system.nanotime(
for(lookup in lookups){
return_value <- test_lookup_env[[lookup]]
}
)
return(timing[['elapsed']])
})
summary(environment_timings)
> summary(environment_timings)
Min. 1st Qu. Median Mean 3rd Qu. Max.
0.09322 0.09524 0.10680 0.11850 0.13760 0.17140
实际上,在这种情况下,环境对于单个项目访问来说似乎更快.谢谢你Neal Fultz指出这个方法.我感激的R.可用的对象类型的更透彻地了解我的问题仍然站立:我使用的是data.table正确的(我希望如此,但我愿意接受批评),并在那里提供的行一行访问的方式data.table使用某种指针魔法可以提供更快的单独行访问.
有人提到我在我测试的最内层循环中的访问模式是低效的.我同意.我想要做的是尽可能地模仿我正在处理的情况.这实际发生的循环不允许矢量化,这就是我不使用它的原因.我意识到这不是严格意义上的'R'做事方式.将data.table在我的代码中提供的参考信息,我不一定知道我需要哪一行,直到我这就是为什么我试图找出如何尽可能快地访问单个项目的环内,最好还是存储的数据在一个data.table.这也是一个好奇心问题,可以做到吗？
我收到了来自@jangrorecki的反馈意见,即使用Sys.time()是一种无效的测量函数性能的方法.我已修改了system.nanotime()根据建议使用的代码.原始代码已更新并且计时结果.
问题仍然存在:这是对a进行行查找的最快方法吗？data.table如果是这样,是否可以创建指向行的指针散列以便快速查找？在这一点上,我最好奇R可以推动多远.作为来自C++的人,这是一个有趣的挑战.
我接受了Neal Fultz提供的答案,因为它讨论了我真正想知道的事情.也就是说,这不是data.table打算使用的方式,所以没有人应该解释这意味着data.table很慢,它实际上是非常快.这是一个非常特殊的用例,我很好奇.我的数据是作为一个data.table,我想知道我是否可以快速访问行,同时将其作为一个data.table.我还想将data.table访问速度与散列表进行比较,散列表通常用于快速,非矢量化项目查找.
对于非向量化访问模式,您可能希望尝试内置environment对象:
require(microbenchmark)
test_lookup_env <- list2env(test_lookup_list)
x <- lookup_tests[[1]][1]
microbenchmark(
lookup_hash[[x]],
test_lookup_list[[x]],
test_lookup_dt[x],
test_lookup_env[[x]]
)
在这里你可以看到它甚至比zippier hash:
Unit: microseconds
expr min lq mean median uq max neval
lookup_hash[[x]] 10.767 12.9070 22.67245 23.2915 26.1710 68.654 100
test_lookup_list[[x]] 847.700 853.2545 887.55680 863.0060 893.8925 1369.395 100
test_lookup_dt[x] 2652.023 2711.9405 2771.06400 2758.8310 2803.9945 3373.273 100
test_lookup_env[[x]] 1.588 1.9450 4.61595 2.5255 6.6430 27.977 100
编辑:
逐步通过data.table:::`[.data.table`是有益的,为什么你看到dt减速.当你使用一个字符进行索引并且有一个密钥集时,它会进行相当多的记账,然后再进行下载bmerge,这是一个二进制搜索.二进制搜索是O(log n),随着n的增加会变慢.
另一方面,环境使用散列(默认情况下)并且相对于n具有恒定的访问时间.
要解决此问题,您可以通过它手动构建地图和索引:
x <- lookup_tests[[2]][2]
e <- list2env(setNames(as.list(1:nrow(test_lookup_dt)), test_lookup_dt$product_id))
#example access:
test_lookup_dt[e[[x]], ]
但是,在data.table方法中看到如此多的簿记代码,我也会尝试普通的旧数据框架:
test_lookup_df <- as.data.frame(test_lookup_dt)
rownames(test_lookup_df) <- test_lookup_df$product_id
如果我们真的是偏执狂,我们可以[完全跳过这些方法并直接对列进行讨论.
这里有一些更多的时间(来自不同于上面的机器):
> microbenchmark(
+ test_lookup_dt[x,],
+ test_lookup_dt[x],
+ test_lookup_dt[e[[x]],],
+ test_lookup_df[x,],
+ test_lookup_df[e[[x]],],
+ lapply(test_lookup_df, `[`, e[[x]]),
+ lapply(test_lookup_dt, `[`, e[[x]]),
+ lookup_hash[[x]]
+ )
Unit: microseconds
expr min lq mean median uq max neval
test_lookup_dt[x, ] 1658.585 1688.9495 1992.57340 1758.4085 2466.7120 2895.592 100
test_lookup_dt[x] 1652.181 1695.1660 2019.12934 1764.8710 2487.9910 2934.832 100
test_lookup_dt[e[[x]], ] 1040.869 1123.0320 1356.49050 1280.6670 1390.1075 2247.503 100
test_lookup_df[x, ] 17355.734 17538.6355 18325.74549 17676.3340 17987.6635 41450.080 100
test_lookup_df[e[[x]], ] 128.749 151.0940 190.74834 174.1320 218.6080 366.122 100
lapply(test_lookup_df, `[`, e[[x]]) 18.913 25.0925 44.53464 35.2175 53.6835 146.944 100
lapply(test_lookup_dt, `[`, e[[x]]) 37.483 50.4990 94.87546 81.2200 124.1325 241.637 100
lookup_hash[[x]] 6.534 15.3085 39.88912 49.8245 55.5680 145.552 100
总的来说,要回答你的问题,你没有使用data.table"错误",但你也没有按照预期的方式使用它(矢量化访问).但是,您可以手动构建映射以进行索引,并获得大部分性能.
您采用的方法效率非常低,因为您要查询数据集中单个值的多倍.
一次查询所有这些,然后循环整个批处理,而不是一个一个地查询1e4会更有效.
见DT2的量化方法.我仍然难以想象这个用例.
另外一件事是450K行的数据很少能够制作出合理的基准,你可能会得到完全不同的4M或更高的结果.就哈希方法而言,您可能还会更快地达到内存限制.
另外,这Sys.time()可能不是测量时序的最佳方法,读取gc参数?system.time.
这是我使用microbenchmarkCore包中的system.nanotime()函数制作的基准.
通过折叠test_lookup_list到data.table并执行合并test_lookup_dt,可以进一步加速data.table方法,但是为了与哈希解决方案进行比较,我还需要对其进行预处理.
library(microbenchmarkCore) # install.packages("microbenchmarkCore", repos="http://olafmersmann.github.io/drat")
library(data.table)
library(hash)
# Set seed to 42 to ensure repeatability
set.seed(42)
# Setting up test ------
# Generate product ids
product_ids = as.vector(
outer(LETTERS[seq(1, 26, 1)],
outer(outer(LETTERS[seq(1, 26, 1)], LETTERS[seq(1, 26, 1)], paste, sep=""),
LETTERS[seq(1, 26, 1)], paste, sep = ""
), paste, sep = ""
)
)
# Create test lookup data
test_lookup_list = lapply(product_ids, function(id) list(
product_id = id,
val_1 = rnorm(1),
val_2 = rnorm(1),
val_3 = rnorm(1),
val_4 = rnorm(1),
val_5 = rnorm(1),
val_6 = rnorm(1),
val_7 = rnorm(1),
val_8 = rnorm(1)
))
# Set names of items in list
names(test_lookup_list) = sapply(test_lookup_list, `[[`, "product_id")
# Create lookup hash
lookup_hash = hash(names(test_lookup_list), test_lookup_list)
# Create data.table from list and set key of data.table to product_id field
test_lookup_dt <- rbindlist(test_lookup_list)
setkey(test_lookup_dt, product_id)
# Generate sample of keys to be used for speed testing
lookup_tests = lapply(1:10, function(x) sample(test_lookup_dt$product_id, 1e4))
native = lapply(lookup_tests, function(lookups) system.nanotime(for(lookup in lookups) test_lookup_list[[lookup]]))
dt1 = lapply(lookup_tests, function(lookups) system.nanotime(for(lookup in lookups) test_lookup_dt[lookup]))
hash = lapply(lookup_tests, function(lookups) system.nanotime(for(lookup in lookups) lookup_hash[[lookup]]))
dt2 = lapply(lookup_tests, function(lookups) system.nanotime(test_lookup_dt[lookups][, .SD, 1:length(product_id)]))
summary(sapply(native, `[[`, 3L))
# Min. 1st Qu. Median Mean 3rd Qu. Max.
# 27.65 28.15 28.47 28.97 28.78 33.45
summary(sapply(dt1, `[[`, 3L))
# Min. 1st Qu. Median Mean 3rd Qu. Max.
# 15.30 15.73 15.96 15.96 16.29 16.52
summary(sapply(hash, `[[`, 3L))
# Min. 1st Qu. Median Mean 3rd Qu. Max.
# 0.1209 0.1216 0.1221 0.1240 0.1225 0.1426
summary(sapply(dt2, `[[`, 3L))
# Min. 1st Qu. Median Mean 3rd Qu. Max.
#0.02421 0.02438 0.02445 0.02476 0.02456 0.02779