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

我正在尝试找到一种更好的方法来管理当前连续马尔可夫链的当前状态向量。使用的状态向量存储成对的（状态，概率），其中概率为浮点数。

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


每次迭代都以当前状态向量开始
计算向量中每个当前状态的可达状态，并将所有状态存储在一个临时列表中
对于此新列表中的每个元素，它都会通过迭代可能的转换来计算新的状态向量（请注意，可能有许多转换导致相同的状态，但从不同的源状态中找到）


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

因此，基本上是要构建新的矢量，对于每个跃迁，都要计算归一化值，然后使用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操作，但是对哈希表进行如此多的操作会降低性能，因为常量成本是相当昂贵的。

最佳答案

用恒定时间if List.length ts = 0代替线性时间if ts = []不会有什么坏处，尽管我怀疑这将解决您的性能问题。

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

关于optimization - 此操作的最佳数据结构，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4096566/