python - 結合 - mpttクエリーセットの祖先のクエリーセットを取得する効率的な関数




クエリセットとは (2)

誰かがmptt querysetのすべての祖先を取り出す効率的なアルゴリズムを持っていますか? 私がこれまで考えることができる最高のものは次のようなものです:

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

このアプローチには2つの問題があります。

  1. 互いに隣り合っていないブランチがある場合(つまり実際には機能しない場合)、失敗します。
  2. 最終的なクエリではnumber_of_trees*number_of_levels節があるため非常に効率が悪く、非常に高速になる可能性があります

私は先祖をどこかにキャッシュすることにはオープンしていますが、効率的なやり方を考えることはできません。 私は祖先のIDのカンマ区切りのリストを持つフィールドを追加し、余分の中でGROUP_CONCAT (私はMySQLにあります)を実行することを考えましたが、それは巨大/低速になる可能性があると思います。


どのように:

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を使用することになります。

しかし、これが大規模なDBクエリと比較してスピードの向上をもたらすかどうかをテストする必要があります。


私は一度同様のアルゴリズムを書く必要があった。 私は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)

実行するクエリーは2つだけ必要です。最初のqsは引数として渡され、最後のクエリーセットは関数によって返されます。 tree_listは、すでにtree_list追加されているノードを保存する辞書です。最適化されているため、アルゴリズムが動作する必要はありません。 しかし、私は相対的に大きな木で作業していたので、それを含めなければなりませんでした。

私はあなたがこのメソッドをマネージャーにしてより一般的なものにすることができると思います。つまり、YourModelだけでなく、どんなMPTTモデルでも動作させることができYourModel





mptt