设计这个算法有更好的方法吗？

Question

我在处理一个更复杂的版本（包含车辆在X和Y方向上移动）

我制作了这个示例来获取更好的实现方法的想法。

1. 我有一辆车以速度 （24.5872 米/秒） 在X方向移动
2. 我通过每100毫秒增加X值来模拟此过程，使用执行器（以保持其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

    }

}

- mainstringargs

---

你使用JMS消息的原因是什么？ - Tim R

这是一个小优化代码的技巧：将 currX = incrementor * increment; 修改为 currX += increment; 并将其初始化为 currX = -increment; 只需改变一个符号，你就能提高代码的运行速度。 - Justin Peel

@Justin 我怀疑如果它正在进行IPC，那么任何想象中的加速都不会有明显的效果。重复的加法也会导致更大的误差累积。 - Pete Kirkham

两件事情：在您的模拟中一致性有多重要？即每次运行是否都必须在相同的位置上有坑洼，或者即使轨迹中没有坑洼，您的汽车有时会随机“停止”？此外，您的经验中延迟有多频繁？或者您是在过早地优化某个完成后将足够快速工作的东西？ - p.marino

我看过上面的算法（不是你的代码）。为了实现这个“通常瞬间”的部分，我彻底改变了算法（请参见我下面的解决方案）。 - Gladwin Burboz

Answer 1

我提议对您上述算法进行更改，如下所示的步骤。

JMS调用其他进程

1a. 从发送车辆的当前位置开始。

1b. 其他进程将响应一个JMS消息，其中包含可见区域内所有“坑洞位置”的列表。将此“可见坑洞位置”列表保留在客户端以供下面的步骤使用。

1c. 我们将可见区域定义为车辆的邻近区域，即使在使用JMS调用其他进程时（具有1秒延迟+网络延迟），车辆的移动也不应越过该区域。

1d. 每秒钟重复执行步骤1a和1b，并替换客户端侧相对于您的车辆的当前位置的坑洞位置列表。

。

车辆运动观察者

2a. 实现一个可以接收车辆运动通知的观察者模式。

2b. 每次事件生成时，观察者将检查车辆的位置是否与在步骤1b中获取的可见坑洞列表中的条目之一匹配。

2c. 如果找到匹配，那么你必须停止车辆。

。

车辆运动

3a. 注册步骤2a观察者以观察车辆的运动。

3b. 等待直到您至少从步骤1b中获得了第一个可见坑洞列表。

3c. 每100毫秒递增X值以开始移动车辆。每次移动时，它应该通知步骤2a观察者。

。

下面是以下图表的图例：

o - 地图上每个坑洞的实例 X - 移动的车辆 . - 车辆行驶的路径 圆圈-司机可见的区域

+---------------------------------------------+
|                                             |
|                    o                o       |
|    o                                        |
|                                             |
|                                             |
|                _.-''''`-._                  |
|    o         ,'           `.             o  |
|            ,'  o            `.              |
|           .'    .            `.             |
|           |      . .          |             |
|           |         .         |   o         |
|           |         X         |             |
|   o       \                o  /             |
|            \                 /              |
|             `.             ,'               |
|               `-._     _.-'                 |
|                   `''''                     |
|                                             |
|                  o                          |
|                                    o        |
|                                             |
|                                             |
|     o                        o              |
+---------------------------------------------+

- Gladwin Burboz

Answer 2

除非您在提供实时保证的网络和操作系统上运行系统，否则偶尔会出现延迟。因此，您必须能够检测这些延迟并决定如何响应-当汽车发现地图正在展开时，时间是否停止进入模拟器？还是时间继续流动，但晚通知的坑洞出现在道路更远的地方？或者晚到的坑洞被识别为晚到并被忽略？

我对Java消息传递的当前状态不太熟悉。您能否澄清一下messageQueue.poll是否阻塞？如果您正在发送消息并阻塞等待答案，则引发了一个问题，即为什么不使用像调用远程对象的方法调用这样的同步方法，因为这肯定有助于基础架构无延迟地将消息传递给您。

- user8599

---

轮询正在阻塞...这些要求不是我的，而是给我的。 - mainstringargs

即使Donal建议阻塞，您仍然可以继续处理。 - Christopher Oezbek

Answer 3

我将节省currX计算的时间以及位置（currX）。

下一次计算currX时，您需要查看自上次计算以来经过了多少毫秒（System.currMillisec() - lastCalc），将其乘以速度并加到currX中。然后将计算的最后日期设置为现在。

编辑： - 注意单位（常量名称：MPS，注释：mph）

将其添加到声明中：

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

并且开始运行方法：

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

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

- Thierry

Answer 4

嗯，如果这是一个模拟，那么你不会提前知道任何坑洼。

到目前为止，我最好的选择是移动：

                // 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 ..
            }

将poll中的参数从1000更改为1（如果这意味着poll不会等待，而是立即退出，则更改为0）

- fazo

---

只需使用messageQueue.poll()，如果没有消息等待，则立即返回。 - Christopher Oezbek

Answer 5

在我的看法中，碰撞检测空间的颗粒度似乎太小了，无法可靠地依赖JMS。

我会更改这个设计，使得Mover可以接收到一个合理大小的地图块，例如如果整个地图是100 x 100，那么Mover应该至少接收到一个10 x 10的网格部分。

这个网格部分可以在每次移动时本地查询坑洞，当位置接近10 x 10部分的边界时，就可以请求下一个方块。

这将给你一种双缓冲窗口的效果，新的方块可以在剩余的移动继续评估旧方块的同时加载。

此外，您可能希望能够监听方块的变化，这样当有人向先前已加载的方块添加新的坑洞时，新的方块将被广播，并且任何当前加载该方块的客户端都可以重新加载它。

祝好运。

- crowne

Answer 6

也许您不需要实时运行代码，而只需模拟并计算实时值？

- Aurril

---

嗯...实际上，这确实需要实时运行...我只是“模拟”的一部分...我们的要求是：计算机时间的1秒钟等同于时钟时间的1秒钟。 - mainstringargs

如果需要实时性，使用标准的JVM是不可能做到的。由于GC和操作系统可能没有实时性，JVM的时间无法预测。要保证实时性，您需要在实时操作系统上运行实时JVM，例如http://java.sun.com/javase/technologies/realtime/index.jsp。 - Chinmay Kanchi

只要您记录自上次模拟更新以来经过的时间，并始终按照该距离推进模拟，模拟就会实时运行。如果您花费一秒钟进行垃圾回收（GC实际上非常快，所以这不是真正的问题），那么下一个时间步长将会更大，并且会“赶上”实时。 - Martin

Answer 7

正如你所说，

我的问题在于“通常立即”的部分。如果我没有及时得到响应，我认为它会打乱整个算法的时间安排。有什么更好的方法来处理这种情况？

在理想的世界里，你的计算机时钟是完美的，垃圾回收是原子的、瞬间的和O(1)的，网络没有延迟，操作系统没有中断，Murphy睡得很香。

由于你正在处理现实世界的情况，你需要调整典型的不确定性。首先，你需要统计数据。Java GC肯定不能保证实时性，但你可以有一个相当好的近似值，可以工作90%的时间。剩下的10%可以通过另一个“计划B”来处理，以此类推。

换句话说：运行你的系统，并尽可能地阻碍它；收集使用统计数据；针对这些情况制定最佳解决方案。例如，

• 在模拟中插入随机延迟并查看其响应（单元测试！）；也许您想每500毫秒运行一次run()方法？
• 使用观察者模式（如其他地方建议的）；
• 尽可能少地在run()方法中运行代码；也许每1秒 - epsilon运行一次，其中epsilon是足够小的间隔，可以考虑到足够大的样本中最高方差的延迟
• 同时运行两个单独的线程，使用锁保持它们同步，平均它们的运行时间以获得更好的时钟

在紧急情况下，没有确切的解决方案，因为没有确切的“真实”世界。添加噪声，准备好最坏的情况，平均剩下的部分。

- lorenzog

Answer 8

我认为应该做出的最大改变是--

删除异步通信，即 JMS，并使用一些同步通信机制。

可以是 RPC 调用 / WebService 调用。

---更新---

刚看到您的评论，因为是一个更大系统的一部分，无法删除 JMS 部分。

那么我们就必须接受，在JMS消息到达之前，我们无法做出决策。可能，在这种情况下几乎不能做什么......

- Mohd Farid

Answer 9

在JMS中实现几乎即时的消息传递将是一项艰巨的任务。基本上，JMS的设计更注重传递保证而不是传递速度。

这里有一些可能帮助您加快JMS传递速度的要点，但在JMS世界中，人们只能保证传递而不能保证速度。

我不得不提到您还应该考虑缓存解决方案。我在SO上的一个问题中得到了一个很好的答案，适用于这种类型的缓存......它非常棒！

- Elister

Answer 10

当电脑B检测到坑洞时，将其位置发送回来，然后电脑A可以将车辆移动到该位置。如果电脑A上的车辆在撞击坑洞时除了静止不动之外还做了其他事情，那么也许这篇文章可以帮助您减少位置/方向/速度的突然变化： http://www.gamedev.net/reference/programming/features/cubicsplines/

• 电脑A：发送其位置的计算机
• 电脑B：检查坑洞的计算机

- CiscoIPPhone