Обработка дерева квадрантов в Erlang. Будет ли редактирование записи дерева квадрантов недействительным родителем?

Итак, этот вопрос является теоретическим, и мне в основном интересно, как этот сценарий обернется для нашего теоретического дерева квадрантов.

Само дерево представляет собой запись с объектами, границами и дочерними элементами. Дети, на данный момент, являются другими рекордами Quadtree. Таким образом, это будет большая структура в зависимости от того, сколько шпагатов будет сделано.

Если, скажем, я хочу удалить объект в поддереве уровня 3. Будет ли это правильно сохранять родителя и его родителя? Если бы я написал что-то вроде этого:

Quad#quad{objects = ListWithoutSaidObject}.

без фактического выполнения рекурсии таким образом, чтобы вызов функции сохранил результат приведенной выше строки в соответствующей дочерней переменной? Как это:

delete_object(Quad, ObjectToDelete) ->
    <nice code to find proper child if not present in current>
    Quad#quad{child = delete_object(Quad#quad.child, ObjectToDelete)}.

где delete_object возвращает то же дерево квадрантов без указанного объекта, если он был в этом дереве, в противном случае он продолжает копать, пока не найдет дерево, содержащее объект, который он должен удалить. При обнаружении он удаляет его и возвращает новое дочернее дерево.

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

Поскольку у меня пока нет кода, я не могу привести примеры. Я спрашиваю, чтобы знать, прежде чем реализовать это, каким образом я это сделаю.


recursion erlang quadtree
person Simon    schedule 08.05.2014    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

person Peer Stritzinger    schedule 08.05.2014
comment
Это то, что я понял. Прямо сейчас я делаю это в процессе, когда каждое дерево является процессом, и в записи перечислены pid для его дочерних элементов, если у него есть дочерние элементы. И создание функции более высокого порядка звучит как хорошая идея. Спасибо! :) - person Simon; 08.05.2014

arrow_upward
1
arrow_downward

В дополнение к ответу Пера Стритцингера:

Quadtrees вообще не очень подходят для удаления.

person AlexWien    schedule 07.07.2014