数据结构 - 随机队列

Question

我目前正在研究普林斯顿算法第 I 部分的 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
}

这里的要点是实现出队操作和迭代器，因为出队移除并returns 一个随机元素并且迭代器以随机排序.

1.数组实现：

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

查询1.1：对于出队操作，我只是简单地select从数组的大小中随机取一个数字，return那个项目，然后将数组中的最后一项移动到 returned 项的位置。

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

// 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: 为了满足迭代器随机 returning 元素的要求，我创建了一个包含队列所有索引的新数组，然后洗牌具有 Knuth 洗牌操作的数组和 return 队列中那些特定索引处的元素。但是，这涉及创建一个等于队列长度的新数组。同样，我确定我错过了一种更有效的方法。

2。内部Class实现

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

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

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

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

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

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

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) 额外 space。同样，您会遇到在添加或删除的同时进行迭代的问题。如果你想要那个能力，那么你需要复制。

Answer 2

创建迭代器时不需要打乱数组的整个副本，但 Fisher-Yate 在 next() 方法

中访问每个元素时懒惰地打乱每个元素

Answer 3

使用数组实现（必须是 dynamic/resizable），以便为除构建迭代器之外的所有操作实现恒定（分摊）的最坏情况运行时间（由于混洗，这需要线性时间）。

这是我的实现：

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");
        }       

    }   
}

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

奖励挑战：尝试实现 toString() 方法。

Answer 4

对于你的查询1.1：在这里你确实可以在常数时间内删除一个随机元素。思路简单如下：

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

这样你就可以在没有 'holes'

的情况下保持连续数组

Answer 5

对于您的查询 1.1，保留随机队列顺序的意图是无意义的，因为您将其随机出队。

另外，我有点明白你真正想要的是，我能不能发明一个随机队列，它可以随机出队，也可以从头到尾出队（这就是你想要保留顺序的原因，对吧？ ).而这两个操作，比如说 dequeueRandom(), dequeue() 都有摊销常数时间。

很遗憾，这不能同时完成。

数据结构 - 随机队列

Data Structures - Randomized Queues

java

random

queue

data-structures