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

Есть ли у кого-нибудь эффективный алгоритм для извлечения всех предков запроса 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 15
python hierarchical-data

2 ответа:

Как насчет: 

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, если ваш querset содержит значительное количество объектов.

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

3

Однажды мне пришлось написать подобный алгоритм. У меня было представление, отображающее дерево 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, передаваемый в качестве аргумента, и конечный queryset, возвращаемый функцией. tree_list - это словарь, в котором хранятся узлы, уже добавленные в queryset, это оптимизация, и она не нужна для работы алгоритма. Но так как я работал с относительным большим деревом, я должен был включить его.

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

3