先进先出存储结构中的随机

我正在寻找一个适当高效的存储结构，用于处理以随机顺序到达但必须按指定顺序处理和/或从堆栈中移除的数据。先进先出存储结构中的随机

为了使这更清楚：

每个项x具有索引i，时间戳T和被处理如下（假设已填充的存储结构）。

repeat 
    1) Process (remove) the item with the smallest time stamp. 
    2) Add new items (0 or more). 
    3) Remove (0 or more) items (referenced by their index). 
until false

保证每个项目都有唯一的时间戳和索引。但是，直到步骤1）完成，或者在步骤3）中将移除多少项目，直到在算法的每个循环内完成步骤1）和2）之前，预测步骤2）中将添加多少项目是不可能的。传入项目的时间戳分布不能被预测（除了新的时间戳将在'未来'中），并且可能随着时间而变化 - 也就是说可能会有一堆随机分布的时间戳，后面跟着一堆时间戳都会更大（或小于）列表中剩余的任何项目。任何时候都会有最大数量的等待处理的元素，但这可能会相当大〜10^6-10^8，并且我需要尽可能快地处理它们 - 注意实际处理时间是对于大量数据我相当小，我预计'调度'将主宰我可以处理数据的速度。

如果我在步骤2）中将每个项目添加到链接的排序列表中，则步骤1）为O（0），但步骤2）为O（n）。如果我使用二叉树，那么步骤1）仍然是O（1），现在步骤2）最初是O（log n），但是如果时间戳没有很好地分布，树会很快失去平衡，这会减慢步骤2）显着下降（如果我不经常重新平衡树，最终不会比O（n）好）。

我的猜测是，如果重新平衡是在正确的间隔完成的，那么沿着二叉树的定期重新平衡的方向应该提供O（log n），但我认为这种问题很好已经解决了，所以有人可以指导我做适当的参考，或者给我一点建议，以帮助我避免重新发明车轮。

来源

2012-08-02 Penguino

因此，我停止阅读所有关于“明确说明”的内容，但为什么不是[Priority Queue]（http://en.wikipedia.org/wiki/Priority_queue）？（查看实现。） – 2012-08-02 03:13:30

你想要的是一个时间调度队列，它是一种优先队列形式。 – RBarryYoung 2012-08-02 03:19:42

通过数据结构堆，您可以使用O（logN）中的所有操作轻松完成此操作。

http://en.wikipedia.org/wiki/Heap_(data_structure)

堆所花费的时间的时间戳作为键。并且你将需要一个额外的数组（或字典）来存储对Q =（item.Index，该项目在堆中的位置）。

由于它是一堆，操作1）和2）将花费O（logN）为每个项目。

而对于操作3），您将需要从堆中移除随机项。幸运的是，这很容易，如here所述。因为item.index不是它在堆中的实际位置，所以需要上述的字典Q，通过其item中的item.Index（在散列映射中）查找堆中项的位置。，否则将花费O（N）来寻找那个位置。并且由于在操作（包括操作1和操作2）期间项目的位置可能会发生变化，请记住每次在堆中移动项目时都要更改Q中的值。

正如有人提到有关Priority Queue的问题，我将在此添加更多单词。

优先级队列是一种抽象数据类型，具有一些抽象接口。而这些接口不包括常规意义上的“移除随机项目”。

堆是一种数据结构。

优先队列可以用堆实现。但是堆可以支持比优先级队列更多的操作。

来源

2012-08-02 03:46:57 lavin

谢谢 - 这看起来很有用 – Penguino 2012-08-02 04:07:01

先进先出存储结构中的随机

回答

相关问题