16

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

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

  1. 隣り合っていないブランチがあると失敗します (つまり、実際には機能しません)。
  2. 最終的なクエリに句が含まれてしまうため、非常に非効率的でnumber_of_trees*number_of_levelsあり、非常に高速に巨大化する可能性があります

祖先を別の場所にキャッシュすることにオープンですが、効率的に行う方法が思いつきません。先祖のIDのコンマ区切りリストを含むフィールドを追加してから、GROUP_CONCAT（私はMySQLにいます）エクストラ内で実行することを検討しましたが、それは巨大/遅くなる可能性があると思います.

4

2 に答える 2

6

私は一度、同様のアルゴリズムを書かなければなりませんでした。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は、クエリセットに既に追加されているノードを格納するディクショナリです。これは最適化であり、アルゴリズムが機能する必要はありません。しかし、比較的大きなツリーを扱っていたので、それを含める必要がありました。

このメソッドをマネージャーに変えて、より一般的なものにすることができると思います。つまり、MPTT モデルだけでなく、どの MPTT モデルでも機能させることができますYourModel

于 2011-07-03T21:09:28.290 に答える
4

どうですか：

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)

上記のスニペットは単なる例ですが、querset に大量のオブジェクトが含まれている場合は、おそらく BST を使用することをお勧めします。

ただし、これにより、より大きな DB クエリと比較して速度が向上するかどうかをテストする必要があります。

于 2011-06-30T16:02:36.533 に答える