Django/Python — группировка объектов по общему набору на основе отношений «многие ко многим»

Question

Это частично вопрос алгоритма-логики (как это сделать), частично вопрос реализации (как это сделать лучше всего!).Я работаю с Django, поэтому решил поделиться этим.

В Python стоит отметить, что проблема в некоторой степени связана с как-я-использую-pythons-itertoolsgroupby.

Предположим, вам даны два класса, производных от модели Django:

from django.db import models

class Car(models.Model):
    mods = models.ManyToManyField(Representative)

и

from django.db import models

class Mods(models.Model):
   ...

Как получить список Машин, сгруппированных по Машинам с общим набором Модов?

Т.е.Я хочу получить такой класс:

Cars_by_common_mods = [ 
  { mods: { 'a' }, cars: { 'W1', 'W2' } },
  { mods: { 'a', 'b' }, cars: { 'X1', 'X2', 'X3' }, },
  { mods: { 'b' }, cars: { 'Y1', 'Y2' } },
  { mods: { 'a', 'b', 'c' }, cars: { 'Z1' } },
]

Я думал о чем-то вроде:

def cars_by_common_mods():
  cars = Cars.objects.all()

  mod_list = []      

  for car in cars:
    mod_list.append( { 'car': car, 'mods': list(car.mods.all()) } 

  ret = []

  for key, mods_group in groupby(list(mods), lambda x: set(x.mods)):
    ret.append(mods_group)

  return ret

Однако это не работает, потому что (возможно, среди других причин) groupby, похоже, не группируется по наборам модов.Я предполагаю, что mod_list должен быть отсортирован для работы с groupby.В общем, я уверен, что есть что-то простое и элегантное, что будет одновременно просветляющим и просветляющим.

Приветствую и спасибо!

Answer 1

Вы пробовали сначала отсортировать список?Предложенный вами алгоритм должен работать, хотя и с большим количеством обращений к базе данных.

import itertools

cars = [
    {'car': 'X2', 'mods': [1,2]},
    {'car': 'Y2', 'mods': [2]},
    {'car': 'W2', 'mods': [1]},
    {'car': 'X1', 'mods': [1,2]},
    {'car': 'W1', 'mods': [1]},
    {'car': 'Y1', 'mods': [2]},
    {'car': 'Z1', 'mods': [1,2,3]},
    {'car': 'X3', 'mods': [1,2]},
]

cars.sort(key=lambda car: car['mods'])

cars_by_common_mods = {}
for k, g in itertools.groupby(cars, lambda car: car['mods']):
    cars_by_common_mods[frozenset(k)] = [car['car'] for car in g]

print cars_by_common_mods

Теперь об этих запросах:

import collections
import itertools
from operator import itemgetter

from django.db import connection

cursor = connection.cursor()
cursor.execute('SELECT car_id, mod_id FROM someapp_car_mod ORDER BY 1, 2')
cars = collections.defaultdict(list)
for row in cursor.fetchall():
    cars[row[0]].append(row[1])

# Here's one I prepared earlier, which emulates the sample data we've been working
# with so far, but using the car id instead of the previous string.
cars = {
    1: [1,2],
    2: [2],
    3: [1],
    4: [1,2],
    5: [1],
    6: [2],
    7: [1,2,3],
    8: [1,2],
}

sorted_cars = sorted(cars.iteritems(), key=itemgetter(1))
cars_by_common_mods = []
for k, g in itertools.groupby(sorted_cars, key=itemgetter(1)):
    cars_by_common_mods.append({'mods': k, 'cars': map(itemgetter(0), g)})

print cars_by_common_mods

# Which, for the sample data gives me (reformatted by hand for clarity)
[{'cars': [3, 5],    'mods': [1]},
 {'cars': [1, 4, 8], 'mods': [1, 2]},
 {'cars': [7],       'mods': [1, 2, 3]},
 {'cars': [2, 6],    'mods': [2]}]

Теперь, когда у вас есть списки идентификаторов автомобилей и идентификаторов модов, если вам нужны полные объекты для работы, вы можете выполнить один запрос для каждого, чтобы получить полный список для каждой модели и создать поиск. dict для тех, кто использует свои идентификаторы - тогда, я считаю, Боб - брат вашего пресловутого отца.

Answer 2

проверять перегруппироваться.это только для шаблонов, но я думаю, что такая классификация в любом случае относится к уровню представления.

Answer 3

У вас здесь несколько проблем.

Вы не отсортировали свой список перед вызовом groupby, а это необходимо.От документация itertools:

Как правило, итерируемый объект уже должен быть отсортирован по одной и той же ключевой функции.

Тогда вы не дублируете список, возвращаемый groupby.Опять же, в документации говорится:

Возвращенная группа сама по себе является итератором, который разделяет базовую итерацию с GroupBy ().Поскольку источник делится, когда объект Groupby продвигается, предыдущая группа больше не видно.Итак, если эти данные необходимы позже, их следует хранить в виде списка:

groups = []
uniquekeys = []
for k, g in groupby(data, keyfunc):
    groups.append(list(g))      # Store group iterator as a list
    uniquekeys.append(k)

И последняя ошибка — использование наборов в качестве ключей.Они здесь не работают.Быстрое решение — преобразовать их в отсортированные кортежи (может быть лучшее решение, но сейчас я не могу об этом думать).

Итак, в вашем примере последняя часть должна выглядеть так:

sortMethod = lambda x: tuple(sorted(set(x.mods)))
sortedMods = sorted(list(mods), key=sortMethod)
for key, mods_group in groupby(sortedMods, sortMethod):
    ret.append(list(mods_group))

Answer 4

Если производительность вызывает беспокойство (т.много автомобилей на странице или сайт с высокой посещаемостью), денормализация имеет смысл и упрощает вашу проблему как побочный эффект.

Имейте в виду, что денормализация отношений «многие ко многим» может оказаться немного сложной задачей.Я еще не встречал подобных примеров кода.

Answer 5

Спасибо всем за полезные ответы.Я заморачивался над этой проблемой.«Лучшее» решение все еще ускользает от меня, но у меня есть кое-какие мысли.

Я должен упомянуть, что статистика набора данных, с которым я работаю.В 75% случаев будет один Мод.В 24% случаев — два.В 1% случаев их будет ноль, три и более.Для каждого мода существует как минимум одна уникальная машина, хотя мод можно применить к множеству машин.

Сказав это, я рассмотрел (но не реализовал) что-то вроде этого:

class ModSet(models.Model):
  mods = models.ManyToManyField(Mod)

и поменять машину на

class Car(models.Model):
  modset = models.ForeignKey(ModSet)

Группировать по Car.modset тривиально:Я могу использовать перегруппировку, как предложил, например, Хавьер.Это кажется более простым и достаточно элегантным решением;мысли были бы очень признательны.