Эффективно удалять недопустимые ветки из иерархии, если они заданы в плоском массиве в PHP.

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

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

Это немного усложняется тем фактом, что корневых узлов также может быть несколько. Если у элемента нет parentID, это корневой узел.

Пример массива (дата-время и другая информация опущены):

Array
(
    [0] => MyObject
        (
            [id:protected] => 1
            [parentID:protected] => 2
        )

    [1] => MyObject
        (
            [id:protected] => 4
        )

    [2] => MyObject
        (
            [id:protected] => 2
            [parentID:protected] => 4
        )

    [3] => MyObject
        (
            [id:protected] => 3
        )

    [4] => MyObject
        (
        [id:protected] => 5
        [parentID:protected] => 3
    )
)

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

Спасибо


arrays php hierarchy
person Eebs    schedule 11.05.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

person goat    schedule 11.05.2012
comment
На самом деле мне не нужно дерево в конце, я хотел бы вернуть массив оставшихся элементов. Если эффективно сделать дерево для обрезки, это одно, но мне нужно сделать его массивом в конце. - person Eebs; 12.05.2012
comment
Он будет очень близок к оптимальному. Вам не нужно строить дерево, но ваш алгоритм построения дерева уже делает то, что необходимо сделать после удаления узлов с самоистекшим сроком действия - убедитесь, что оставшиеся узлы по-прежнему имеют путь к корневому узлу. Я предполагаю, что в объекте нет других данных, которые могли бы улучшить способность быстро находить предков, например, идентификатор предков всегда меньше идентификаторов его потомков или других вещей, которые можно было бы использовать для настройки алгоритма. - person goat; 12.05.2012