2010-03-02 10 views
10

Estoy trabajando en una versión mucho más compleja de esto (con el vehículo moviéndose en ambas direcciones X e Y)¿Diseñando este algoritmo de una mejor manera?

Hice este ejemplo para obtener ideas sobre mejores formas de lograr esto.

  1. Tengo un vehículo en movimiento en la dirección X a una velocidad (24.5872 mps)
  2. Estoy simulando esta incrementando el valor de X cada 100 ms utilizando un ejecutor (para mantener su posición X más precisa y real tiempo)
  3. Después de cada segundo, envío un mensaje a otro proceso con los valores xMin y xMax de la línea que acabo de cubrir
  4. El otro proceso responderá con un mensaje JMS (generalmente al instante) indicándome que detenga si hay era un "Bache" en el área X anterior (mensaje de devolución de llamada a una secuencia de bloqueo vinculada).

El problema que tengo es con la parte "por lo general al instante". Si no obtengo una respuesta lo suficientemente rápido, creo que arrojará todo el tiempo de mi algoritmo. ¿Cuál es una mejor manera de manejar esta situación?

Aquí hay un código básico de lo que estoy tratando de hacer:

public class Mover implements MessageHandler { 

    private static final long CAR_UPDATE_RATE_IN_MS = 100; 
    private static double currX = 0; 
    private static double CONSTANT_SPEED_IN_MPS = 24.5872; // 55 mph 
    private static double increment = CONSTANT_SPEED_IN_MPS/(1000/CAR_UPDATE_RATE_IN_MS); 
    static LinkedBlockingQueue<BaseMessage> messageQueue = new LinkedBlockingQueue<BaseMessage>(); // ms 

    private static int incrementor = 0; 

    public static void main(String[] args) { 
     startMoverExecutor(); 
    } 

    private static void startMoverExecutor() { 

     ScheduledExecutorService mover = Executors.newSingleThreadScheduledExecutor(); 
     mover.scheduleAtFixedRate((new Runnable() { 

      @Override 
      public void run() { 
       currX = incrementor * increment; 

       if (incrementor % (1000/CAR_UPDATE_RATE_IN_MS) == 0) { 
        System.out.println(currX); 

        sendMessage(currX - CONSTANT_SPEED_IN_MPS, currX); 

        // do something 
        try { 
         messageQueue.poll(1000, TimeUnit.MILLISECONDS); 

        } catch (InterruptedException e) { 
         // TODO Auto-generated catch block 
         e.printStackTrace(); 
        } 

       } 
       incrementor++; 
      } 

     }), 0, CAR_UPDATE_RATE_IN_MS, TimeUnit.MILLISECONDS); 

    } 

    @Override 
    public void handleMessage(BaseMessage msg) { 
     messageQueue.add(msg); 

    } 

    protected static void sendMessage(double firstX, double secondX) { 
     // sendMessage here 

    } 

} 
+1

¿Hay algún motivo por el que esté utilizando un mensaje JMS? –

+0

Interprocess communication – systemoutprintln

+0

Aquí hay una pequeña aceleración en su código: cambie 'currX = incrementor * increment;' a 'currX + = increment;' y configure initialize currX como 'currX = -increment;' Simplemente cambiando a * a a + , pero ahí tienes. –

Respuesta

6

Propongo cambios a tu algoritmo arriba como se muestra en los pasos a continuación.

JMS llamada a otro proceso


1a. Comience enviando la posición actual de vehical.

1b. El otro proceso responderá con un mensaje JMS que contiene una lista de todas las "posiciones de orificios en el pozo" en el área visible de la posición de su vehículo. Mantenga esta lista de "posiciones visibles de los hoyos" en el lado del cliente para usar en los pasos a continuación.

1c. Definimos el área visible como el área vecina del vehículo de tal manera que incluso con (retraso de 1 segundo + demora de red) de llamar a otro proceso con JMS, el movimiento del vehículo no debe cruzar esta área.

1d. Después de cada segundo, repita los pasos 1a y 1b y reemplace la lista de posiciones de orificios en el lado del cliente en relación con la posición actual de su vehículo.

.

Vehical observador movimiento


2a. Implemente un patrón Observer que pueda recibir notificaciones de movimientos vehiculares.

2b. Cada vez que se genera un evento, el observador verificará si la posición del vehículo coincide con una de las entradas en la lista de agujeros visibles adquiridos en el paso 1b.

2c. Si se encuentra el partido, ¡bingo! Tienes que parar el vehical.

.

movimiento Vehical


3a. Registre el paso 2a observador para observar los movimientos del vehículo

3b. Espere hasta que haya obtenido al menos la primera lista de agujeros visibles desde el paso 1b.

3c. Comience a mover el vehículo incrementando el valor X cada 100 ms. Cada vez que se mueve, debe notificar al observador step-2a.

.

Leyendas para el diagrama siguiente:


 
o - Instance of each pot hole somewhere on map 
X - Moving vehical 
. - Path followed by vehical 
Circle - Visible area of the vehical driver 
+---------------------------------------------+ 
|            | 
|     o    o  | 
| o          | 
|            | 
|            | 
|    _.-''''`-._     | 
| o   ,'   `.    o | 
|   ,' o   `.    | 
|   .' .   `.    | 
|   |  . .   |    | 
|   |   .   | o   | 
|   |   X   |    | 
| o  \    o/   | 
|   \    /   | 
|    `.    ,'    | 
|    `-._  _.-'     | 
|     `''''      | 
|            | 
|     o       | 
|         o  | 
|            | 
|            | 
|  o      o    | 
+---------------------------------------------+ 
1

Tal vez usted no necesita el código para ejecutar en tiempo real, pero sólo simularlo y calcular los valores en tiempo real?

+0

Hmmm ... En realidad, esto necesita ejecutarse en tiempo real ... Solo soy parte de una "simulación" ... Nuestro requisito es: 1 segundo de tiempo de la computadora es 1 segundo de tiempo del reloj. – systemoutprintln

+5

Si necesita ser en tiempo real, esto no es posible usando la JVM estándar. El tiempo en la JVM no es predecible debido a gc y también porque el sistema operativo puede no ser en tiempo real. Debe estar ejecutando una JVM en tiempo real como http://java.sun.com/javase/technologies/realtime/index.jsp en un sistema operativo en tiempo real para garantizar esto. –

+0

Mientras mantenga un conteo de la cantidad de tiempo transcurrido desde la última actualización de simulación, y siempre progrese la simulación en esa distancia, la simulación será en tiempo real. Si pasas un segundo haciendo una recolección de basura (los GC son realmente muy rápidos, entonces no es realmente una preocupación) entonces el siguiente paso será un poco más grande y se pondrá al día con la encuesta – Martin

2

Me volvería a ahorrar el tiempo de la computación CMBM junto con la posición (CMBM)

La próxima vez que calcular el CMBM, miras la cantidad de milisegundos transcurrir desde la última vez (System.currMillisec() - lastCalc), multiplique eso por la velocidad y agréguelo a currX. Luego configure la última fecha de cálculo hasta ahora.

edición: - tener cuidado con su unidad (nombre de la constante: MPS, comentario: mph)

añadir que a la declaración:

private static long compDate = System.currentTimeMillis(); 
private static long lastNotifDate = System.currentTimeMillis(); 

y el inicio del método run:

currX += (System.currentTimeMillis() - compDate) * CONSTANT_SPEED_IN_MPS/1000; 
compDate = System.currentTimeMillis(); 

if (compDate - lastNotifDate > 1000) { 
    lastNotifDate = System.currentTimeMillis(); 
... 
3

A menos que esté ejecutando el sistema en redes y sistemas operativos que brinden garantías en tiempo real, será ocasionalmente hay retrasos. De modo que debe ser capaz de detectar esos retrasos y decidir cómo responder: ¿se detiene el tiempo de su lado de la simulación hasta que el automóvil descubra cómo se desenrolla el mapa debajo de él? o el tiempo continúa fluyendo, pero un bache notado tarde se encuentra más adelante en el camino de lo que lo hubiera hecho? ¿o se detecta un último bache que llega tarde y se ignora?

No estoy muy familiarizado con el estado actual de los mensajes de Java. ¿Puedes aclarar si messageQueue.poll está bloqueando? Si envía un mensaje y luego bloquea una respuesta, surge la pregunta de por qué no utiliza algo sincrónico como una llamada a un objeto remoto, ya que eso definitivamente ayudaría a la infraestructura a recibir mensajes sin demoras.

+0

en tiempo real está bloqueando ... Estos requisitos no son míos, sino que me son dados – systemoutprintln

+0

Aún puede continuar el procesamiento, incluso si el sondeo es de bloqueo es lo que Donal sugiere –

0

Haga que la computadora B envíe nuevamente la ubicación del bache cuando detecta uno, luego el equipo A puede mover el vehículo a esta posición.Si el vehículo en el equipo A hace algo más que simplemente sentarse allí cuando se ha dado en el bache entonces tal vez este artículo le ayudará a reducir un cambio repentino en la posición/dirección/velocidad: http://www.gamedev.net/reference/programming/features/cubicsplines/

  • equipo A: El equipo eso es enviar su posición
  • equipo B: El equipo que comprueba baches
0

¿no sería posible utilizar concurrencia o algún Lectura anticipada técnica?

Quiero decir que su problema está esperando en la messageQueue. Si pudieras sincronizarlo, ¿no sería de ayuda? Tal vez use la devolución de llamada?

Quizás pueda guardar el estado cuando se realiza una llamada al Proceso B y continuar el Proceso A. Si el Proceso B responde con algún error, entonces detenga y revierte el estado a valores guardados.

0

¿Tiene mucha experiencia con la simulación de eventos discretos? El concepto es que programe eventos con anticipación en un calendario, mantenga un registro del tiempo que esos eventos ocurren en una lista, y actualice el estado del sistema al llegar a cualquier evento con un conjunto de reglas. En lugar de preocuparse por el tiempo requerido para ejecutar una subrutina llamada, efectivamente planifica el futuro en una lista. ¿Esto tiene sentido? Avíseme si necesita más información/referencias.

0

¿Posiblemente use Observer en lugar de mensaje que pasa para una respuesta rápida?

+0

JMS es obligatorio ... Soy parte de un sistema más grande donde se usan los mensajes – systemoutprintln

1

bueno, si esto es una simulación, entonces no sabrá por delante de ningún bache. mi mejor apuesta hasta ahora es mover:

   // do something 
       try { 
        messageQueue.poll(1000, TimeUnit.MILLISECONDS); 

       } catch (InterruptedException e) { 
        // TODO Auto-generated catch block 
        e.printStackTrace(); 
       }' 

después o antes de esto:

  if (incrementor % (1000/CAR_UPDATE_RATE_IN_MS) == 0) { 
      .. code .. 
      } 

y el cambio argumento en encuesta de 1000 a 1 (o 0 si esto significa que la encuesta no va a esperar, pero dejar de fumar immidiately)

+0

+1 solo use messageQueue.poll() que devuelve inmediatamente si hay no hay mensaje esperando –

1

Como usted dice,

el problema que tengo es con la parte "por lo general al instante". Si no obtengo una respuesta lo suficientemente rápido, creo que arrojará todo el tiempo de mi algoritmo. ¿Cuál es una mejor manera de manejar esta situación?

En un mundo ideal, el reloj del equipo es perfecto, la recolección de basura es atómica, instantánea y en tiempo O (1), las redes tienen ningún retraso, el sistema operativo tiene ninguna interrupción y Murphy está profundamente dormido.

Dado que se trata de una situación del mundo real, debe ajustarse a la incertidumbre típica de la misma. En primer lugar, necesita estadísticas. Sin duda, nunca se garantiza que Java GC sea en tiempo real, pero puede tener una aproximación bastante buena que funcione el 90% del tiempo. El 10% restante puede ser manejado por otro 'plan B', y así sucesivamente.

En otras palabras: ejecute su sistema y trate de obstaculizarlo tanto como sea posible; recoger estadísticas de uso; trabajar en las mejores soluciones para esas circunstancias.Por ejemplo,

  • de inserción retardos aleatorios en la simulación de la simulación y ver cómo responde (prueba de unidad!); ¿Quizás quiera ejecutar el método run() cada 500 ms?
  • usa un patrón de observador (como se sugiere en otra parte);
  • tienen la menor cantidad de código posible en el método run(); tal vez ejecutarlo cada 1sec - epsilon, donde épsilon es un intervalo lo suficientemente pequeño que representa el retraso con la mayor varianza en una muestra lo suficientemente grande
  • tienen dos subprocesos separados se ejecutan simultáneamente, mantenerlos sincronizados mediante un bloqueo, promedian su funcionamiento es hora de obtener un mejor reloj

Por un momento, no hay una solución exacta ya que no existe un mundo "real" exacto. Agregue ruido, prepárese para lo peor, promedie el resto.

1

El tamaño de grano del espacio de detección de colisión me parece demasiado pequeño para depender de JMS de manera confiable.

Yo cambiaría esto para que Mover reciba una porción razonable del mapa que puede usar localmente, p. Ej. si el mapa completo es 100 x 100, entonces Mover debe recibir al menos una porción de 10 x 10 de la cuadrícula.

Esta parte de la cuadrícula se puede interrogar localmente en busca de baches en cada movimiento, y cuando la ubicación se acerca a un límite de la porción de 10 x 10, se puede solicitar el siguiente cuadrado.

Esto le dará una especie de ventana de doble buffer, donde el nuevo cuadrado se puede cargar mientras los movimientos restantes continúan evaluándose en el cuadro anterior.

Además, es posible que desee escuchar los cambios en los cuadrados, de modo que cuando alguien agrega un nuevo bache a un cuadrado que se haya cargado previamente, se transmita ese nuevo cuadrado y cualquier cliente que tenga ese el cuadrado actualmente cargado puede volver a cargarlo.

Buena suerte.

0

Yo diría que el cambio más importante que debe hacerse es -

Retire las comunicaciones asíncronas es decir, JMS y poner un poco mecanismo de comunicación sincrónico.

Podría ser una llamada RPC/Llamada a un servicio web.

--- Actualización ---

acaba de ver su comentario de que no se puede quitar la parte JMS ser parte de un sistema mucho más grande.

Luego, tendremos que aceptar que no podemos tomar una decisión hasta que el mensaje JMS no haya llegado. Probablemente, hay muy poco que se podría hacer en este escenario ...

0

Lograr una entrega casi instantánea de mensajes con JMS va a ser difícil aquí. Básicamente, JMS se diseñó con más enfoque en la garantía de entrega que la velocidad de entrega.

Here son algunos de los puntos que pueden ayudarlo a acelerar sus entregas JMS pero en el mundo JMS uno solo puede garantizar la entrega y no la velocidad.

No puedo evitar mencionar que también debe considerar una solución de almacenamiento en caché. Obtuve un buen answer para este tipo de caché para una de mis preguntas en SO. .... ¡Y es genial!