data-structures - prioridad - heap

¿Una cola de prioridad que permite una actualización de prioridad eficiente?

Question

ACTUALIZACIÓN : Aquí está mi implementación de Hashed Timing Wheels . Por favor, avíseme si tiene una idea para mejorar el rendimiento y la concurrencia. (20-ene-2009)

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

ACTUALIZACIÓN : resolví este problema mediante el uso de ruedas dentadas jerárquicas y hash . (19-ene-2009)

Estoy tratando de implementar un temporizador de propósito especial en Java que está optimizado para el manejo del tiempo de espera. Por ejemplo, un usuario puede registrar una tarea con una línea muerta y el temporizador podría notificar el método de devolución de llamada de un usuario cuando se acabe la línea muerta. En la mayoría de los casos, una tarea registrada se realizará en un período de tiempo muy corto, por lo que la mayoría de las tareas se cancelarán (por ejemplo, task.cancel ()) o reprogramadas para el futuro (por ejemplo, task.rescheduleToLater (1, TimeUnit.SECOND)) .

Quiero utilizar este temporizador para detectar una conexión de socket inactiva (por ejemplo, cerrar la conexión cuando no se recibe un mensaje en 10 segundos) y escribir tiempo de espera (por ejemplo, levantar una excepción cuando la operación de escritura no termina en 30 segundos). En la mayoría de los casos, el tiempo de espera no se producirá, el cliente enviará un mensaje y la respuesta se enviará a menos que haya un problema de red extraño.

No puedo usar java.util.Timer o java.util.concurrent.ScheduledThreadPoolExecutor porque suponen que se supone que la mayoría de las tareas han expirado. Si se cancela una tarea, la tarea cancelada se almacena en su pila interna hasta que se llame a ScheduledThreadPoolExecutor.purge (), y es una operación muy costosa. (O (NlogN) tal vez?)

En montones tradicionales o colas de prioridad que aprendí en mis clases de CS, la actualización de la prioridad de un elemento era una operación costosa (O (logN) en muchos casos porque solo se puede lograr eliminando el elemento y volviéndolo a insertar con un nuevo valor de prioridad. Algunos montones como el montón Fibonacci tienen O (1) tiempo de operación decreaseKey () y min (), pero lo que necesito al menos es fast increaseKey () y min () (o decreaseKey () y max ()) .

¿Conoces alguna estructura de datos que esté altamente optimizada para este caso de uso particular? Una estrategia en la que estoy pensando es simplemente almacenar todas las tareas en una tabla hash e iterar todas las tareas cada segundo, pero no es tan hermoso.

Answer 1

¿Hay alguna buena razón para no usar java.lang.PriorityQueue? ¿No elimina () maneja sus operaciones de cancelación en tiempo de registro (N)? Luego, implemente su propia espera en función del tiempo hasta el elemento en la parte frontal de la cola.

Answer 2

¿Qué hay de tratar de separar la entrega del caso normal donde las cosas se completan rápidamente desde los casos de error?

Use una tabla hash y una cola de prioridad. Cuando se inicia una tarea, se coloca en la tabla hash y, si finaliza rápidamente, se elimina en O (1) vez.

Cada segundo escanea la tabla hash y todas las tareas que llevan mucho tiempo, digamos .75 segundos, se mueven a la cola de prioridad. La cola de prioridad siempre debe ser pequeña y fácil de manejar. Esto supone que un segundo es mucho menos que los tiempos de espera que está buscando.

Si el escaneo de la tabla hash es demasiado lento, puede usar dos tablas hash, esencialmente una para los segundos pares y otra para los segundos impares. Cuando se inicia una tarea, se coloca en la tabla hash actual. Cada segundo mueve todas las tareas de la tabla hash no actual a la cola de prioridad y cambia las tablas hash para que la tabla hash actual esté ahora vacía y la tabla no actual contenga las tareas iniciadas hace uno o dos segundos.

Las opciones son mucho más complicadas que el simple uso de una cola de prioridad, pero se implementan con bastante facilidad y deben ser estables.

Answer 3

Alguna combinación de hashes y estructuras O (logN) debe hacer lo que usted solicite.

Estoy tentado a discutir con la forma en que estás analizando el problema. En tu comentario anterior, dices

Porque la actualización ocurrirá muy frecuentemente. Digamos que estamos enviando M mensajes por conexión, entonces el tiempo total se convierte en O (MNlogN), que es bastante grande. - Trustin Lee (hace 6 horas)

que es absolutamente correcto hasta donde llega. Pero la mayoría de las personas que conozco se concentrarán en el costo por mensaje , en la teoría de que a medida que su aplicación tenga más y más trabajo por hacer, obviamente requerirá más recursos.

Entonces, si su aplicación tiene mil millones de sockets abiertos simultáneamente (¿es eso realmente posible?), El costo de inserción es de solo 60 comparaciones por mensaje.

Apuesto a que esta es una optimización prematura: en realidad no ha medido los cuellos de botella en su sistema con una herramienta de análisis de rendimiento como CodeAnalyst o VTune.

De todos modos, es probable que exista un número infinito de formas de hacer lo que usted pide, una vez que decide que ninguna estructura hará lo que quiere, y quiere una combinación de las fortalezas y debilidades de los diferentes algoritmos.

Una posibilidad es dividir el dominio de socket N en un número de cubos de tamaño B, y luego hash cada socket en uno de esos cubos (N / B). En ese cubo hay un montón (o lo que sea) con el tiempo de actualización O (log B). Si un límite superior en N no se fija por adelantado, pero puede variar, entonces puede crear más segmentos de forma dinámica, lo que agrega una pequeña complicación, pero es ciertamente factible.

En el peor de los casos, el temporizador de vigilancia tiene que buscar las colas (N / B) para vencimientos, pero supongo que el temporizador de vigilancia no es necesario para matar las tomas inactivas en cualquier orden en particular. Es decir, si 10 sockets permanecieron inactivos en la última división de tiempo, no tiene que buscar primero ese dominio para el tiempo de espera, tratarlo, encontrar el que agotó el tiempo de espera, etc. Simplemente tiene que escanear el conjunto (N / B) de cubos y enumerar todos los tiempos muertos.

Si no está satisfecho con una matriz lineal de depósitos, puede usar una cola de colas de prioridad, pero desea evitar actualizar esa cola en cada mensaje, o bien está de vuelta donde comenzó. En su lugar, defina un tiempo que sea menor que el tiempo de espera real. (Digamos, 3/4 o 7/8 de eso) y usted solo pone la cola de bajo nivel en la cola de alto nivel si es el tiempo más largo que excede eso.

Y a riesgo de afirmar lo obvio, no desea que sus colas estén programadas para el tiempo transcurrido . Las claves deben ser hora de inicio . Para cada registro en las colas, el tiempo transcurrido debería actualizarse constantemente, pero la hora de inicio de cada registro no cambia.

Answer 4

Creo que almacenar todas las tareas en una lista y repetirlas sería lo mejor.

Debes (ejecutar) ejecutar el servidor en una máquina bastante robusta para llegar a los límites donde este costo será importante.

Answer 5

Hasta donde yo sé (escribí un artículo sobre una nueva cola de prioridad, que también revisó los resultados anteriores), ninguna implementación de cola de prioridad obtiene los límites de los montones de Fibonacci, así como la clave de aumento de tiempo constante.

Hay un pequeño problema para obtener eso literalmente. Si pudieras obtener la tecla aumentar en O (1), entonces podrías obtener eliminar en O (1) - simplemente aumenta la tecla a + infinito (puedes manejar la cola llena de muchos + infinitos usando algunos trucos de amortización estándar) ) Pero si find-min también es O (1), eso significa que delete-min = find-min + delete se convierte en O (1). Eso es imposible en una cola de prioridad basada en la comparación porque el límite ordenado implica (inserte todo, luego elimine uno por uno) que

n * insertar + n * borrar-min> n registrar n.

El punto aquí es que si quiere que una cola de prioridad admita la tecla aumentar en O (1), entonces debe aceptar una de las siguientes penalizaciones:

• No se basa en la comparación. En realidad, esta es una muy buena forma de evitar cosas, por ejemplo, árboles vEB .
• Acepte O (log n) para inserciones y también O (n log n) para make-heap (dado n valores iniciales). Esto apesta.
• Acepte O (log n) para find-min. Esto es completamente aceptable si en realidad nunca encuentra-min (sin una eliminación adjunta).

Pero, de nuevo, que yo sepa, nadie ha hecho la última opción. Siempre lo he visto como una oportunidad para obtener nuevos resultados en un área bastante básica de estructuras de datos.

Answer 6

Hay una manera muy simple de hacer todas las inserciones y elimina en O (1), aprovechando el hecho de que 1) la prioridad se basa en el tiempo y 2) es probable que tenga un número pequeño y fijo de tiempos de espera.

1. Cree una cola FIFO regular para contener todas las tareas que exceden el tiempo de espera en 10 segundos. Debido a que todas las tareas tienen duraciones de tiempo de espera idénticas, puede simplemente insertarlas hasta el final y eliminarlas desde el principio para mantener ordenada la cola.
2. Cree otra cola FIFO para tareas con una duración de tiempo de espera de 30 segundos. Crea más colas para otras duraciones de tiempo de espera.
3. Para cancelar, elimine el elemento de la cola. Esto es O (1) si la cola se implementa como una lista vinculada.
4. La reprogramación puede realizarse como cancel-insert, ya que ambas operaciones son O (1). Tenga en cuenta que las tareas pueden reprogramarse en diferentes colas.
5. Finalmente, para combinar todas las colas FIFO en una única cola de prioridad general, haga que el jefe de cada cola FIFO participe de forma regular. El jefe de este montón será la tarea con el tiempo de expiración más próximo de TODAS las tareas.

Si tiene m número de duraciones de tiempo de espera diferente, la complejidad de cada operación de la estructura general es O (log m). La inserción es O (log m) debido a la necesidad de buscar en qué cola insertar. Remove-min es O (log m) para restaurar el montón. La cancelación es O (1) pero el caso más desfavorable O (log m) si cancela el encabezado de una cola. Como m es un número pequeño y fijo, O (log m) es esencialmente O (1). No escala con el número de tareas.

Answer 7

Su escenario específico sugiere un búfer circular para mí. Si el máximo el tiempo de espera es de 30 segundos y queremos obtener tomas al menos cada décima de segundo, luego use un buffer de 300 listas doblemente enlazadas, una por cada décima de segundo en ese período. Para ''increaseTime'' en una entrada, elimínela de la lista y agréguela a la de su nuevo período de décimo segundo (ambas operaciones de tiempo constante). Cuando finaliza un período, coseche lo que quede en la lista actual (tal vez alimentándolo con un hilo de reaper) y avance el puntero de la lista actual.

Answer 8

Tiene un límite estricto para la cantidad de elementos en la cola; existe un límite para los sockets TCP.

Por lo tanto, el problema está limitado. Sospecho que cualquier estructura de datos inteligente será más lenta que el uso de tipos incorporados.

Answer 9

Utilice la rueda dentada Hashed Timing Wheel - Google ''Hashed Hierarchical Timing Wheels'' para obtener más información. Es una generalización de las respuestas hechas por la gente aquí. Prefiero una rueda de tiempo hash con un tamaño de rueda grande para las ruedas de distribución jerárquica.