Django/Python - Regrouper des objets par ensemble commun d'une relation plusieurs-à-plusieurs

Question

Il s'agit d'une question algorithmique-logique (comment le faire), question de la mise en œuvre partielle (comment le faire mieux!). Je travaille avec Django, alors j'ai pensé partager ça avec ça. En Python, le problème est quelque peu lié à how-do-i-use-pythons-itertoolsgroupby.

Supposons que vous avez donné deux classes dérivées 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 peut-on obtenir une liste des voitures, regroupées par voitures avec un ensemble commun de Mods?

I.e. Je veux obtenir un likeso de 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' } }, 
] 

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 entre autres) la groupby ne semblent se regrouper par les ensembles de mods. Je suppose que le mod_list doit être trié pour fonctionner avec groupby. Tout ça pour dire, je suis confiant qu'il y a quelque chose de simple et d'élégant qui sera à la fois éclairant et éclairant.

Salutations & merci!

Answer 1

Avez-vous essayé de trier la liste en premier? L'algorithme que vous avez proposé devrait fonctionner, mais avec beaucoup de succès dans la 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, au sujet 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 de ids de voiture et ids mod, si vous avez besoin des objets complets pour travailler avec, vous pourriez faire une seule requête pour chacun d'obtenir une liste complète pour chaque modèle et créer une recherche dict pour ceux, saisis par leurs identifiants - alors, je crois, Bob est le frère de votre père proverbiale.

Answer 2

vérifiez regroup. c'est seulement pour les templates, mais je suppose que ce genre de classification appartient à la couche de présentation de toute façon.

Answer 3

Vous avez quelques problèmes ici.

Vous n'avez pas trié votre liste avant d'appeler groupby, et cela est nécessaire. De itertools documentation:

Généralement, l'itérable doit déjà être trié sur la même fonction de clé.

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

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

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

Et dernière erreur utilise des ensembles comme clés. Ils ne travaillent pas ici. Une solution rapide consiste à les convertir en tuples 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 la performance est une préoccupation (à savoir beaucoup de voitures sur une page ou un site à fort trafic), denormalization est logique et simplifie votre problème en tant qu'effet secondaire. Sachez cependant que la dénormalisation des relations plusieurs-à-plusieurs peut être un peu compliquée. Je n'ai pas encore rencontré de tels exemples de code.

Answer 5

Merci à tous pour les réponses utiles. J'ai été brancher à ce problème. Une «meilleure» solution m'échappe toujours, mais j'ai quelques réflexions.

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

Cela dit, je l'ai considéré (mais non mis en œuvre) quelque chose comme-si:

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

et changer les voitures à

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

Il est trivial de groupe par Car.modset: I peut utiliser regrouper, comme suggéré par Javier, par exemple. Cela semble une solution plus simple et raisonnablement élégante; Les pensées seraient très appréciées.