Расчет расстояния для большого количества устройств / узлов Часть 2

Этот вопрос является улучшением предыдущего вопроса SO.

Расчет расстояния для большого количества устройств / узлов

У меня есть N мобильных устройств / узлов (скажем, 100K), и я периодически получаю значения их местоположения (широта, долгота).

Некоторые из устройств «логически подключены» примерно к M другим устройствам (скажем, в среднем 10). Моя программа периодически сравнивает расстояние между каждым устройством и его логически подключенными устройствами и определяет, находится ли расстояние в пределах порогового значения (скажем, 100 метров).

Кроме того, количество логических соединений «K» также может быть больше одного и (скажем, 5 в среднем). Пример: A может быть соединен с B, C, например, для «родительской» логики. А также можно подключить к C, D, E, F для «рабочей» логики.

Мне нужен надежный алгоритм для расчета этих расстояний до логически связанных устройств.

Порядок сложности метода грубой силы будет N M K или (3 с точки зрения порядка)

Программа делает это каждые 3 секунды (все устройства мобильные), поэтому, например, 100K * 10 * 5 = 5M вычислений каждые 3 секунды не очень хорошо.

Какие-нибудь хорошие / классические алгоритмы для этой операции?


graph distance algorithm
person math_law    schedule 22.02.2014    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Я решил переписать свой ответ, немного подумав.

Сложность вашей проблемы не O (N ^ 3) в худшем случае, на самом деле только O (N ^ 2) в худшем случае. Это также не O (N * M * K), а скорее O (N * (M + K)), где O (M + K) - это O (N). Однако реальная сложность вашей проблемы - O (E), где E - общее количество логических подключений (количество рабочих подключений + количество родительских подключений). Если вы не хотите приближаться, ваше решение не может быть лучше, чем O (E). Ваши средние значения предполагают, что у вас, вероятно, порядка 5 миллионов соединений, что составляет порядка O (N log N).

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

При этом приведенный вами пример и предполагаемая временная сложность предполагают, что вас интересует не только то, находятся ли отдельные соединения в пределах порогового значения, но скорее, если наборы соединений находятся в пределах порогового значения. В частности, в вашем примере он вернет True, если родительская логика: (A, B), (A, C) и рабочая логика (A, C), (A, D), (A, E), (A, F) все верны. В этом случае лучшей структурой данных будет словарь словарей, который в Python выглядит следующим образом (включая оптимизацию ниже): «parentLogic [A] [B] = (последняя позиция A, последняя позиция B, была в пределах порогового значения)» .

Если часто позиции не сильно меняются, вы можете получить некоторое улучшение времени выполнения, сохранив предыдущие позиции и были ли они в пределах порогового значения (логическое значение). Преимущество заключается в том, что вы можете просто вернуть предыдущий результат, если две позиции не изменились, и обновить их, если они изменились.

person Nuclearman    schedule 23.02.2014
comment
Подход с трехмерной сферой выглядит многообещающим. Я думаю об одном: некоторые узлы неподвижны в течение последних 3 секунд. Тогда мне действительно не нужно сравнивать их, если их подключенное устройство также неподвижно. Можете ли вы придумать что-нибудь на основе последнего записанного местоположения по сравнению с текущим местоположением, чтобы отфильтровать некоторые сравнения? - person math_law; 25.02.2014
comment
Нет, не особо, подумал, что это немного поможет. И эта мысль заставила меня дважды проверить, что вы написали, и найти в вашем вопросе вероятную ошибку. В результате возникла необходимость переписать свой ответ. Нет абсолютно никакой необходимости рассматривать близлежащие связи, если только не требуется приблизительный ответ, а полученные вами средние значения заставляют меня думать, что это не так. - person Nuclearman; 25.02.2014
comment
Мне нужно узнать, что точки A, C или A, D находятся в некоторой близости. Нет необходимости иметь все логические связи, чтобы быть удовлетворенным. Когда A, C в порядке, я позволю пользователю, эй, A очень близко к C, сделать что-нибудь! - person math_law; 26.02.2014
comment
Однако не могу следовать за вашим первым абзацем. O (N2), как? O (E) ?? - person math_law; 26.02.2014
comment
Рассмотрим случай, когда логические соединения - это AB, AD, BC, BD. AD и BD близки, а AB и BC - нет. В конце концов, вы должны учитывать каждое соединение, даже если это нужно только для того, чтобы проверить, изменилось ли оно. Если есть E-соединения, то в худшем случае вы проверяете E-соединения, таким образом вы получаете O (E). Это верно, даже если вы остановитесь после того, как найдете близкое, потому что это может быть последнее соединение, которое вы проверяете. Если это все еще не ясно, добавьте пример с несколькими устройствами / узлами и их подключениями за несколько временных шагов к вашему вопросу и ожидаемым результатам / результатам, и я расширю свой ответ. - person Nuclearman; 27.02.2014
comment
Спасибо нуклеа. Я верю, что вашего подхода достаточно, и он даст мне понимание. Да благословит Бог ваши атомы. - person math_law; 01.03.2014

arrow_upward
0
arrow_downward

Вы можете использовать алгоритм грубой силы и отсортировать результат, а затем использовать лучшие лучшие группы.

person Gigamegs    schedule 22.02.2014
comment
Я сказал, что грубая сила здесь невозможна. Ищу эвристические / оптимизированные подходы. - person math_law; 22.02.2014
comment
В грубой силе вы можете ограничить рекурсию. - person Gigamegs; 22.02.2014
comment
А вы можете начать брутфорс в другом порядке. - person Gigamegs; 22.02.2014

arrow_upward
0
arrow_downward

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

Например, если порог равен 100 м, сохраните список подключенных устройств в пределах 200 м от каждого устройства и обновите его для каждого устройства, которое переместилось более чем на 50 м с момента последнего обновления.

person Anton    schedule 22.02.2014