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

Question

Вот пример макета:

    A
B       C

D
    G    F
E
            H
K       I
    J

Каждая буква представляет физическое устройство. В этом примере вы можете видеть, что A находится рядом с B и C. B находится рядом с A, D и, возможно, C.

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

device | siblings
-------+---------
A      | B,C
-------+---------
B      | A,D,C
-------+---------
D      | B,G,E

Таким образом, когда мне нужно найти устройства поблизости от D, я могу сделать:

SELECT siblings FROM devices WHERE device = 'D';

siblings = siblings.split(',')

for sibling in siblings:
    # do something with each sibling device

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

Есть предложения?

Answer 1

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

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

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

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

Надеюсь, это поможет!