optimization - 此操作的最佳数据结构

Question

我试图找到一种更好的方法来管理连续马尔可夫链的当前状态向量。使用的状态向量存储(状态，概率)对，其中概率是一个浮点数。

需要优化的算法部分执行以下操作:

每次迭代都从当前状态向量开始

计算向量中每个当前状态的可达状态，并将它们与到达那里的概率一起存储在一个临时列表中

对于这个新列表中的每个元素，它通过迭代可能的转换来计算新的状态向量(请注意，可能有许多导致相同状态但从不同源状态找到的转换)

这实际上是通过使用哈希表来完成的，哈希表将状态作为键，将概率作为值。

所以基本上要建立新的向量，对于每个转换，计算归一化值，然后用 get 检索向量中的状态，添加当前转换的概率，然后将结果存储回来。

到目前为止，这种方法似乎有效，但我正在尝试处理导致非常大的空间向量(500k-1mil 状态)的系统，因此，尽管哈希表为存储和检索提供了恒定的复杂性，但迭代确实开始放慢了很多。

这是因为例如，我们从具有 100k 个状态的向量开始，对于每个状态，我们计算可达状态(通常 > 1)，以便我们获得 100k*(平均可达状态)的转换列表。然后通过每个转换来计算新的概率向量。

不幸的是，我需要遍历整个可达列表才能找到规范化值，而无需实际计算下一个 vecto，但无论如何，正如我通过分析看到的，这不是算法的瓶颈。计算每个转换时都会出现瓶颈。

这是用于从当前向量 ( pi ) 计算转换列表的函数:

HTable.fold (fun s p l ->
  if check s f2 then (0., s, p, [s, 1.0]) :: l
  else if not (check s f1) then (0., s, p, [s, 1.0]) :: l
  else
    let ts = P.rnext s in                         
    if List.length ts = 0 then (0., s, p, [s, 1.0]) :: l
    else
      let lm = List.fold_left (fun a (s,f) -> f +. a) 0. ts in
      (lm, s, p, ts) :: l) pi []

这是计算新 pi 的函数通过浏览转换列表并将它们全部标准化:

let update_pi s v = 
  try
    let t = HTable.find pi s in
    HTable.replace pi s (v +. t)
  with Not_found -> HTable.add pi s v
in
  HTable.clear pi;
  List.iter (fun (llm, s, p, ts) ->
    if llm = 0. then
      update_pi s p
    else begin
      List.iter (fun (ss, pp) -> 
        update_pi ss (p *. (pp /. lm))
      ) ts;
      if llm < lm then update_pi s (p *. (1. -. (llm /. lm)))
    end 
  ) u;

我应该找到一个更适合我正在做的操作的数据结构，问题是，使用当前的方法，我必须为每个单独的转换做一个 get 和一个 set，但是在哈希表上执行如此多的操作会降低性能，因为常数成本相当昂贵。

Answer 1

更换线性时间无害if List.length ts = 0按恒定时间 if ts = [] ，虽然我怀疑这是否会解决您的性能问题。

你的算法听起来有点像矩阵乘以向量得到一个新向量。这通常由 blocking 加速.但是在这里，哈希表中的表示可能会消耗您的位置。是否有可能一劳永逸地对所有状态进行编号，然后使用数组而不是哈希表？请注意，对于任意转换，目标状态仍然不是本地状态，但它可能是一种改进(如果仅仅是因为访问数组比访问哈希表更直接)。