Django / Python - Agrupar objetos por conjunto común de una relación de muchos a muchos

Question

Esta es una pregunta de algoritmo-lógica de parte (cómo hacerlo), pregunta de implementación de parte (¡cómo hacerlo mejor!). Estoy trabajando con Django, así que pensé en compartir con eso.

En Python, vale la pena mencionar que el problema está relacionado con how-do- i-use-pythons-itertoolsgroupby .

Supongamos que te dan dos clases derivadas del modelo Django:

from django.db import models

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

y

from django.db import models

class Mods(models.Model):
   ...

¿Cómo se obtiene una lista de Autos, agrupados por Autos con un conjunto común de Mods?

I.e. Quiero obtener una clase como:

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' } },
]

He estado pensando en algo como:

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

Sin embargo, eso no funciona porque (quizás entre otras razones) el groupby no parece agruparse por los conjuntos de mods. Supongo que el mod_list tiene que estar ordenado para trabajar con groupby. Todo para decir, estoy seguro de que hay algo simple y elegante por ahí que será tanto esclarecedor como iluminador.

Saludos & amp; gracias!

Answer 1

¿Ha intentado clasificar la lista primero? El algoritmo que propuso debería funcionar, aunque con muchas visitas a la base de datos.

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

Ahora, acerca de esas consultas:

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]}]

Ahora que tiene sus listas de identificaciones de automóviles y de mods, si necesita los objetos completos para trabajar, puede hacer una única consulta para obtener una lista completa de cada modelo y crear un código de búsqueda. > dict para aquellos, codificados por sus identificadores - entonces, creo, Bob es el hermano de tu proverbial padre.

Answer 2

marque reagrupar . es solo para plantillas, pero supongo que este tipo de clasificación pertenece a la capa de presentación de todos modos.

Answer 3

Tienes algunos problemas aquí.

No ordenó su lista antes de llamar a groupby, y esto es obligatorio. De documentación de itertools :

  

En general, el iterable debe estar ya ordenado en la misma función clave.

Entonces, no duplica la lista devuelta por groupby. Una vez más, la documentación dice:

  

El grupo devuelto es en sí mismo un iterador que comparte el iterable subyacente con   agrupar por(). Debido a que la fuente es compartida, cuando el objeto groupby es avanzado, el   El grupo anterior ya no es visible. Entonces, si esos datos son necesarios más tarde, deberían   ser almacenado como una lista:

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

Y el error final es usar conjuntos como claves. Ellos no trabajan aquí. Una solución rápida es convertirlas en tuplas ordenadas (podría haber una solución mejor, pero no puedo pensar en ello ahora).

Entonces, en tu ejemplo, la última parte debería verse así:

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

Si el rendimiento es una preocupación (es decir, muchos autos en una página o un sitio de alto tráfico), denormalization tiene sentido y simplifica su problema como efecto secundario.

Tenga en cuenta que desnaturalizar relaciones de muchos a muchos puede ser un poco complicado. Todavía no he encontrado ninguno de estos ejemplos de código.

Answer 5

Gracias a todos por las útiles respuestas. He estado conectando este problema. Una "mejor" solución todavía me elude, pero tengo algunos pensamientos.

Debo mencionar que las estadísticas del conjunto de datos con el que estoy trabajando. En el 75% de los casos habrá una Mod. En el 24% de los casos, dos. En el 1% de los casos habrá cero, o tres o más. Para cada Mod, hay al menos un Coche único, aunque se puede aplicar un Mod a numerosos Coches.

Habiendo dicho eso, he considerado (pero no implementado) algo así como:

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

y cambia de coche a

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

Es trivial agrupar por Car.modset: puedo usar reagrupar, como lo sugiere Javier, por ejemplo. Parece una solución más simple y razonablemente elegante; Los pensamientos serían muy apreciados.