Django/Python - Gruppieren von Objekten nach gemeinsamen Satz von einer Viele-zu-viele-Beziehungen

Question

Dies ist ein Teil Algorithmus-Logik-Frage (wie es gemacht wird), Teil-Implementierung Frage (wie es am besten geht!). Ich arbeite mit Django, also dachte ich, ich würde das teilen. In Python ist es erwähnenswert, dass das Problem etwas mit how-do-i-use-pythons-itertoolsgroupby zusammenhängt.

Angenommen, Sie sind bei zwei Django Modell abgeleiteten Klassen:

from django.db import models 

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

und

from django.db import models 

class Mods(models.Model): 
    ... 

Wie man eine Liste von Autos, von Autos mit einem gemeinsamen Satz von Mods gruppiert bekommt?

I.e. Ich möchte eine Klasse likeso erhalten:

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

Ich habe wie von etwas gedacht:

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 

jedoch nicht, weil nicht funktioniert (vielleicht unter anderem) die groupby nicht scheinen nach den Mods-Sets zu gruppieren. Ich denke, die mod_list muss so sortiert werden, dass sie mit groupby funktioniert. Alles in allem bin ich zuversichtlich, dass es da draußen etwas Einfaches und Elegantes gibt, das sowohl erhellend als auch erhellend sein wird.

Prost & danke!

Answer 1

Haben Sie versucht, die Liste zuerst zu sortieren? Der Algorithmus, den Sie vorgeschlagen haben, sollte funktionieren, allerdings mit vielen Datenbanktreffern.

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 

Nun, über diese Abfragen:

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

Nun, da Sie Ihre Listen von Auto-IDs und mod-IDs haben, wenn Sie die komplette Objekte müssen mit arbeiten, können Sie eine einzelne tun Abfrage für jeden, um eine vollständige Liste für jedes Modell zu erhalten und erstellen Sie eine Suche dict für diejenigen, die von ihren IDs - dann, glaube ich, Bob ist der Bruder Ihres sprichwörtlichen Vaters.

Answer 2

überprüfen Sie regroup. Es ist nur für Vorlagen, aber ich denke, diese Art der Klassifizierung gehört sowieso zur Präsentationsebene.

Answer 3

Sie haben hier ein paar Probleme.

Sie haben Ihre Liste vor dem Aufruf von groupby nicht sortiert, und dies ist erforderlich. Von itertools documentation:

:

Im Allgemeinen muss das iterable bereits nach der gleichen Schlüsselfunktion sortiert werden.

Dann duplizieren Sie nicht die von groupby zurückgegebene Liste. Wieder Dokumentation heißt es:

Die zurückgegebene Gruppe selbst ein Iterator ist, dass der zugrunde liegende iterable mit groupby() teilt.Da die Quelle freigegeben ist, ist die vorherige Gruppe nicht mehr sichtbar, wenn das groupby-Objekt erweitert wird. Also, wenn diese Daten später benötigt wird, soll es als Liste gespeichert werden:

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

und letzten Fehler wird unter Verwendung von Sätzen als Schlüssel. Sie arbeiten hier nicht. Eine schnelle Lösung besteht darin, sie in sortierte Tupel zu konvertieren (es könnte eine bessere Lösung geben, aber ich kann jetzt nicht daran denken).

Also, in Ihrem Beispiel, der letzte Teil sollte wie folgt aussehen:

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

Wenn Leistung ein Anliegen ist (dh viele Autos auf einer Seite oder eine High-Traffic-Website), macht denormalization Sinn und vereinfacht Ihr Problem als Nebeneffekt.

Beachten Sie, dass die Denormalisierung von Viele-zu-Viele-Beziehungen ein wenig schwierig sein kann. Ich bin noch nicht auf solche Codebeispiele gestoßen.

Answer 5

Vielen Dank für die hilfreichen Antworten. Ich habe dieses Problem beseitigt. Eine "beste" Lösung entgeht mir immer noch, aber ich habe einige Gedanken.

Ich sollte erwähnen, dass die Statistik des Datensatzes, mit dem ich arbeite. In 75% der Fälle wird es einen Mod geben. In 24% der Fälle zwei. In 1% der Fälle wird es null oder drei oder mehr geben. Für jeden Mod gibt es mindestens ein einzigartiges Auto, obwohl ein Mod auf zahlreiche Autos angewendet werden kann.

Having said that, ich habe in Betracht gezogen (aber nicht umgesetzt) ​​so etwas wie-so:

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

und Autos

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

zu

zu einer Gruppe von Car.modset Es ist trivial ändern: I kann die Umgruppierung verwenden, wie beispielsweise von Javier vorgeschlagen. Es scheint eine einfachere und einigermaßen elegante Lösung zu sein; Gedanken würden sehr geschätzt werden.