代码之家 › 专栏 › 技术社区 › mainstringargs

把这个算法设计得更好?

ipc algorithm java

mainstringargs · 技术社区 · 14 年前

我正在做一个更复杂的版本(车辆在x和y方向上移动)

我做这个例子是为了找到更好的方法来实现这个目标。

我有一辆车以24.5872mps的速度在x方向行驶
我用一个执行器每100毫秒递增一次x值来模拟这个过程(以保持它的x位置更加精确和实时)
在每一秒之后,我用刚刚覆盖的行的xmin和xmax值向另一个进程发送一条消息
另一个进程将用一条jms消息(通常是立即)响应,告诉我如果前一个x区域中存在“pottole”(消息回调消息到linkedblockingqueue),就停止。

我遇到的问题是“通常是瞬间”的部分。如果我得不到足够快的响应,我想这会使我的算法失去整个时间。处理这种情况的更好方法是什么?

以下是一些我正在尝试的基本代码:

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

    }

}

13 回复 | 直到 14 年前

Gladwin Burboz 14 年前

我建议对上面的算法进行修改,如下步骤所示。

对其他进程的jms调用

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

1b.另一个进程将响应一条jms消息,其中包含车辆位置可见区域中所有“坑洞位置”的列表。在客户端保留“可见的坑洞位置”列表,以便在下面的步骤中使用。

1c.我们将可视区域定义为车辆的相邻区域,这样即使使用jms调用其他进程(1秒延迟+网络延迟),车辆的移动也不应该穿过该区域。

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

车辆移动观察员

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

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

2c.如果找到匹配,宾果!你必须停车。

车辆移动

3A.注册步骤2A观察员观察车辆移动

3b.等到你得到了步骤1b中至少第一个可见的坑洞列表。

3c.通过每100 ms增加x值开始移动车辆。每次移动时,应通知步骤2a观察员。

下图图例:

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

user8599 14 年前

除非您在提供实时保证的网络和操作系统上运行系统,否则将偶尔会耽搁。所以你必须能够检测到这些延误,并决定如何回应-时间是否会停在你的模拟旁边,直到汽车发现地图是如何展开的?或者时间继续流动,但一个迟到的通知坑洞出现在道路上比它会有更多?或者是一个迟到的坑洞被发现得太晚而被忽略了?

我不太熟悉Java消息的当前状态。你能澄清一下 messageQueue.poll 阻塞了吗?如果您发送一条消息,然后阻塞一个答案,就会产生这样一个问题:为什么不使用诸如对远程对象的方法调用之类的同步方法,因为这肯定有助于基础结构毫不延迟地向您获取消息。

Thierry 14 年前

我将节省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();
...

Aurril Thorbjørn Ravn Andersen 14 年前

也许您不需要代码来实时运行,但只需模拟它并计算实时值?

fazo 14 年前

好吧,如果这是一个模拟,那么你不会知道前面有什么坑。到目前为止,我最好的选择是:

                // 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)

lorenzog 14 年前

正如你所说的,

我遇到的问题是“通常是瞬间”的部分。如果我得不到足够快的响应,我想这会使我的算法失去整个时间。处理这种情况的更好方法是什么?

在一个理想的世界里,你的计算机时钟是完美的,垃圾收集是原子的,即时的,在o(1)中,网络没有延迟,操作系统没有中断,墨菲是酣睡的。

既然你是在处理现实世界的情况,你就需要适应其中典型的不确定性。首先,你需要 统计学 . 当然,Java GC从不保证是实时的,但是您可以有一个相当好的近似90%的时间。剩下的10%可以由另一个“计划B”处理,以此类推。

换句话说:运行您的系统并尽可能地阻止它;收集使用情况统计信息;针对这些情况制定最佳解决方案。例如,

在模拟中插入随机延迟并查看其响应( 单元测试 !);也许您想每500毫秒运行一次run()方法?
使用观察者模式(如其他地方所建议的);
在run()方法中运行尽可能少的代码;可能每 1sec - epsilon 在哪里 ε 是一个足够小的间隔,用来解释足够大样本中方差最大的延迟
让两个独立的线程同时运行,使用锁使它们保持同步,平均它们的运行时间以获得更好的时钟

在紧要关头,没有精确的解决方案,因为没有精确的“真实”世界。加上噪音,做好更坏的准备,把剩下的平均化。

crowne 14 年前

在我看来,碰撞检测空间的粒度太小,无法可靠地依赖jms。

我会把这个换成 搬运工 接收可以在本地使用的合理映射块,例如,如果整个映射是100 x 100,则 搬运工 应至少接收10 x 10的网格部分。

网格的这一部分可以在每次移动时本地查询是否有坑,当位置接近10 x 10部分的边界时,可以请求下一个正方形。

这将给您一种双缓冲窗口,在这里可以加载新的方块,而剩余的移动将继续根据旧方块进行计算。

此外,您可能希望能够监听对方块的更改,以便当有人向先前加载的方块添加新的凹坑时,将广播该新方块,并且当前加载该方块的任何客户端都可以重新加载它。

祝你好运。

CiscoIPPhone 14 年前

当计算机B检测到坑洞时,让它发回坑洞的位置,然后计算机A可以将车辆移到这个位置。如果计算机A上的车辆撞到坑洞时不只是坐在那里,而是做了其他事情,那么本文可能会帮助您减少位置/方向/速度的突然变化: http://www.gamedev.net/reference/programming/features/cubicsplines/

电脑A:那台电脑发送它的位置
计算机B: 检查坑洞的计算机

Padmarag 14 年前

难道不能用 并发性 或者一些 先行阅读 技术?

我的意思是你的问题是等待消息队列。如果你能异步的话,会有帮助吗?或者使用回调?

您也许可以在调用进程B并继续进程A时保存状态。如果进程B答复某些错误,则停止并将状态还原为已保存的值。

Grembo 14 年前

你对离散事件模拟有很多经验吗?其概念是在日历上提前安排事件,在列表中跟踪这些事件发生的时间,并在到达任何给定事件时使用一组规则更新系统的状态。不必担心运行被调用的子例程所需的时间,您可以有效地在列表中安排未来。这有道理吗?如果你需要更多的信息/推荐信,请告诉我。

Finbarr 14 年前

可能使用观察者而不是消息传递来快速响应?

Mohd Farid 14 年前

我想应该做的最大的改变是--

去掉异步通信ie-jms,设置一些同步通信机制。

可能是rpc调用/webservice调用。

----更新---

刚刚看到您的评论,您不能删除作为一个更大的系统的一方的jms部分。

然后,我们将不得不接受,在jms消息未到达之前,我们无法做出决定。可能,在这种情况下几乎没有什么可以做的…

Community c0D3l0g1c 7 年前

在这里,用jms实现几乎即时的消息传递将是一件困难的事情。基本上,jms的设计重点是交付保证,而不是交付速度。

Here 以下是一些可能有助于加快jms交付速度的要点,但在jms世界中,只能保证交付而不能保证速度。

我不得不提到,您还应该考虑缓存解决方案。我得到了一个很好的 answer 对于这种类型的缓存,我的一个问题。……而且它是岩石!