data-structures - algorithms - pseudocode linear search
¿Por qué necesitamos estructuras de datos Deque en el mundo real? (8)
- Una buena aplicación del deque es almacenar el historial de un navegador web. Las URL visitadas recientemente se agregan al frente del deque, y la URL en la parte posterior del deque se elimina después de un número especificado de inserciones en el frente.
- Otra aplicación común del deque es el almacenamiento de la lista de operaciones de deshacer de una aplicación de software.
- Un ejemplo en el que se puede usar un deque es el algoritmo de programación de trabajos de A-Steal. [5] Este algoritmo implementa la programación de tareas para varios procesadores. Se mantiene una deque separada con hilos para ejecutar para cada procesador. Para ejecutar el siguiente hilo, el procesador obtiene el primer elemento del deque (usando la operación deque "quitar el primer elemento"). Si el hilo actual se bifurca, se coloca de nuevo al frente del deque ("insertar elemento al frente") y se ejecuta un nuevo hilo. Cuando uno de los procesadores termina la ejecución de sus propios hilos (es decir, su deque está vacío), puede "robar" un hilo de otro procesador: obtiene el último elemento del deque de otro procesador ("eliminar el último elemento") y ejecuta eso. - Cortesía Wikipedia
¿Alguien puede darme un ejemplo de situación donde se necesita una estructura de datos Deque ?
Nota: no explique qué es una deque .
Al modelar cualquier tipo de línea de espera en el mundo real: las entidades (bits, personas, automóviles, palabras, partículas, lo que sea) llegan con una determinada frecuencia al final de la línea y reciben servicio a una frecuencia diferente al comienzo de la línea. Mientras espera, algunas entidades pueden decidir abandonar la línea ... etc. El punto es que necesita "acceso rápido" para insertar / eliminar en ambos extremos de la línea, de ahí una deque.
Hay un ejemplo de uso práctico al encadenar iteradores. Lo he usado para implementar un iterador extensible :
import java.util.Deque;
import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedDeque;
public class ExtendableIterator<T> implements Iterator<T> {
public Deque<Iterator<T>> its = new ConcurrentLinkedDeque<Iterator<T>>();
public ExtendableIterator() {
}
public ExtendableIterator(Iterator<T> it) {
this();
this.extend(it);
}
@Override
public boolean hasNext() {
// this is true since we never hold empty iterators
return !its.isEmpty() && its.peekLast().hasNext();
}
@Override
public T next() {
T next = its.peekFirst().next();
if (!its.peekFirst().hasNext()) {
its.removeFirst();
}
return next;
}
public void extend(Iterator<T> it) {
if (it.hasNext()) {
its.addLast(it);
}
}
}
Se puede implementar una "cola" utilizando una de las dos estructuras de datos
- lista enlazada: si trabaja exclusivamente en los extremos y no le preocupa la sobrecarga de la asignación de memoria (o tiene limitaciones en cuanto a cómo se puede asignar la memoria), esto tiene sentido.
- Deque: si trabaja en los extremos, también se requiere acceso posicional (o la capacidad de iterar elementos en la cola rápidamente) y la sobrecarga de asignación de memoria es importante (pero no limitada), luego deque ofrece lo mejor de ambos (asignación similar a vector) con la lista vinculada como funcionalidad - bueno, al final de todos modos, insertar en el medio es más caro)
Normalmente, un deque es útil para la cola de prioridad, el escaneo de la cola es significativamente más rápido con una lista deque que enlazada.
Un deque puede modelar una estación de tren donde los automóviles pueden entrar y salir en el lado izquierdo o derecho de una línea, pero solo los autos en los extremos pueden entrar y salir. Esto se debe a que los autos en el interior no pueden golpear a los autos en el exterior para salir, por lo que solo tienen que esperar.
Una Deque es una cola de doble finalización que permite insertar y eliminar de ambos extremos.
En un escenario real, podemos adjuntarlo a una línea de compra de tickets, funciona como una cola, pero a veces sucede que un cuerpo ha comprado el boleto y de repente vuelven a preguntar algo en la parte delantera de la cola. En este escenario, porque ya compraron el ticket, por lo que tienen el privilegio de solicitar más consultas. Entonces, en este tipo de escenario, necesitamos una estructura de datos donde, de acuerdo con los requisitos, agreguemos datos del frente. Y en el mismo escenario, el usuario también puede dejar la cola desde atrás.
Entonces sigue completamente la estructura de datos de Deque.
http://en.wikipedia.org/wiki/Deque dice que hay algoritmos de programación de trabajos que usan deques. La página wikipedia alemana (http://de.wikipedia.org/wiki/Deque) menciona algoritmos de coincidencia de patrones y la implementación de máquinas de estado finito no deterministas como casos de uso para deques.
Un ejemplo en el que se puede utilizar un deque es el algoritmo de programación de trabajos de A-Steal. Este algoritmo implementa la programación de tareas para varios procesadores. Se mantiene una deque separada con hilos para ejecutar para cada procesador. Para ejecutar el siguiente hilo, el procesador obtiene el primer elemento del deque (usando la operación deque "quitar el primer elemento"). Si el hilo actual se bifurca, se coloca de nuevo al frente del deque ("insertar elemento al frente") y se ejecuta un nuevo hilo. Cuando uno de los procesadores termina la ejecución de sus propios hilos (es decir, su deque está vacío), puede "robar" un hilo de otro procesador: obtiene el último elemento del deque de otro procesador ("eliminar el último elemento") y ejecuta eso.
En el reciente libro CLR via C #, Richter describe las mejoras realizadas en ThreadPool en .Net 4.0. Definitivamente vale la pena leerlo, especialmente sobre el robo de trabajo. El algoritmo descrito por Richter es muy similar al ejemplo de Wikipedia, así que sospecho que Deque también se usa allí.