java 数据结构 - 随机队列

Data Structures - Randomized Queues

提问by philosopher

I am currently working on the Queues assignmentfrom Princeton's Algorithms Part I. One of the assignments is to implement a randomized queue. This is a question regarding the implementation and tradeoffs of using different data structures.

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

Question:

问题：

A randomized queue is similar to a stack or queue, except that the item removed is chosen uniformly at random from items in the data structure. Create a generic data type RandomizedQueue that implements the following API:

随机队列类似于堆栈或队列，不同之处在于删除的项目是从数据结构中的项目中随机统一选择的。创建实现以下 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
}

The catch here is to implement the dequeue operation and the iterator since the dequeue removes and returns a random elementand the iterator iterates over the queue in a random order.

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

1. Array Implementation:

1.数组实现：

The primary implementation I was considering is an array implementation. This will be identical to the implementation of an an array queue except the randomness.

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

Query 1.1:For the dequeue operation, I simply select a number randomly from the size of the array and return that item, and then move the last item in the array to the position of the returned item.

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

However, this approach changes the order of the queue. In this case it does not matter since I am dequeuing in random order. However, I was wondering if there was an time/memory efficient way to dequeue a random element from the array while preserving the order of the queue without having to create a new array and transfer all the data to it.

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

// 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;
}

Query 1.2:For the iterator to meet the requirement of returning elements randomly, I create a new array with all the indices of the queue, then shuffle the array with a Knuth shuffle operation and return the elements at those particular indices in the queue. However, this involves creating a new array equal to the length of the queue. Again, I am sure I am missing a more efficient method.

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

2. Inner Class Implementation

2. 内部类实现

The second implementation involves an inner node class.

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

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

Query 2.1.In this case I understand how to perform the dequeue operation efficiently: Return a random node and change the references for the adjacent nodes.

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

However, I am confounded by how to return a iterator that returns the nodes in random order without having to create a whole new queue with nodes attached in random order.

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

Further, what are the benefits of using such a data structure over an array, other than readability and ease of implementation?

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

This post is kind of long. I appreciate that you guys have taken the time to read my question and help me out. Thanks!

这个帖子有点长。我很感激你们花时间阅读我的问题并帮助我。谢谢！

采纳答案by Jim Mischel

In your array implementation, your Query 1.1seems to be the best way to do things. The only other way to remove a random element would be to move everything up to fill its spot. So if you had [1,2,3,4,5]and you removed 2, your code would move items 3, 4, and 5 up and you'd decrease the count. That will take, on average n/2 item moves for every removal. So removal is O(n). Bad.

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

If you won't be adding and removing items while iterating, then just use a Fisher-Yates shuffle on the existing array, and start returning items from front to back. There's no reason to make a copy. It really depends on your usage pattern. If you envision adding and removing items from the queue while you're iterating, then things get wonky if you don't make a copy.

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

With the linked list approach, the random dequeue operation is difficult to implement efficiently because in order to get to a random item, you have to traverse the list from the front. So if you have 100 items in the queue and you want to remove the 85th item, you'll have to start at the front and follow 85 links before you get to the one you want to remove. Since you're using a double-linked list, you could potentially cut that time in half by counting backwards from the end when the item to be removed is beyond the halfway point, but it's still horribly inefficient when the number of items in your queue is large. Imagine removing the 500,000th item from a queue of one million items.

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

For the random iterator, you can shuffle the linked list in-place before you start iterating. That takes O(n log n) time, but just O(1) extra space. Again, you have the problem of iterating at the same time you're adding or removing. If you want that ability, then you need to make a copy.

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

回答by arenard

For your Query 1.1: Here you can indeed remove a random element in constant time. The idea is simply as follows:

对于您的查询 1.1：在这里您确实可以在恒定时间内删除随机元素。思路简单如下：

• pick a random element to return
• swap it with the last element in your queue
• delete the last element in your queue

• 选择一个随机元素返回
• 将它与队列中的最后一个元素交换
• 删除队列中的最后一个元素

This way you keep having a continuous array without 'holes'

这样你就可以拥有一个没有“洞”的连续数组

回答by matharumanpreet00

You don't need to shuffle the whole copy of array when you create the iterator, but lazily Fisher-Yate shuffle each element while accessing it in the next()method

创建迭代器时不需要对整个数组副本进行混洗，但在next()方法中访问每个元素时，Fisher-Yate 会懒惰地混洗每个元素

回答by PlsWork

Use the array implementation (must be dynamic/resizable) in order to achieve constant (amortized) worst case runtime for all operations except for building the iterator (this takes linear time because of the shuffle).

使用数组实现（必须是动态的/可调整大小的），以便为除构建迭代器之外的所有操作实现恒定（摊销）最坏情况运行时间（由于 shuffle，这需要线性时间）。

Here is my implementation:

这是我的实现：

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

/* http://coursera.cs.princeton.edu/algs4/assignments/queues.html
 * 
 * A randomized queue is similar to a stack or queue, except that the item
 * removed is chosen uniformly at random from items in the data structure. 
 */
public class RandomizedQueue<T> implements Iterable<T> {

    private int queueEnd = 0;   /* index of the end in the queue,
                                   also the number of elements in the queue. */

    @SuppressWarnings("unchecked")
    private T[] queue = (T[]) new Object[1];    // array representing the queue

    private Random rGen = new Random();     // used for generating uniformly random numbers

    /**
     * Changes the queue size to the specified size.
     * @param newSize the new queue size.
     */
    private void resize(int newSize) {
        System.out.println("Resizing from " + queue.length + " to " + newSize);
        T[] newArray = Arrays.copyOfRange(queue, 0, newSize);
        queue = newArray;
    }


    public boolean isEmpty() {
        return queueEnd == 0;
    }

    public int size() {
        return queueEnd;
    }

    /**
     * Adds an element to the queue.
     * @param elem the new queue entry.
     */
    public void enqueue(T elem) {
        if (elem == null)
            throw new NullPointerException();

        if (queueEnd == queue.length) 
            resize(queue.length*2);

        queue[queueEnd++] = elem;
    }

    /**
     * Works in constant (amortized) time.
     * @return uniformly random entry from the queue.
     */
    public T dequeue() {    
        if (queueEnd == 0)  // can't remove element from empty queue
            throw new UnsupportedOperationException();

        if (queueEnd <= queue.length/4)     // adjusts the array size if less than a quarter of it is used
            resize(queue.length/2);

        int index = rGen.nextInt(queueEnd);     // selects a random index

        T returnValue = queue[index];   /* saves the element behind the randomly selected index 
                                            which will be returned later */

        queue[index] = queue[--queueEnd];   /* fills the hole (randomly selected index is being deleted) 
                                               with the last element in the queue */
        queue[queueEnd] = null;         // avoids loitering

        return returnValue;
    }

    /**
     * Returns the value of a random element in the queue, doesn't modify the queue.
     * @return random entry of the queue.
     */
    public T sample() {
        int index = rGen.nextInt(queueEnd);     // selects a random index
        return queue[index];
    }

    /*
     * Every iteration will (should) return entries in a different order.
     */
    private class RanQueueIterator implements Iterator<T> {

        private T[] shuffledArray;

        private int current = 0;

        public RanQueueIterator() {
            shuffledArray = queue.clone();
            shuffle(shuffledArray);
        }

        @Override
        public boolean hasNext() {
            return current < queue.length;
        }

        @Override
        public T next() {
            if (!hasNext())
                throw new NoSuchElementException();

            return shuffledArray[current++];
        }


        /**
         * Rearranges an array of objects in uniformly random order
         * (under the assumption that {@code Math.random()} generates independent
         * and uniformly distributed numbers between 0 and 1).
         * @param array the array to be shuffled
         */
        public void shuffle(T[] array) {
            int n = array.length;
            for (int i = 0; i < n; i++) {
                // choose index uniformly in [i, n-1]
                int r = i + (int) (Math.random() * (n - i));
                T swap = array[r];
                array[r] = array[i];
                array[i] = swap;
            }
        }

    }

    @Override
    public Iterator<T> iterator() {
        return new RanQueueIterator();
    }

    public static void main(String[] args) {
        RandomizedQueue<Integer> test = new RandomizedQueue<>();

        // adding 10 elements
        for (int i = 0; i < 10; i++) {
            test.enqueue(i);
            System.out.println("Added element: " + i);
            System.out.println("Current number of elements in queue: " + test.size() + "\n");

        }


        System.out.print("\nIterator test:\n[");
        for (Integer elem: test)
            System.out.print(elem + " ");
        System.out.println("]\n");

        // removing 10 elements
        for (int i = 0; i < 10; i++) {
            System.out.println("Removed element: " + test.dequeue());
            System.out.println("Current number of elements in queue: " + test.size() + "\n");
        }       

    }   
}

Note: my implementation is based on the following assignment: http://coursera.cs.princeton.edu/algs4/assignments/queues.html

注意：我的实现基于以下作业：http: //coursera.cs.princeton.edu/algs4/assignments/queues.html

Bonus challenge: try implementing a toString() method.

额外挑战：尝试实现一个 toString() 方法。