持久性队列数据结构

我需要创建一个类持久化队列，其中函数入队需要一个元素将其排入当前队列并返回新队列。原始队列如何保持不变。同样，出列函数删除前面的元素，返回新的队列，但原始队列保持不变。这当然可以在O（队列的长度）中完成，但我可以做得更快。持久性队列数据结构

来源

2014-01-14 Aditya Nambiar

是否有任何理由为什么你需要一成不变的队列？ – Njol

@ Gab是的，因为回答无用的问题是无用的。如果我们知道提问者打算做什么，那么可以提出更好的方法，而不是提问者最初打算做的事情。 – Njol

回到主题：我相信你将无法复制任何集合的每个元素，而无需迭代每个元素一次。因此，比O（n）好看似乎对我来说不合理。 – ccjmne

你可以使用链表作为队列（不是LinkedList，但是你自己的实现）。

要添加一个新元素，您只需创建一个新的队列类实例，将其开始元素设置为复制队列的开始元素，并创建一个新的结束元素。

删除元素与此类似，但将新队列的结束元素设置为复制队列的倒数第二个元素。

队列类看起来是这样的：

static class Node { 
    final Node next; 
    final Object o; 
    Node(Node next, Object o) {...} 
} 

final Node start, end; 

private Queue(Node start, Node end) {...} 

public Queue(Object o) { 
    start = end = new Node(null, o); 
} 

public Queue add(Object o) { 
    return new Queue(start, new Node(end, o)); 
} 

public Queue remove() { 
    return new Queue(start, end.next); 
}

的这一队列的add和remove方法复杂度为O（1）。

请注意，您只能以相反的顺序（即最新的元素）迭代此队列。也许你可以想出一些可以以其他方式迭代或甚至在两个方向上迭代的东西。

来源

2014-01-14 08:37:12 Njol

双向链表应该允许你在两个方向上迭代。 –

@PeterLawrey然后你将不能在O（1）中添加或删除，因为你必须复制每个节点（如果我的代码天真地扩展了一个新的'Node previous'） – Njol

好点。每个队列都需要有一个自己的前一个字段。如果你只有一个生产者，这将不是一个问题。 –

我所做的是使用Java Chronicle（免责声明：我写的）。这是存储在磁盘或tmpfs（共享内存）上的一个无界的堆持久化队列。

在这种方法您的消费跟踪，其中它是由在排队，但没有进入实际删除（除非在每天或每周的保养周期）

这避免了需要改变的队列中，除了当添加到它时，你不需要复制它。因此，保持对每个消费者认为的地方的多个引用是每个消费者的队列的尾部是O（1）。

由于Chronicle使用紧凑的二进制格式，因此可以存储多少的限制受到磁盘空间的限制。例如即使在8 GB的计算机上，2 TB驱动器也可以存储大量数据，然后再旋转队列日志。

来源

2014-01-14 08:35:02

您不能使用此方法添加元素而不修改数据结构 – Njol

@Njol如果您需要此功能，您还可以记录结束位置。要拍摄所有你需要知道的是开始和结束。 O（1）。只有当您想添加到多个快照并且您不能应用排队消息的任何过滤器时，问题才会出现。 –

我建议看看scala的实现。对课程顶部的评论描述了所选方法（复杂性：O(1)）。

Queue被实现为对List S，一个包含“”中“”的元素和其它的“”出来“”元素。
元素被添加到''in''列表中，并从''out''列表中删除。当'out''列表干涸时，队列通过用'in.reverse'替换''out''列表，并用''Nil''替换''in''。

将项目添加到队列始终有成本O(1)。删除物品的费用为O(1)，但在需要数据透视的情况下为，在这种情况下，将产生O(n)的费用，其中n是队列中元素的数量。发生这种情况时， n删除操作与O(1)成本有保证。删除项目平均为O(1)。

http://xuwei-k.github.io/scala-library-sxr/scala-library-2.10.0/scala/collection/immutable/Queue.scala.html

来源

2014-01-14 08:51:00 Gab

持久性队列数据结构

回答

相关问题