ACTUALIZACIÓN: Aquí está my implementation of Hashed Timing Wheels. Por favor, avíseme si tiene una idea para mejorar el rendimiento y la concurrencia. (20-ene-2009)¿Una cola de prioridad que permite una actualización de prioridad eficiente?
// 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: He resuelto este problema mediante el uso de Hierarchical and Hashed Timing Wheels. (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 ocurrirá, 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 he aprendido 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 puede ser Esto se logra 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 y iterar todas las tareas cada segundo más o menos, pero no es tan hermoso.
¿Por qué una actualización O (LogN) sería demasiado lenta? – ConcernedOfTunbridgeWells
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
No pude entender claramente su problema. ¿Puedes reformular? – user51568