Xpoint
   [напомнить пароль]

переформирование дерева

Метки: [без меток]
2005-04-06 13:01:33 [обр] Suvit[досье]
Есть дерево объектов. причем имеются не сами объекты а строки путей '/aaa/bbb', пользователь может видеть не все объекты дерева, т.е. есть функция, которая получает пользователя, а выдает список путей на разрешеные объекты,
требуется построить новое дерево по путям.
Вопрос1:как это можно быстро сделать(подскажите алгоритм)?
Вопрос2: если имеется какой то разрешенный путь, как быстро получить пути всех детей, т.е. детями в данном случае я называю следущее: исходный путь '/aaa', если '/aaa/bbb' запрешен, а '/aaa/bbb/ccc' и 'aaa/bbb/ccc/ddd' разрешены, то '/aaa/bbb/ccc' сын для '/aaa', но '/aaa/bbb/ccc/ddd' уже нет(не сын)?
спустя 3 часа 50 минут [обр] Suvit[досье]

сделал 2 вопрос так, (язык питон)

def get_items(item, paths=paths, pathdelim='/'):# здесь пути всех разрешенных объектов
    paths.sort() # Это нужно чтобы первыми были ближайжее к item элементы по уровню вложености

    children = []
    for path in paths:
        if not path.startswith( item + pathdelim ):# только вложеные элементы(незнаю что лучще, сначала 
                                                   # выбрасить, потом сортировать, или так)
            continue
        for child in children:
            # выбрасываем детей у детей
            if path.startswith( child + pathdelim ):
                break
        else:
            children.insert( 0, path ) # всовываем в начало, чтобы быстрее сравнивать
                                       # для близких элементов(после сортировки много близких)

    return children

но тут из-за 2 вложеных циклов сложность O( len(paths) ^2 ), а еще есть тяжелая сортировка,
хотелось бы как то уменьшить сложность и избавится от сортировки.
просто может кто-то уже сталкивался с такой задачей.

ну и решение первого вопроса получаю из второго.

спустя 1 час 40 минут [обр] Владимир Палант(27/4445)[досье]

Сортировка нужна для первого вопроса — после сортировки все пути уже в правильном порядке, потом нужно лишь пройтись по ним и рассчитать уровень вложенности, сравнив их с предыдущими элементами списка.

Второй же вопрос вы решили как-то очень странно. Можно сначала пройтись по paths и запихнуть в массив temp всё, что начинается на item + pathdelim. Потом сортируем temp (там должно быть гораздо меньше элементов, чем в paths) и проходимся по temp, сохраняя предыдущий элемент в переменной prev. Если данный элемент начинается на prev + pathdelim, мы его игнорируем. Иначе мы заносим его в children и присваиваем prev = child. Получается O(len(paths) + O(len(temp) * log(len(temp))) + O(len(temp))).

Powered by POEM™ Engine Copyright © 2002-2005