高效的搜索和更新，数据表或稀疏矩阵-R
我正在尝试找到最有效的方法来重复搜索引用表中两个变量的组合。该问题基于具有退火步长的爬山算法的实现，因此增加了问题的复杂性。
为了解释，假设我有两个想要优化的变量A和B。我从这些变量的100个组合开始，我将遍历这些组合
set.seed(100)
A_start <- sample(1000,10,rep=F)
B_start <- sample(1000,10,rep=F)
A_B_starts<-expand.grid(A = A_start,
B = B_start)
head(A_B_starts)
A B
1 714 823
2 503 823
3 358 823
4 624 823
5 985 823
6 718 823对于这些开始组合中的每一个，我希望在预测模型中使用它们的近邻，如果它们的误差小于开始组合的误差，则继续沿着该方向进行。重复这一过程，直到达到最大迭代次数或误差增加(标准爬山)。但是，我不想重新检查我已经查看过的组合，为此，我想使用一个参考表来存储检查过的组合。然后，在运行预测模型之前，每次生成直接邻居时，我都会检查它们是否在参考表中。任何存在的内容都会被简单地删除。增加了更多的复杂性，因为我希望生成紧邻的步长是退火的；随着时间的推移变得更小。我已经使用data.tables实现了这一点
max_iterations <-1e+06
#Set max size so efficient to add new combinations, max size is 100 start points by max iterations allowed
ref <-data.table(A=numeric(),
B=numeric(),
key=c("A","B"))[1:(100*max_iterations)]
ref
A B
1: NA NA
2: NA NA
3: NA NA
4: NA NA
5: NA NA
---
99999996: NA NA
99999997: NA NA
99999998: NA NA
99999999: NA NA
100000000: NA NA所以循环实际处理这个问题
step_A <- 5
step_B <- 5
visited_counter <- 1L
for(start_i in 1:nrow(A_B_starts)){
initial_error <- get.error.pred.model(A_B_starts[1,])
A <-A_B_starts[1,1]
B <-A_B_starts[1,2]
#Add start i to checked combinations
set(ref, i=visited_counter, j="A", value=A)
set(ref, i=visited_counter, j="B", value=B)
visited_counter <- visited_counter+1L
iterations <- 1
while(iterations<max_iterations){
#Anneal step
decay_A = step_A / iterations
decay_B = step_B / iterations
step_A <- step_A * 1/(1+decay_A*iterations)
step_B <- step_B * 1/(1+decay_B*iterations)
#Get neighbours to check
to_visit_A <- c(A+step_A,A-step_A)
to_visit_B <- c(B+step_B,B-step_B)
to_visit <- setDT(expand.grid("A"=to_visit_A,"B" = to_visit_B),
key=c("A","B"))
#Now check if any combination have been checked before and remove if so
#set key for efficient searching - need to reset in loop as you are updating values in datatable
setkey(ref,A,B)
prev_visited<-ref[to_visit,nomatch=0L]
to_visit<-to_visit[!prev_visited]
#Run model on remaining combinations and if error reducing continue
best_neighbour <- get.min.error.pred.model(to_visit)
if(best_neighbour$error<initial_error){
initial_error <- best_neighbour_error
A <- best_neighbour$A
B <- best_neighbour$B
}
else{
iterations <- max_iterations
}
#Add all checked to reference and also update the number of iterations
for(visit_i in 1L:nrow(to_visit)){
#This will reset the key of the data table
set(ref, i=visited_counter, j="A", value=to_visit[visit_i,1])
set(ref, i=visited_counter, j="B", value=to_visit[visit_i,2])
visited_neighbour_counter <- visited_counter+1L
iterations <- iterations+1
}
}
}这种方法的问题是，我必须在每次循环迭代时重置键，因为已经向ref添加了一个新的组合，这使得它非常慢：
setkey(ref,A,B)
prev_visited<-ref[to_visit,nomatch=0L]
to_visit<-to_visit[!prev_visited]此外，我提到退火的原因是因为我有另一个想法，使用稀疏矩阵；Matrix保存已经检查的对的指示符，这将允许非常快速的检查
require(Matrix)
#Use a sparse matrix for efficient search and optimum RAM usage
sparse_matrix <- sparseMatrix(A = 1:(100*1e+06),
B = 1:(100*1e+06) )然而，由于步长是可变的，即A/B可以以越来越小的间隔保持任何值，我不知道如何在稀疏矩阵中初始化A和B的适当值来捕获所有可能的组合。
回答 1
Stack Overflow用户
发布于 2020-05-18 16:39:53
(不是真正的答案，但太长了，不能发表评论。)
如果可能的解决方案数量巨大，则可能不切实际或不可能将它们全部存储。更重要的是，查找单个解决方案的最快方法通常是哈希表；但是设置哈希表很慢，因此您可能不会获得太多(您的目标函数需要比这种设置/查找-oberhead更昂贵)。根据问题的不同，这种存储解决方案的大部分可能是一种浪费；算法可能永远不会重新访问它们。另一种建议可能是先进/先出数据结构，它只存储访问过的最后N个解决方案。(对于短列表，即使是线性查找也可能比使用重复设置的哈希表更快。)但在任何情况下，我都会从一些测试开始，测试算法是否以及重新访问特定解决方案的频率。
https://stackoverflow.com/questions/61849147
复制相似问题
腾讯云开发者
