Django / Python - Agrupamento de objetos de conjunto comum de um muitos-para-muitos relacionamentos

Question

Esta é uma pergunta parte algoritmo de lógica (como fazê-lo), pergunta implementação parte (como fazê-lo melhor!). Eu estou trabalhando com Django, então eu pensei que iria partilhar com isso.

Em Python, vale a pena mencionar que o problema é algo relacionado a how-do- i-use-pítons-itertoolsgroupby .

Suponha que você está dado duas classes Django Model-derivados:

from django.db import models

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

e

from django.db import models

class Mods(models.Model):
   ...

Como se obter uma lista de carros, agrupados por carros com um conjunto comum de Mods?

i. Eu quero começar uma classe likeso:

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

Eu estive pensando em 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

No entanto, isso não funciona porque (talvez entre outras razões) a groupby não parece grupo pelos conjuntos mods. Eu acho que a mod_list tem de ser resolvida para trabalhar com groupby. Tudo para dizer, estou confiante de que há algo simples e elegante lá fora, que será ao mesmo tempo esclarecedor e esclarecedora.

Felicidades e obrigado!

Answer 1

Você tentou classificar a lista em primeiro lugar? O algoritmo que você proposta deve funcionar, embora com muitos hits de banco de dados.

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

Agora, sobre essas 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]}]

Agora que você tem suas listas de ids de carro e ids mod, se você precisar os objetos completos para trabalhar com, você poderia fazer uma única consulta para cada um para obter uma lista completa para cada modelo e criar um dict pesquisa para aqueles, introduzidos por seus ids -., em seguida, creio eu, Bob é o irmão de seu pai proverbial

Answer 2

reagrupar . é apenas para modelos, mas eu acho que esse tipo de classificação pertence à camada de apresentação de qualquer maneira.

Answer 3

Você tem alguns problemas aqui.

Você não classificar sua lista antes de chamar groupby, e isso é necessário. De itertools documentação :

Geralmente, as necessidades iteráveis ??já estar classificados na mesma tecla de função.

Então, você não duplicar a lista devolvida pelo groupby. Novamente, estados documentação:

O grupo retornado é em si um iterador que as ações da iterable subjacente com groupby (). Porque a fonte é compartilhada, quando o objeto groupby é avançada, a grupo anterior não é mais visível. Então, se os dados são necessários mais tarde, deveria ser armazenados como uma lista:

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

E erro final está usando conjuntos de chaves. Eles não trabalham aqui. Uma solução rápida é para lançá-los para tuplas ordenadas (poderia haver uma solução melhor, mas eu não posso pensar nisso agora).

Assim, no seu exemplo, a última parte deve ficar assim:

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

Se o desempenho é uma preocupação (ou seja, lotes de carros em uma página ou um site de alto tráfego), desnormalização faz sentido, e simplifica o seu problema como um efeito colateral.

Esteja ciente de que desnormalizar muitos-para-muitos relações pode ser um embora complicada bit. Eu não tenho que correr em tais exemplos de código ainda.

Answer 5

Obrigado a todos pelas respostas úteis. Eu estive longe de ligar a este problema. Uma solução 'melhor' ainda me escapa, mas eu tenho alguns pensamentos.

Eu devo mencionar que as estatísticas do conjunto de dados que eu estou trabalhando. Em 75% dos casos, haverá uma modificação. Em 24% dos casos, dois. Em 1% dos casos não irá ser igual a zero, ou três ou mais. Para cada Mod, há pelo menos um carro único, embora um Mod pode ser aplicado para vários carros.

Dito isto, tenho considerado (mas não implementado) algo como-assim:

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

e carros de alteração para

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

É trivial para agrupar por Car.modset: Eu posso usar reagrupar, como sugerido por Javier, por exemplo. Parece uma solução mais simples e razoavelmente elegante; pensamentos seria muito apreciado.