Расчет комбинаций с использованием Django ORM (CROSS JOIN)

У меня есть три связанные модели: Process, Factor и Level. Process имеет отношения "многие ко многим" с Factors, а Factor будет иметь один или несколько Levels. Я пытаюсь рассчитать все комбинации Level, связанные с Process. Это легко реализовать с помощью Python itertools в качестве метода модели, но скорость выполнения несколько медленная, поэтому я пытаюсь понять, как использовать Django ORM для выполнения этого вычисления в SQL.

Модели:

class Process(models.Model):
    factors = models.ManyToManyField(Factor, blank = True)

class Factor(models.Model):
    ...

class Level(models.Model):
    factor = models.ForeignKey(Factor, on_delete=models.CASCADE)

Пример: Процесс 'Running' включает в себя три Factors ('Distance', 'Climb', 'Surface'), каждый из которых состоит из нескольких Levels ('Long'/'Short', 'Flat'/'Hilly', 'Road'/'Mixed'/'Trail'). Вычисление комбинаций в SQL будет включать построение запроса, сначала определяя, сколько Factor было задействовано (3 в этом примере), и выполняя CROSS JOIN всех уровней столько раз.

В SQL это может быть выполнено следующим образом:

WITH foo AS
    (SELECT * FROM Level
     WHERE Level.factor_id IN
        (SELECT ProcessFactors.factor_id FROM ProcessFactors WHERE process_id = 1)
    )
SELECT a1.*, a2.*, a3.*
    FROM foo a1
    CROSS JOIN foo a2
    CROSS JOIN foo a3
WHERE (a1.factor_id < a2.factor_id) AND (a2.factor_id < a3.factor_id)

Результат:

a1.name | a2.name | a3.name
--------------------------
Long    | Flat    | Road
Long    | Flat    | Mixed
Long    | Flat    | Trail
Long    | Hilly   | Road
Long    | Hilly   | Mixed
Long    | Hilly   | Trail
Short   | Flat    | Road
Short   | Flat    | Mixed
Short   | Flat    | Trail
Short   | Hilly   | Road
Short   | Hilly   | Mixed
Short   | Hilly   | Trail

В настоящее время я реализовал это как метод для модели Process как:

def level_combinations(self):
    levels = []
    for factor in self.factors.all():
        levels.append(Level.objects.filter(factor = factor))
    
    combinations = []
    for levels in itertools.product(*levels):
        combination = {}
        
        combination["levels"] = levels
        
        combinations.append(combination)
    
    return combinations

Возможно ли это с помощью Django ORM или он достаточно сложен, чтобы его можно было реализовать как необработанный запрос для повышения скорости по сравнению с реализацией кода Python?

Несколько лет назад возник похожий вопрос о выполнении CROSS JOIN в Django ORM (примерно Django v1.3 выглядит так) не привлекал особого внимания (автор решил просто использовать Python itertools).


django django-queryset django-orm
person Linville    schedule 22.01.2016    source источник

Ответы (3)


arrow_upward
3
arrow_downward 

from itertools import groupby, product
    
def level_combinations(self):
    # We need order by factor_id for proper grouping
    levels = Level.objects.filter(factor__process=self).order_by('factor_id')
    # [{'name': 'Long', 'factor_id': 1, ...},
    #  {'name': 'Short', 'factor_id': 1, ...},
    #  {'name': 'Flat', 'factor_id': 2, ...},
    #  {'name': 'Hilly', 'factor_id': 2, ...}]

    groups = [list(group) for _, group in groupby(levels, lambda l: l.factor_id)]
    # [[{'name': 'Long', 'factor_id': 1, ...},
    #   {'name': 'Short', 'factor_id': 1, ...}],
    #  [{'name': 'Flat', 'factor_id': 2, ...},
    #   {'name': 'Hilly', 'factor_id': 2, ...}]]

    # Note: don't forget, that product is iterator/generator, not list
    return product(*groups)

Если порядок не имеет значения, то:

def level_combinations(self):
    levels = Level.objects.filter(factor__process=self)
    groups = {}
    for level in levels:
        groups.setdefault(level.factor_id, []).append(level)
    return product(*groups.values())
person Community    schedule 23.01.2016
comment
Хотя это не чистое решение Django ORM, на которое я надеялся (которого в любом случае не существует с Django 1.9), оно значительно быстрее, чем код, который я использовал раньше (у timeit он примерно на 60% быстрее). Для моего производственного набора данных неупорядоченный алгоритм примерно на 10% быстрее, чем упорядоченный метод). - person Linville; 27.01.2016

arrow_upward
0
arrow_downward

Если я вас правильно понял, вы можете попробовать:

for process in Process.objects.all():
    # get all levels for current process
    levels = Level.objects.filter(factor__in=process.factors.all())
person Shang Wang    schedule 22.01.2016

arrow_upward
0
arrow_downward

Спустя несколько лет этот обходной путь не на самом деле использует CROSS JOIN, но действительно дает желаемый результат в одном запросе.

Шаг 1: добавьте поле cross в модель Factor

class Factor(models.Model):
    cross = models.ForeignKey(
        to='self', on_delete=models.CASCADE, null=True, blank=True)
    ...

Шаг 2: свяжите 'Climb' с 'Surface' и свяжите 'Distance' с 'Climb', используя новое поле Factor.cross

Шаг 3: запрос следующим образом

Level.objects.filter(factor__name='Distance').values_list(
    'name', 'factor__cross__level__name', 'factor__cross__cross__level__name')

Результат:

('Long', 'Flat', 'Road')
('Long', 'Flat', 'Mixed')
('Long', 'Flat', 'Trail')
('Long', 'Hilly', 'Road')
('Long', 'Hilly', 'Mixed')
('Long', 'Hilly', 'Trail')
('Short', 'Flat', 'Road')
('Short', 'Flat', 'Mixed')
('Short', 'Flat', 'Trail')
('Short', 'Hilly', 'Road')
('Short', 'Hilly', 'Mixed')
('Short', 'Hilly', 'Trail')

Это упрощенный пример. Чтобы сделать его более общим, вместо добавления поля Factor.cross вы можете добавить новую модель CrossedFactors с двумя внешними ключами в Factor. Затем эту модель можно использовать для определения различных экспериментальных планов.

person djvg    schedule 16.07.2021