使用 OCaml 实现高效的函数式数据结构，用于频繁重新调度的队列。

Question

使用 OCaml 实现高效的函数式数据结构，用于频繁重新调度的队列。

data-structuresocamlocaml-batteries

3

我的问题是选择一个事件驱动模拟的数据结构。

一些未来事件及其发生时间会被维护。N是固定的或至少有界的，范围从10到10000不等。每个事件都有一个唯一的ID，原则上可以通过这个ID检索到它，除了时间之外。

在循环中，以下操作发生：下一个即将发生的事件被移除并执行，然后为随机未来时间生成相同类型的新事件以替换它。作为副作用，一些（＜10）现有事件的发生时间会改变，并需要重新安排。这些待重新安排的事件的ID已知，但不知道它们的发生时间。

我想使用堆来快速获取最小元素，但我也需要快速重新排序任意元素，这些元素由ID访问。有一个名为BatHeap的工具，可以在O(log N)内找到元素并插入，但似乎不允许索引访问？

我更喜欢持久化的结构（部分是为了教育目的），但如果只有可变结构可以快速运行，我将使用它。

- user3240588

2个回答

2

初步估计，您可以使用堆或映射（堆具有O(1)的remove-first而不是O(log n)，但可能无法实现随机删除），并将其与将id映射到时间的哈希表配对。映射结构不需要持久存在，因为它可以从时间索引结构轻松重建。

- gasche

好的，这听起来是可行的。如果我理解正确，有一个带有浮点键（即时间）的 Map。在 log(N) 的时间内，我取出最小元素，再用 log(N) 的时间插入替换事件。然后，我获取需要重新调度的候选人的 ID，并在 O(1) 的时间内在 Hashtbl 中查找它们，以获取事件时间作为值。对于每个候选人，再次使用 log(n) 的时间将其按时间从 Map 中取出，并使用 log(n) 的时间将每个候选人重新插入 Map 中，以获得新的修改时间。最后，从 Hashtbl 中删除旧条目并添加新条目（不知道这会有多大的代价）。 - user3240588

实际上，如果我为每个事件类型（id）定义整数索引，我可以用一个普通的浮点数组替换Hashtbl部分来存储时间。这样会更快吗？ - user3240588

如果它们是连续的整数，那么速度比哈希表要快得多。但我不确定如何在合理的范围内生成相对连续的整数流，并进行动态插入/删除，而不使用半奇怪的压缩策略。我想这取决于应用程序。 - gasche

在我的特定应用程序中，这将起作用。有确切的N个事件类型，并且任何给定时间只安排其中一个。因此，我可以分配从1到N的索引来标记事件类型。 - user3240588

经过一些更多的维基谷歌搜索，我接受了这个答案。（抱歉@jackson-tale，但这是更好的解释）。对于其他人的附注：单个treap也似乎是一个合理的选择。由于事件具有随机发生时间，因此不需要额外的随机数来进行treap操作；并且频繁发生的事件类型会上升到顶部。 - user3240588

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jackson Tale · Accepted Answer

你的问题需要使用优先队列，而对于优先队列来说，堆是最好的选择。

如果你需要一个持久化堆，你可以用OCaml实现一个左偏堆（Leftist heap），以满足你的教育目的。

然而，由于它是函数式堆，BatHeap也可以满足你的需求。

好的，现在我知道你想要一个“堆+映射”（heap + map）的东西。

你需要知道 OCaml 中映射操作的时间复杂度是 O(logN)，这是由于函数式编程的原因。你可以使用 hashtbl，但它使用数组，这是一种命令式而非持久化或函数式的方式。

如果你想要一个纯函数式的方式，并且可以接受 O(logN) 的时间复杂度，那么你需要有两种数据结构，一种是堆，另一种是映射。

在映射中，键是事件类型 ID，值是该事件类型的堆。

但我猜即使你发明了一个 HeapMap，你仍然需要双倍的空间，因为两种信息（时间顺序和索引顺序）都需要维护。