我正在尝试寻找一种比我目前使用的更好的方法来管理连续马尔可夫链的当前状态向量。所使用的状态向量存储了（状态，概率）对，其中概率是一个浮点数。
需要优化的算法部分执行以下操作：
- 每次迭代都从当前状态向量开始 - 计算每个当前向量中的可达状态，并将它们与到达这些状态的概率一起存储在临时列表中 - 对于这个新列表中的每个元素，通过迭代可能的转换（注意，可能有许多转换导致相同的状态，但是从不同的源状态发现），计算新的状态向量
实际上，这是通过使用哈希表来完成的，哈希表的键是状态，值是概率。
因此，基本上为了建立新向量，对于每个转换，都会计算归一化值，然后使用get检索向量中的状态，添加当前转换的概率，然后将结果存储回去。
到目前为止，这种方法似乎有效，但我正在尝试应对导致非常大的空间向量（500k-1mil状态）的系统，因此，尽管哈希表提供了恒定的复杂度来存储和检索，但迭代速度确实变得非常慢。
例如，我们从具有100k个状态的向量开始，对于每个状态，我们计算可达状态（通常>1），从而获得100k *（平均可达状态）的转换列表。然后遍历每个转换以计算新的概率向量。
不幸的是，我需要浏览整个可达列表才能找到规范化值，而实际上并没有计算下一个向量，但无论如何，正如我通过分析看到的那样，这不是算法的瓶颈。瓶颈存在于计算每个转换时。
这是用于从当前向量（pi）计算转换列表的函数：
需要优化的算法部分执行以下操作：
- 每次迭代都从当前状态向量开始 - 计算每个当前向量中的可达状态，并将它们与到达这些状态的概率一起存储在临时列表中 - 对于这个新列表中的每个元素，通过迭代可能的转换（注意，可能有许多转换导致相同的状态，但是从不同的源状态发现），计算新的状态向量
实际上，这是通过使用哈希表来完成的，哈希表的键是状态，值是概率。
因此，基本上为了建立新向量，对于每个转换，都会计算归一化值，然后使用get检索向量中的状态，添加当前转换的概率，然后将结果存储回去。
到目前为止，这种方法似乎有效，但我正在尝试应对导致非常大的空间向量（500k-1mil状态）的系统，因此，尽管哈希表提供了恒定的复杂度来存储和检索，但迭代速度确实变得非常慢。
例如，我们从具有100k个状态的向量开始，对于每个状态，我们计算可达状态（通常>1），从而获得100k *（平均可达状态）的转换列表。然后遍历每个转换以计算新的概率向量。
不幸的是，我需要浏览整个可达列表才能找到规范化值，而实际上并没有计算下一个向量，但无论如何，正如我通过分析看到的那样，这不是算法的瓶颈。瓶颈存在于计算每个转换时。
这是用于从当前向量（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操作，但是这样做太多次会导致性能下降，因为常数成本非常昂贵。