поиск корневого узла по данным дерева - PullRequest
Новая
       23

поиск корневого узла по данным дерева

0 голосов
/ 12 марта 2019

У меня есть следующий класс: 

class Category(object):
    def __init__(self, *args, **kwargs):
        self.id = kwargs.get('id')
        self.name = kwargs.get('name')
        self.parent_id = kwargs.get('parent_id', None)

    def get_top_parent_category(self, obj_list):
        # This algorithm is using extensive resource 
        category = self
        while category.parent_id:
            def filter_func(obj):
                return obj.id == category.parent_id
            parent = list(filter(filter_func, obj_list))

            category = parent[0]
        return category

    @classmethod
    def all(cls):
        url = BASE_URL + '/api/v1/categories/'
        response = requests.get(url, headers=headers, verify=False)
        if not response.status_code == 200:
            raise Exception('Error')
        categories = response.json()
        _temp_categories = []
        for _i in categories['results']:
            _temp_categories.append(cls(**_i))
        return _temp_categories

Я получаю все категории по: 

all_categories = Category.all()

Теперь мне нужно найти корневой узел любой предоставленной категории. 

category = Category(**category_data)
category.get_top_parent_category(all_categories)

Я получаю желаемые результаты, но мне кажется, что может быть лучший способ найти корневой узел, используя Теория графов

Какой может быть лучший подход к решению этой проблемы?

1 Ответ

0 голосов
/ 12 марта 2019

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

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

parent = list(filter(filter_func, obj_list))

Если вы замените его словарем, ваша производительность будет намного лучше, так как время поиска для одного родителябудет ~ постоянное время

например, просто например 

parent_map = dict([(c.id, c) for c in obj_list])

(очевидно, не делайте этого внутри метода get_top_parent_category (), так как это так же дорого)

Затем поиск родителя категории можно выполнить с помощью простого: 

parent = parent_map[parent.id]

Тот же цикл, который вы имеете сейчас, будет на порядок быстрее.

...