java - 数据结构 - 随机队列

Question

我目前正在处理 Queues assignment来自普林斯顿的算法第一部分。其中一项任务是实现一个随机队列。这是一个关于使用不同数据结构的实现和权衡的问题。

问题:

随机队列类似于堆栈或队列，只是删除的项目是从数据结构中的项目中均匀随机选择的。创建实现以下 API 的通用数据类型 RandomizedQueue:

public class RandomizedQueue<Item> implements Iterable<Item> {
    public RandomizedQueue() // construct an empty randomized queue
    public boolean isEmpty() // is the queue empty?
    public int size() // return the number of items on the queue
    public void enqueue(Item item) // add the item
    public Item dequeue() // remove and return a random item
    public Item sample() // return (but do not remove) a random item
    public Iterator<Item> iterator() // return an independent iterator over items in random order
    public static void main(String[] args)   // unit testing
}

这里的关键是实现出队操作和迭代器，因为出队移除并返回一个随机元素，并且迭代器以随机顺序遍历队列。

1.数组实现:

我考虑的主要实现是数组实现。除了随机性之外，这将与数组队列的实现相同。

查询 1.1: 对于出队操作，我只是简单地从数组的大小中随机选择一个数字并返回该项目，然后将数组中的最后一项移动到返回的位置项目。

但是，这种方法会改变队列的顺序。在这种情况下，这并不重要，因为我以随机顺序出队。但是，我想知道是否有一种时间/内存有效的方法可以从数组中取出一个随机元素，同时保留队列的顺序，而不必创建一个新数组并将所有数据传输给它。

// Current code for dequeue - changes the order of the array after dequeue
private int[] queue; // array queue
private int N; // number of items in the queue

public Item dequeue() {
    if (isEmpty()) throw NoSuchElementException("Queue is empty");
    int randomIndex = StdRandom.uniform(N);
    Item temp = queue[randomIndex]        

    if (randomIndex == N - 1) {
        queue[randomIndex] = null; // to avoid loitering
    } else {
        queue[randomIndex] = queue[N - 1];
        queue[randomIndex] = null; 
    }

    // code to resize array

    N--;
    return temp;
}

查询 1.2: 为了让迭代器满足随机返回元素的要求，我用队列的所有索引创建了一个新数组，然后用 Knuth shuffle 操作对数组进行洗牌并返回队列中那些特定索引处的元素。但是，这涉及创建一个与队列长度相等的新数组。同样，我确信我错过了一种更有效的方法。

<强>2。内部类实现

第二种实现涉及一个内部节点类。

public class RandomizedQueue<Item> {
    private static class Node<Item> {
        Item item;
        Node<Item> next;
        Node<Item> previous;
    }
}

查询 2.1。 在这种情况下，我了解如何有效地执行出队操作:返回一个随机节点并更改相邻节点的引用。

但是，我对如何返回一个以随机顺序返回节点的迭代器感到困惑，而不必创建一个以随机顺序附加节点的全​​新队列。

此外，除了可读性和易于实现之外，在数组上使用这种数据结构还有什么好处？

这篇文章有点长。感谢你们花时间阅读我的问题并帮助我。谢谢!

Answer 1

在您的数组实现中，您的 Query 1.1 似乎是做事的最佳方式。删除随机元素的唯一其他方法是将所有内容向上移动以填充其位置。因此，如果您有 [1,2,3,4,5] 并且您删除了 2，您的代码会将项目 3、4 和 5 向上移动并且您会减少计数。每次移除平均需要 n/2 个项目移动。所以去除是O(n)。不好。

如果您不会在迭代时添加和删除项目，那么只需在现有数组上使用 Fisher-Yates 洗牌，然后开始从前到后返回项目。没有理由复制。这实际上取决于您的使用模式。如果您设想在迭代时从队列中添加和删除项目，那么如果您不制作副本，事情就会变得不稳定。

使用链表的方法，随机出队操作很难有效地实现，因为为了得到一个随机项，你必须从前面遍历列表。因此，如果您在队列中有 100 个项目并且您想要删除第 85 个项目，则您必须从前面开始并遵循 85 个链接，然后才能到达要删除的那个。由于您使用的是双向链表，因此当要删除的项目超过中点时，您可以通过从末尾倒数来将时间减半，但是当队列中的项目数量时，它仍然非常低效很大。想象一下从一百万个项目的队列中删除第 500,000 个项目。

对于随机迭代器，您可以在开始迭代之前就地打乱链表。这需要 O(n log n) 时间，但只需要 O(1) 额外空间。同样，您在添加或删除的同时存在迭代问题。如果你想要那个能力，那么你需要制作一个副本。