Django/Python - Objekte Gruppieren durch gemeinsame aus einer viele-zu-viele-Beziehungen

Question

Dies ist ein Teil-Algorithmus-Logik-Frage (wie es zu tun), Teil der Implementierung Frage (wie man es am besten!).Ich arbeite mit Django, so dass ich dachte, ich würde teilen mit, dass.

In Python, es ist erwähnenswert, dass das problem etwas mit Bezug zu how-do-i-use-pythons-itertoolsgroupby.

Angenommen, Sie sind 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 macht man eine Liste der Autos, gruppiert nach Autos mit einem gemeinsamen Satz von Mods?

I. e.Ich möchte eine Klasse 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' } },
]

Ich habe darüber nachgedacht, etwas wie:

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

Aber das klappt nicht, weil (vielleicht neben anderen Gründen) der groupby scheint nicht zu Gruppe der mods sets.Ich denke, die mod_list muss sortiert werden, um die Arbeit mit groupby.Alle sagen, ich bin zuversichtlich, es gibt etwas, das einfach und elegant gibt, die sowohl aufschlussreich und erhellend.

Cheers & danke!

Answer 1

Haben Sie versucht, zuerst die Liste Sortierung? Der Algorithmus sollte man allerdings mit vielen Datenbank Hits arbeiten, vorgeschlagen.

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 kompletten Objekte müssen mit arbeiten, können Sie eine einzelne Abfrage tun für die jeweils eine komplette Liste für jedes Modell zu erhalten und eine Lookup dict schafft für diejenigen, durch deren ids verkeilt -. dann, glaube ich, Bob ist dein sprichwörtlich Vaters Bruder

Answer 2

Neugruppierung . es ist nur für Vorlagen, aber ich denke, diese Art der Klassifizierung der ohnehin Präsentationsschicht gehört.

Answer 3

Sie haben ein paar Probleme hier.

Sie haben sortieren Sie Ihre Liste nicht vor dem Aufruf groupby, und dies erforderlich ist. Aus itertools Dokumentation :

  

Im Allgemeinen ist die iterable muss bereits auf der gleichen Tastenfunktion sortiert werden.

Dann Sie die Liste nicht duplizieren, indem groupby zurückgegeben. Wieder Dokumentation heißt es:

  

Die zurückgegebene Gruppe ist selbst ein Iterator, der die zugrunde liegenden iterable teilt mit   gruppiere nach(). Da die Quelle geteilt wird, wenn das Objekt groupby vorgeschoben wird, die   vorherige Gruppe nicht mehr sichtbar ist. Also, wenn diese Daten später benötigt wird, sollte es   wird als eine Liste gespeichert:

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

Und letzter Fehler wird unter Verwendung von Sätzen als Schlüssel. Sie funktionieren hier nicht. Eine schnelle Lösung ist, sie zu sortieren Tupel zu werfen (es könnte eine bessere Lösung sein, aber ich kann es jetzt nicht 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 die Leistung ist ein Anliegen (dh viele Autos auf einer Seite oder eine High-Traffic-Website), Denormalisierung macht Sinn, und vereinfacht Ihr Problem als Nebenwirkung.

Beachten Sie, dass Denormalisierung many-to-many-Beziehungen könnte aber ein bisschen schwierig sein. Ich habe noch nicht in solchen Code-Beispiele ausgeführt werden.

Answer 5

Danke Euch allen für die hilfreichen Antworten.Ich habe einstecken entfernt an dieses problem.Eine "beste" Lösung noch entzieht sich mir, aber ich habe einige Gedanken.

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

Nachdem das gesagt ist, habe ich mir überlegt (aber nicht umgesetzt) so etwas wie so:

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

und ändern Autos

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

Es ist trivial zu der Gruppe mit dem Auto.modset:Ich verwenden können, neu-gruppieren, wie vorgeschlagen, von Javier, zum Beispiel.Es scheint ein einfacher und halbwegs elegante Lösung;Gedanken würden sehr geschätzt.