距离计算设备的数量庞大的/节点第2部分 [英] Distance Calculation for massive number of devices/nodes Part 2

问题描述

这个问题是一个增强previous SO问题。

This question is an enhancement to the previous SO question.

<一个href="http://stackoverflow.com/questions/21803392/distance-calculation-for-massive-number-of-devices-nodes">Distance计算设备的数量庞大的/节点

我有N个移动设备/节点（比如100K），我定期地获得自己的位置（纬度，经度）值。

I have N mobile devices/nodes (say 100K) and I periodically obtain their location ( latitude , longtitude ) values.

一些装置被逻辑连接到大致M之外的设备（例如10平均）。我的程序周期性地比较的距离的每个设备和其在逻辑上连接的设备之间，并确定如果该距离在阈值内（例如100米）。

Some of the devices are "logically connected" to roughly M other devices (say 10 in average). My program periodically compares the distance between the each device and its logically connected devices and determines if the distance is within a threshold (say 100 meters).

另外的逻辑连接的数目K也可以是更多然后（在平均比如说5）之一，并 例子是一个可以连接到B，C为即父母的逻辑。一个也可以连接到C，D，E，F为工作的逻辑

Furthermore number of logical connections "K" can also be more then one and (say 5 in average) Example is A can be connected to B,C for i.e. "parents" logic. A can also be connected to C,D,E,F for "work" logic

我需要一个强大的算法来计算这些距离的逻辑连接的设备。

I need a robust algorithm to calculate these distances to the logically connected devices.

暴力破解方法的复杂性顺序是（在顺序方面Θ3）N * M * K或

The complexity order of brute force approach would be N*M*K or (Θ3 in terms of order)

该程序将执行每3秒（所有设备都是移动），因此，例如100K * 10 * 5 = 500万计算，每3秒是不好的。

The program does this every 3 seconds (all devices are mobile), thus for instance 100K*10*5 = 5M calculations every 3 seconds is not good.

任何好的/经典算法进行此项操作？

Any good/classical algorithms for this operation ?

推荐答案

我决定重写我的答案后，多一点想法。

I decided to rewrite my answer after a bit more thought.

的你的问题的复杂性不是O（N ^ 3）在最坏的情况下，它实际上是唯一的O（N ^ 2）在最坏的情况下。它也没有为O（N * M * K），而O（N *（M + K）），其中O（M + K）为O（N）。然而，你的问题的真正复杂度为O（E），其中E是逻辑连接（工作连接+母连接数）的总数。除非你想接近，你的解决方案不能高于O（E）更好。您的平均数建议你可能有500万连接的顺序，这是O（N日志N）的数量级上。

The complexity of your problem is not O(N^3) in the worst case, it is actually only O(N^2) in the worst case. It's also not O(N*M*K) but rather O(N*(M+K)), where O(M+K) is O(N). However, the real complexity of your problem is O(E) where E is the total number of logical connections (number of work connections + number of parent connections). Unless you want to approximate, your solution cannot be better than O(E). Your averages suggest that you likely have on the order of 5 million connections, which is on the order of O(N log N).

您例如采用两套逻辑连接。所以，你会简单地循环通过每一组，并检查逻辑连接的设备之间的距离在阈值内。

You example uses two sets of logical connections. So you would simply cycle through each set and check if distance between the devices of the logical connection is within the threshold.

话虽这么说，比如你给了，你的假定时间复杂度表明你有兴趣不仅仅是如果单独连接内的阈值，而如果套的连接都在门槛。具体而言，在你的榜样，它会返回true，如果父母逻辑：（甲，乙），（A，C）和工作逻辑（A，C），（A，D），（A，E），（A，F）都是真。在这种情况下，你最好的数据结构将是一个字典词典，看起来像在Python以下（包括下面的优化）： parentsLogic [A] [B] =（最后一个位置A，最后的位置B，是在阈值）。

That being said, the example you gave and your assumed time complexity suggests you are interested in more than just if the individual connections are within threshold, but rather if sets of connections are within threshold. Specifically, in your example it would return True if parents logic: (A,B), (A,C) and Work logic (A,C),(A,D),(A,E),(A,F) are all True. In which case your best data structure would be a dictionary of dictionaries that looks like the following in Python (includes the optimization below): "parentsLogic[A][B] = (last position A, last position B, was within threshold)".

和如果它是共同的立场不会发生大的变化，您可以通过存储previous立场得到了一些运行时改进，如果他们中的阈值进行判断（布尔）。这样做的好处是，你可以简单地返回previous结果如果这两个位置都没有改变，如果他们改变了更新它们。

If it's common that the positions don't change much, you may obtain some run-time improvement by storing the previous positions and if they were within the threshold or not (Boolean). The benefit is that you can simply return the previous result if the two positions haven't changed and updating them if they have changed.

这篇关于距离计算设备的数量庞大的/节点第2部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！