Django / Python - Raggruppamento di oggetti per set comune da relazioni molti-a-molti

Question

Questa è una domanda parte-algoritmo-logica (come farlo), una domanda di implementazione parte (come farlo meglio!). Sto lavorando con Django, quindi ho pensato di condividere con quello.

In Python, vale la pena ricordare che il problema è in qualche modo correlato a how-do- i-use-pitoni-itertoolsgroupby.

Supponi di avere due classi derivate dal Modello Django:

from django.db import models

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

e

from django.db import models

class Mods(models.Model):
   ...

Come si ottiene un elenco di auto, raggruppate per auto con un set comune di mod?

vale a dire. Voglio ottenere un like sulla classe:

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

Ho pensato a qualcosa del tipo:

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

Tuttavia, ciò non funziona perché (forse tra le altre ragioni) il groupby non sembra raggrupparsi per set di mod. Immagino che mod_list debba essere ordinato per funzionare con groupby. Tutto sommato, sono sicuro che ci sia qualcosa di semplice ed elegante là fuori che sarà sia illuminante che illuminante.

Saluti & amp; grazie!

Answer 1

Hai provato prima a ordinare l'elenco? L'algoritmo che hai proposto dovrebbe funzionare, anche se con un sacco di accessi al database.

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

Ora, su quelle domande:

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

Ora che hai i tuoi elenchi di ID auto e ID mod, se hai bisogno degli oggetti completi con cui lavorare, puoi fare una singola query per ognuno per ottenere un elenco completo per ogni modello e creare una ricerca dict per quelli, codificati dai loro id - quindi, credo, Bob è il fratello del tuo proverbiale padre.

Answer 2

controlla regroup . è solo per i modelli, ma immagino che questo tipo di classificazione appartenga comunque al livello di presentazione.

Answer 3

Hai qualche problema qui.

Non hai ordinato la tua lista prima di chiamare groupby, e questo è richiesto. Dalla documentazione itertools :

  

Generalmente, l'iterabile deve essere già ordinato sulla stessa funzione chiave.

Quindi, non duplicare l'elenco restituito da groupby. Ancora una volta, la documentazione afferma:

  

Il gruppo restituito è esso stesso un iteratore con cui condivide l'iterabile sottostante   raggruppa per(). Poiché l'origine è condivisa, quando l'oggetto groupby è avanzato, il   il gruppo precedente non è più visibile. Quindi, se tali dati sono necessari in un secondo momento, dovrebbero   essere memorizzato come un elenco:

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

E l'errore finale sta usando i set come chiavi. Non funzionano qui. Una soluzione rapida è lanciarli in tuple ordinate (potrebbe esserci una soluzione migliore, ma non riesco a pensarci ora).

Quindi, nel tuo esempio, l'ultima parte dovrebbe apparire così:

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 le prestazioni sono un problema (ovvero molte macchine su una pagina o un sito ad alto traffico), denormalizzazione ha senso e semplifica il problema come effetto collaterale.

Siate consapevoli del fatto che denormalizzare le relazioni molti-a-molti potrebbe essere un po 'complicato. Non ho ancora incontrato nessuno di questi esempi di codice.

Answer 5

Grazie a tutti per le risposte utili. Mi sono occupato di questo problema. Una soluzione "migliore" mi sfugge ancora, ma ho alcuni pensieri.

Dovrei menzionare che le statistiche del set di dati con cui sto lavorando. Nel 75% dei casi ci sarà un Mod. Nel 24% dei casi, due. Nell'1% dei casi ci saranno zero, o tre o più. Per ogni Mod, esiste almeno un'auto unica, sebbene una Mod possa essere applicata a numerose auto.

Detto questo, ho considerato (ma non implementato) qualcosa del genere:

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

e cambia auto in

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

È banale raggruppare per Car.modset: posso usare regroup, come suggerito da Javier, per esempio. Sembra una soluzione più semplice e ragionevolmente elegante; i pensieri sarebbero molto apprezzati.