listas - pilas con nodos en java

Estructuras de datos-colas aleatorizadas

Question

Actualmente estoy trabajando en la Parte I de Algoritmos de Princeton. Una de las tareas es implementar una cola aleatoria. Esta es una pregunta sobre la implementación y las compensaciones del uso de diferentes estructuras de datos.

Pregunta:

Una cola aleatoria es similar a una pila o cola, excepto que el elemento eliminado se elige de manera uniforme al azar de los elementos en la estructura de datos. Cree un tipo de datos genérico RandomizedQueue que implemente la siguiente API:

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
}

El problema aquí es implementar la operación de salida de cola y el iterador ya que la salida de cola elimina y devuelve un elemento aleatorio y el iterador itera sobre la cola en un orden aleatorio .

1. Implementación de la matriz:

La implementación primaria que estaba considerando es una implementación de matriz. Esto será idéntico a la implementación de una cola de matriz, excepto la aleatoriedad.

Consulta 1.1: Para la operación de salida de cola, simplemente selecciono un número al azar del tamaño de la matriz y devuelvo ese elemento, y luego muevo el último elemento de la matriz a la posición del elemento devuelto.

Sin embargo, este enfoque cambia el orden de la cola. En este caso no importa ya que estoy en cola en orden aleatorio. Sin embargo, me preguntaba si había una forma eficiente en tiempo / memoria para poner en cola un elemento aleatorio de la matriz al tiempo que se conservaba el orden de la cola sin tener que crear una nueva matriz y transferirle todos los datos.

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

Consulta 1.2: Para que el iterador cumpla con el requisito de devolver elementos al azar, creo una nueva matriz con todos los índices de la cola, luego la mezclo con una operación aleatoria Knuth y devuelvo los elementos en esos índices particulares en la cola. Sin embargo, esto implica crear una nueva matriz igual a la longitud de la cola. De nuevo, estoy seguro de que me falta un método más eficiente.

2. Implementación de la clase interna

La segunda implementación involucra una clase de nodo interno.

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

Consulta 2.1. En este caso, entiendo cómo realizar la operación de salida de manera eficiente: devuelva un nodo aleatorio y cambie las referencias para los nodos adyacentes.

Sin embargo, estoy confundido por cómo devolver un iterador que devuelve los nodos en orden aleatorio sin tener que crear una cola completamente nueva con nodos adjuntos en orden aleatorio.

Además, ¿cuáles son los beneficios de usar dicha estructura de datos en una matriz, aparte de la legibilidad y la facilidad de implementación?

Este post es un poco largo. Aprecio que ustedes se hayan tomado el tiempo de leer mi pregunta y ayudarme. ¡Gracias!

Answer 1

En su implementación de matriz, su Consulta 1.1 parece ser la mejor manera de hacer las cosas. La única otra forma de eliminar un elemento aleatorio sería mover todo hacia arriba para llenar su lugar. Entonces, si tenía [1,2,3,4,5] y eliminó 2 , su código movería los ítems 3, 4 y 5 hacia arriba y disminuiría el conteo. Eso tomará, en promedio, n / 2 movimientos de elementos por cada eliminación. Así que la eliminación es O (n). Malo.

Si no va a agregar y eliminar elementos mientras está iterando, simplemente use un shuffle de Fisher-Yates en la matriz existente y comience a devolver los elementos de adelante hacia atrás. No hay razón para hacer una copia. Realmente depende de su patrón de uso. Si visualiza agregar y eliminar elementos de la cola mientras está iterando, entonces las cosas se complican si no hace una copia.

Con el enfoque de lista enlazada, la operación de salida aleatoria es difícil de implementar de manera eficiente porque para llegar a un elemento aleatorio, debe atravesar la lista desde el frente. Por lo tanto, si tiene 100 elementos en la cola y desea eliminar el elemento número 85, deberá comenzar desde el principio y seguir 85 enlaces antes de llegar al que desea eliminar. Ya que está utilizando una lista de doble enlace, podría reducir ese tiempo a la mitad contando hacia atrás desde el final cuando el elemento que se va a eliminar está más allá del punto medio, pero aún así es terriblemente ineficiente cuando el número de elementos en su cola es largo. Imagínese eliminando el artículo 500,000 de una cola de un millón de artículos.

Para el iterador aleatorio, puede barajar la lista enlazada en el lugar antes de comenzar la iteración. Eso toma tiempo O (n log n), pero solo O (1) espacio adicional. De nuevo, tiene el problema de iterar al mismo tiempo que agrega o elimina. Si quieres esa habilidad, entonces necesitas hacer una copia.

Answer 2

No necesita barajar la copia completa de la matriz cuando crea el iterador, pero Fisher-Yate mezcla cada elemento al acceder next() método next()

Answer 3

Para su consulta 1.1: Aquí puede eliminar un elemento aleatorio en tiempo constante. La idea es simplemente la siguiente:

• elige un elemento aleatorio para volver
• intercambia con el último elemento en tu cola
• borra el último elemento de tu cola

De esta manera sigues teniendo una matriz continua sin ''agujeros''

Answer 4

Use la implementación de la matriz (debe ser dinámica / redimensionable) para lograr un tiempo de ejecución constante (amortizado) en el peor de los casos para todas las operaciones, excepto para la construcción del iterador (esto toma un tiempo lineal debido a la confusión).

Aquí está mi implementación:

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

    }   
}

Nota: mi implementación se basa en la siguiente asignación: http://coursera.cs.princeton.edu/algs4/assignments/queues.html

Desafío de bonificación: intente implementar un método toString ().