Ускоренная генерация таблиц содержимого в Django

Я пытаюсь сделать таблицу содержимого для моего queryset в Django следующим образом:

    def get_toc(self):
        toc = {}
        qs = self.get_queryset()
        idx = set()
        for q in qs:
            idx.add(q.title[0])
        idx = list(idx)
        idx.sort()
        for i in idx:
            toc[i] = []
            for q in qs:
                if q.title[0] == i:
                    toc[i].append(q)
        return toc

Но это имеет временную сложность O(n^2). Есть ли лучший способ сделать это?

Я считаю, что это эквивалентно вышеописанному, но должно быть намного быстрее, так как использует движок базы данных для сортировки и де-дупликации:

def get_toc(self):
    return {
        q.title[0]: q
        for q in self.get_queryset().distinct("title").order_by('title')
    }

Вместо того чтобы перебирать все запросы для каждого элемента в idx, пройдитесь по qs в качестве крайнего и единственного цикла for, добавляя каждый запрос в соответствующий бакет. Примерно так:

def get_toc(self):
    toc = {}
    qs = self.get_queryset()

    for q in qs:
        t = q.title[0]
        toc[t].setdefault(t, []).append(value)

    return toc

Первоначальное решение было не таким плохим, как O(n^2) - это O(nm), где n - длина queryset, а m - количество уникальных названий. В худшем случае (когда каждая запись уникальна по названию) это превратилось бы в O(n^2). Новое решение - O(n).

Это похоже не на оглавление, а на глоссарий, где первый символ термина отображается на список терминов.

Мы можем работать с .groupby(…) [python-doc] здесь:

from itertools import groupby

result = {
    k: list(vs)
    for k, vs in groupby(
        self.get_queryset().order_by('title'), lambda x: x.title[0]
    )
}
Вернуться на верх