Django / Python - Grouper des objets par un ensemble commun à partir de relations plusieurs à plusieurs

Question

Ceci est une partie question d'algorithme-logique (comment le faire), partie question de mise en oeuvre (comment le faire au mieux!). Je travaille avec Django, alors je pensais partager cela.

En Python, il convient de mentionner que le problème est quelque peu lié à how-do- i-use-pythons-itertoolsgroupby .

Supposons que vous receviez deux classes dérivées du modèle Django:

from django.db import models

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

et

from django.db import models

class Mods(models.Model):
   ...

Comment obtient-on une liste de voitures, regroupées par voitures avec un ensemble commun de mods?

I.e. Je veux un cours de langue:

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

J'ai pensé à quelque chose comme:

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

Cependant, cela ne fonctionne pas parce que (peut-être parmi d'autres raisons) le groupe ne semble pas grouper par les ensembles de mods. Je suppose que la mod_list doit être triée pour fonctionner avec groupby. Tout ça pour dire, je suis convaincu qu'il y a quelque chose de simple et d'élégant à la fois éclairant et éclairant.

Cheers & amp; merci!

Answer 1

Avez-vous déjà essayé de trier la liste? L’algorithme que vous avez proposé devrait fonctionner, même s’il contient beaucoup de résultats de base de données.

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

Maintenant, à propos de ces requêtes:

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

Maintenant que vous avez vos listes d'identifiants de voiture et de mod, si vous avez besoin de travailler avec les objets complets, vous pouvez effectuer une requête unique pour obtenir une liste complète pour chaque modèle et créer une recherche dict pour ceux qui sont identifiés par leur identifiant - alors, je pense que Bob est le frère proverbial de votre père.

Answer 2

vérifiez regrouper . c'est seulement pour les modèles, mais je suppose que ce genre de classification appartient quand même à la couche présentation.

Answer 3

Vous avez quelques problèmes ici.

Vous n'avez pas trié votre liste avant d'appeler groupby, ce qui est obligatoire. De la documentation sur les outils de calcul :

  

En général, l'itérable doit déjà être trié sur la même fonction de touche.

Ensuite, vous ne dupliquez pas la liste renvoyée par groupby. Encore une fois, la documentation indique:

  

Le groupe retourné est lui-même un itérateur qui partage l'itérable sous-jacent avec   par groupe(). Comme la source est partagée, lorsque l’objet groupby est avancé, le   le groupe précédent n'est plus visible. Donc, si ces données sont nécessaires plus tard, il devrait   être stocké sous forme de liste:

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

Et la dernière erreur consiste à utiliser des ensembles comme clés. Ils ne travaillent pas ici. Une solution rapide consiste à les mouler sur des n-uplets triés (il pourrait y avoir une meilleure solution, mais je ne peux pas y penser maintenant).

Ainsi, dans votre exemple, la dernière partie devrait ressembler à ceci:

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 les performances vous préoccupent (par exemple, de nombreuses voitures sur une page ou un site très fréquenté), dénormaliser est logique et simplifie votre problème en tant qu’effet secondaire.

Sachez cependant que dénormaliser les relations plusieurs à plusieurs peut être un peu délicat. Je n'ai pas encore rencontré de tels exemples de code.

Answer 5

Merci à tous pour vos réponses utiles. Je me suis attelé à ce problème. Une solution "optimale" m'échappe toujours, mais j'ai quelques réflexions.

Je dois mentionner que les statistiques de l'ensemble de données avec lequel je travaille. Dans 75% des cas, il y aura un Mod. Dans 24% des cas, deux. Dans 1% des cas, il y en aura zéro, voire trois ou plus. Pour chaque mod, il existe au moins une voiture unique, bien qu'un mod puisse être appliqué à de nombreuses voitures.

Cela dit, j'ai envisagé (mais pas encore implémenté) quelque chose comme ça:

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

et changer de voiture pour

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

C’est simple de regrouper par groupe de voitures: je peux utiliser le regroupement, comme suggéré par Javier, par exemple. Cela semble une solution plus simple et assez élégante. des pensées seraient très appréciées.