эффективная функция для извлечения набора запросов предков набора запросов mptt - PullRequest
Новая
       21

эффективная функция для извлечения набора запросов предков набора запросов mptt

15 голосов
/ 24 июня 2011

Есть ли у кого-нибудь эффективный алгоритм для извлечения всех предков набора запросов mptt? Лучшее, о чем я мог думать, это что-то вроде этого: 

def qs_ancestors(queryset):
    if isinstance(queryset, EmptyQuerySet):
        return queryset
    queryset_aggs = queryset.values_list('tree_id', 'level').annotate(max_lft=Max('lft'), min_rght=Min('rght'))
    new_queryset = queryset.none()
    for tree_id, level, max_lft, min_rght in queryset_aggs:
        ancestors = MyModel.objects.filter(
           tree_id=tree_id,
           level__lt=level, 
           lft__lte=max_lft,
           rght__gte=min_rght,
        )
        new_queryset = ancestors | new_queryset
    return new_queryset

У этого подхода есть две проблемы:

  1. Сбой, если есть ветки, которые не находятся рядом друг с другом (то есть, на самом деле это не работает)
  2. Это крайне неэффективно, потому что в конечном итоге в окончательном запросе есть предложения number_of_trees*number_of_levels, которые могут быть очень большими и очень быстрыми

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

Ответы [ 2 ]

3 голосов
/ 04 июля 2011

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

Это работало хорошо, пока мой начальник не попросил меня реализовать опцию «поиск». При поиске нужно было просмотреть все узлы и взорвать дерево, если оно нашло совпадение. Мне потребовалось некоторое время, чтобы понять это, но я наконец понял. Вот решение, которое придумало: 

from django.db.models import Q

def get_parents(self, qs):
    tree_list = {}
    query = Q()
    for node in qs:
        if node.tree_id not in tree_list:
            tree_list[node.tree_id] = []

        parent =  node.parent.pk if node.parent is not None else None,

        if parent not in tree_list[node.tree_id]:
            tree_list[node.tree_id].append(parent)

            query |= Q(lft__lt=node.lft, rght__gt=node.rght, tree_id=node.tree_id)

    return YourModel.objects.filter(query)

Для запуска требуется только два запроса: начальный qs передан в качестве аргумента и последний набор запросов, возвращенный функцией. tree_list - это словарь, в котором хранятся узлы, которые уже были добавлены в набор запросов, это оптимизация, и алгоритм не нужен для работы. Но так как я работал с относительно большим деревом, мне пришлось включить его.

Полагаю, вы могли бы превратить этот метод в менеджера и сделать его более общим, то есть заставить его работать для любой модели MPTT, а не только YourModel

3 голосов
/ 30 июня 2011

Как насчет: 

def qs_ancestors(queryset):
    if isinstance(queryset, EmptyQuerySet):
        return queryset
    new_queryset = queryset.none()
    for obj in queryset:
        new_queryset = new_queryset | obj.get_ancestors()
return new_queryset

Это все еще предложения len (queryset).Потенциально можно немного уменьшить количество предложений, выполнив этап предварительной обработки, удаляющий объекты, являющиеся предками других объектов в наборе запросов, например: 

min_obj_set = []
for obj in queryset.order_by('tree_id', '-level'):
    for obj2 in min_obj_set:
        if obj.is_ancestor_of(obj2):
            break
    else:
        min_obj_set.append(obj)

Хотя приведенный выше фрагмент является лишь примером, выВозможно, вам захочется использовать BST, если ваш набор запросов содержит значительное количество объектов.

Вам придется проверить, приводит ли это к увеличению скорости по сравнению с большим запросом к БД.

...