Django / Python-多対多の関係からの共通セットによるオブジェクトのグループ化

Question

これは、一部のアルゴリズムと論理の質問（それを行う方法）、一部の実装の質問（それを最善にする方法）です。私はDjangoで作業しているので、共有したいと思いました。

Pythonでは、この問題は how-do- i-use-pythons-itertoolsgroupby 。

Django Modelから派生した2つのクラスが与えられたとします：

from django.db import models

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

and

from django.db import models

class Mods(models.Model):
   ...

どのように車のリストを取得し、一般的な改造のセットで車ごとにグループ化しますか？

つまり次のようなクラスを取得したい：

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

次のようなことを考えてきました：

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

ただし、groupbyはmodセットによってグループ化されていないようです（おそらく他の理由もあります）。 groupbyで動作するにはmod_listをソートする必要があると思います。言うまでもなく、そこにはシンプルでエレガントなものがあり、それが啓発と照明の両方になると確信しています。

乾杯＆amp;ありがとう！

Answer 1

最初にリストをソートしてみましたか？提案したアルゴリズムは、多くのデータベースヒットが発生しても動作するはずです。

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

今、これらのクエリについて：

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

車のIDとMODのIDのリストを取得したので、完全なオブジェクトを操作する必要がある場合は、それぞれに対して単一のクエリを実行して、各モデルの完全なリストを取得し、ルックアップ<コードそれらのIDをキーとするそれらのための> dict -そして、私は、ボブがあなたのことわざの父の兄弟であると信じています。

Answer 2

再グループ化を確認します。テンプレート専用ですが、とにかくこの種の分類はプレゼンテーション層に属していると思います。

Answer 3

ここにいくつか問題があります。

groupbyを呼び出す前にリストをソートしなかったため、これは必須です。 itertoolsのドキュメントから：

  

一般に、反復可能オブジェクトは同じキー機能で既にソートされている必要があります。

その後、groupbyによって返されるリストを複製しません。繰り返しますが、ドキュメントの状態：

  

返されるグループ自体は、基になる反復可能オブジェクトを共有する反復子です   groupby（）。ソースは共有されているため、groupbyオブジェクトが進められると、   前のグループは表示されなくなりました。そのため、後でそのデータが必要になった場合、   リストとして保存する：

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

最後の間違いは、セットをキーとして使用することです。ここでは機能しません。簡単な修正方法は、ソートされたタプルにキャストすることです（より良い解決策があるかもしれませんが、今は考えられません）。

したがって、あなたの例では、最後の部分は次のようになります。

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

パフォーマンスが懸念される場合（ページ上の多くの車、またはトラフィックの多いサイト）、非正規化は理にかなっており、副作用として問題を簡素化します。

ただし、多対多の関係の非正規化は少し注意が必要な場合があることに注意してください。そのようなコード例にはまだ出会っていません。

Answer 5

有益な回答をありがとうございました。私はこの問題を解決してきました。 「最高の」解決策はまだ私を避けますが、私はいくつかの考えを持っています。

作業しているデータセットの統計について言及する必要があります。ケースの75％に1つのModがあります。ケースの24％で、2つ。 1％のケースでは、ゼロまたは3つ以上があります。 MODは複数の車に適用できますが、すべてのMODには少なくとも1つのユニークな車があります。

それを言って、私は次のようなものを考えました（しかし実装していません）：

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

そして車を変更

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

Car.modsetでグループ化するのは簡単です。たとえば、Javierが提案するように、regroupを使用できます。これは、よりシンプルで合理的なソリューションです。考えをいただければ幸いです。