有效的搜索和更新，数据表或稀疏矩阵-R

Question

我正在尝试找到最有效的方法来重复搜索参考表中两个变量的组合。该问题基于具有退火步长的爬山算法的实现，因此，该问题增加了很多复杂性。

解释一下，我有两个要优化的变量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的适当值以捕获所有检查的可能组合？

Answer 1

（不是真正的答案，但评论太久。）

如果可能的解决方案数量巨大，则可能将它们存储起来是不切实际或不可能的。什么更多，查找单个解决方案的最快方法通常是一个哈希表；但是设置哈希表速度慢，因此您可能不会获得太多收益（您的目标功能需要更昂贵设置/查找标头）。根据问题，这种存储解决方案中的大部分可能是浪费；的算法可能永远不会再访问它们。替代建议可能是先进先出数据结构，仅存储最后的N个解决方案被访问过的。 （即使是线性查找也可能是比使用重复设置的哈希表短时间更快列表。）但无论如何，我将从一些测试开始该算法是否以及多久重新访问一次特定解决方案。