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

Question

Esta es una pregunta de parte de algoritmo lógica (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 un poco how-do-i-use-pythons-itertoolsgroupby.

supongamos que usted es dado dos clases de derivados de los modelos de 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 puede obtener una lista de los coches, agrupados por coches con un conjunto común de Mods?

I.e. Quiero conseguir un likeso clase:

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, que no funciona debido a que (quizá entre otras razones) la GroupBy no lo hace parece agruparse por los conjuntos de modificaciones. Supongo que la lista_de_mod debe ser ordenada para que funcione con groupby. Todo para decir, estoy seguro de que hay algo simple y elegante por ahí que será a la vez instructivo y esclarecedor.

Saludos & gracias!

Answer 1

has necesitado ordenar la lista por primera vez? El algoritmo que propuso debería funcionar, aunque con muchos hits en 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, sobre 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 usted tiene sus listas de identificadores de automóviles y las identificaciones mod, si necesita los objetos completos para trabajar, usted podría hacer un solo consulta para que cada uno obtenga una lista completa para cada modelo y cree una búsqueda dict para aquellos, codificados por sus identificaciones; entonces, creo, Bob es el proverbial hermano de su padre.

Answer 2

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

Answer 3

Tiene algunos problemas aquí.

No ordenaste tu lista antes de llamar a groupby, y esto es obligatorio. De itertools documentation:

En general, el iterable necesita estar ordenado en la misma función de tecla.

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

el grupo volvió en sí es un iterador que comparte la iterables subyacente con GroupBy().Como la fuente se comparte, cuando se avanza el objeto groupby, el grupo anterior ya no está visible. Por lo tanto, si se necesita que los datos más adelante, debe 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 último error está utilizando conjuntos como claves. Ellos no trabajan aquí. Una solución rápida es convertirlos en tuplas ordenadas (podría haber una solución mejor, pero no puedo pensar en eso ahora).

Así, en su ejemplo, la última parte debería tener este aspecto:

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, un montón de coches en una página o un sitio de alto tráfico), denormalization tiene sentido y simplifica tu problema como un efecto secundario.

Sin embargo, tenga en cuenta que la desnormalización de relaciones muchos a muchos puede ser un poco complicado. Todavía no me he encontrado con ningún ejemplo de código.

Answer 5

Gracias a todos por las útiles respuestas. Me he estado ocupando de este problema. La 'mejor' solución todavía me escapa, 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 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 automóvil único, aunque se puede aplicar un Mod a numerosos automóviles.

Dicho esto, he considerado (pero no implementado) algo así como tan:

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

y cambiar de coche a

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

Es trivial grupo por Car.modset: I puede usar reagrupamiento, como lo sugirió Javier, por ejemplo. Parece una solución más simple y razonablemente elegante; los pensamientos serían muy apreciados.