Разработать этот алгоритм лучше?

Question

Я работаю над гораздо более сложной версией этого (с транспортным средством, движущимся в обоих направлениях X и Y)

Я сделал этот пример, чтобы получить идеи о лучших способах достижения этого.

1. У меня есть транспортное средство, движущееся в направлении X со скоростью (24,5872 м / с)
2. Я имитирую это, увеличивая значение X каждые 100 мс, используя исполнителя (чтобы сохранить его положение X более точным и в реальном времени)
3. Через каждую секунду я отправляю сообщение другому процессу со значениями xMin и xMax строки, которую я только что охватил
4. Другой процесс ответит сообщением JMS (обычно мгновенным), сообщающим мне, что нужно остановиться, если в предыдущей X-области была «дыра» (сообщение обратного вызова msg для связанной очереди блокировки).

У меня проблема с «обычно мгновенной» частью. Если я не получу ответ достаточно быстро, я думаю, что он потеряет все время моего алгоритма. Как лучше справиться с этой ситуацией?

Вот некоторый основной код того, что я пытаюсь сделать:

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

    }

}

Answer 1

Я предлагаю изменения в вашем алгоритме выше, как показано в шагах ниже.

JMS Вызов другого процесса

---

1a. Начните с отправки текущей позиции.

1b. Другой процесс ответит сообщением JMS, содержащим список всех «позиций ямок» в видимой области позиции вашего транспортного средства. Сохраните этот список «видимых положений ямок» на стороне клиента для использования в шагах ниже.

1c. Мы определяем видимую область как соседнюю область vehical, так что даже при (1-секундная задержка + сетевая задержка) вызова другого процесса с JMS движение vehical не должно пересекать эту область.

1d. Через каждую секунду повторяйте шаги 1a и 1b и заменяйте список позиций отверстий на стороне клиента относительно текущей позиции вашего транспортного средства.

.

Наблюдатель за подвижным движением

---

2a. Внедрите шаблон Observer, который может получать уведомления о движениях.

2b. Каждый раз, когда генерируется событие, наблюдатель проверяет, совпадает ли позиция vehical с одной из записей в списке видимых отверстий в горшке, полученных на шаге 1b.

2в. Если совпадение найдено, бинго! Вы должны остановить транспортное средство.

.

Автомобильное движение

---

3a. Зарегистрируйте наблюдателя step-2a для наблюдения за движениями автомобиля

3b. Подождите, пока вы не получите хотя бы первый список видимых отверстий в горшке с шага 1b.

3c. Начните движение vehical, увеличивая значение X каждые 100 мс. Каждый раз, когда он движется, он должен уведомить наблюдателя шага 2а.

.

Обозначения на диаграмме ниже:

---

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              |
+---------------------------------------------+

Answer 2

Если вы не используете систему в сетях и операционных системах, которые предоставляют гарантии в режиме реального времени, будет иногда с задержками. Таким образом, вы должны быть в состоянии обнаружить эти задержки и решить, как реагировать - останавливается ли время для вашей стороны симуляции, пока автомобиль не узнает, как карта разворачивается под ним? или время продолжает течь, но выброшенная в последнее время выбоина поворачивает дальше по дороге, чем это было бы? или опоздавшая выбоина была обнаружена как опоздавшая и проигнорированная?

Я не слишком знаком с текущим состоянием обмена сообщениями Java. Можете ли вы уточнить, если messageQueue.poll блокирует? Если вы отправляете сообщение, а затем блокируете ответ, возникает вопрос, почему вы не используете что-то синхронное, например, вызов метода для удаленного объекта, поскольку это определенно поможет инфраструктуре в получении сообщений без задержек.

Answer 3

Я бы сэкономил время вычисления currX вместе с позицией (currX)

В следующий раз, когда вы вычислите currX, вы посмотрите, сколько миллисекунд прошло с последнего раза (System.currMillisec () - lastCalc), умножьте это на скорость и добавьте это к currX. Затем установите последнюю дату расчета на сейчас.

редактировать: - будьте осторожны с вашим подразделением (постоянное имя: MPS, комментарий: mph)

добавить это к объявлению:

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

и метод запуска run:

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

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

Answer 4

Размер зерна в области обнаружения столкновений мне кажется слишком маленьким, чтобы надежно зависеть от JMS.

Я бы изменил это так, чтобы Mover получил разумный кусок карты, который он может использовать локально, например, если вся карта имеет размер 100 x 100, то Mover должен получить как минимум 10 x 10 частей сетки.

Эта часть сетки может быть опрошена локально для выбоин при каждом движении, и когда местоположение приближается к границе части 10 × 10, тогда может быть запрошен следующий квадрат.

Это даст вам своего рода окно с двойным буфером, где новый квадрат может быть загружен, в то время как оставшиеся ходы продолжают сравниваться со старым квадратом.

Кроме того, вы можете захотеть иметь возможность прослушивать изменения в квадратах, так что, когда кто-то добавляет новую выбоину в ранее загруженный квадрат, тогда этот новый квадрат будет транслироваться, и любые клиенты, имеющие этот квадрат в настоящее время загружен может перезагрузить его.

Удачи.

Answer 5

Как вы говорите,

У меня проблема с «обычно мгновенной» частью. Если я не получу ответ достаточно быстро, я думаю, что он потеряет все время моего алгоритма. Как лучше справиться с этой ситуацией?

В идеальном мире часы вашего компьютера идеальны, сборка мусора является атомарной, мгновенной, а в O (1) сети не имеют задержек, ОС не имеет прерываний, а Мерфи спит.

Так как вы имеете дело с реальной ситуацией, вам необходимо приспособиться к типичной для нее неопределенности. Для начала вам нужно статистика . Конечно, Java GC никогда не гарантируется в режиме реального времени, но вы можете иметь довольно хорошее приближение, которое работает в 90% случаев. Оставшиеся 10% могут быть обработаны другим «планом B» и так далее.

Другими словами: запустите вашу систему и постарайтесь как можно больше мешать ей; собирать статистику использования; работать на лучшие обходные пути для этих обстоятельств. Например,

• вставьте случайные задержки в симуляцию вашей симуляции и посмотрите, как она отреагирует ( модульный тест !); возможно, вы хотите запускать метод run () каждые 500 мс?
• использовать шаблон наблюдателя (как предложено в другом месте);
• иметь как можно меньше кода, запускаемого в методе run (); возможно, запускайте его каждые 1sec - epsilon, где epsilon - достаточно маленький интервал, который учитывает задержку с наибольшей дисперсией в достаточно большой выборке
• одновременно работают два отдельных потока, синхронизируйте их, используя блокировку, усредните их время выполнения, чтобы получить лучшие часы

В крайнем случае, нет точного решения, поскольку нет точного «реального» мира. Добавьте шум, будьте готовы к худшему, усредните все остальное.

Answer 6

ну, если это симуляция, то вы не узнаете заранее ни одной пробоины. Моя лучшая ставка на данный момент - это двигаться:

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

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

после или до этого:

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

и изменить аргумент в опросе с 1000 на 1 (или 0, если это означает, что опрос не будет ждать, но немедленно завершится)

Answer 7

Может быть, вам не нужен код для запуска в реальном времени, а просто имитировать его и вычислять значения в реальном времени?

Answer 8

Достижение почти мгновенной доставки сообщений с JMS будет непростым делом. По сути, JMS был разработан с большим вниманием к гарантии доставки, чем к скорости доставки.

Здесь - это некоторые моменты, которые могут помочь вам ускорить доставку JMS, но в мире JMS можно гарантировать только доставку, а не скорость.

Не могу не упомянуть, что вы должны также рассмотреть решение для кэширования. Я получил хороший ответ для этого типа кеша на один из моих вопросов о SO. .... И это круто!

Answer 9

Я бы сказал, что самое большое изменение, которое должно быть сделано, -

Удалите асинхронную связь, т.е. JMS, и установите некоторый механизм синхронной связи.

Это может быть вызов RPC / WebService Call.

--- Update ---

Только что увидел ваш комментарий, что вы не можете удалить часть JMS, являющуюся участником гораздо большей системы.

Тогда нам придется признать, что мы не можем принять решение, пока сообщение JMS не поступило. Возможно, в этом сценарии мало что можно сделать ...

Answer 10

Возможно использовать Observer вместо передачи сообщений для быстрого ответа?