8

これは、アルゴリズム ロジックに関する質問 (どのように行うか) と、実装に関する質問 (どのように最善を尽くすか) の部分です。私は Django で作業しているので、それを共有したいと思いました。

Python では、問題がhow-do-i-use-pythons-itertoolsgroupby に多少関連していることに言及する価値があります。

Django モデルから派生した 2 つのクラスが与えられたとします。

from django.db import models

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

と

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 が mods セットによってグループ化されていないように見えるため、これは機能しません。groupby を使用するには、mod_list をソートする必要があると思います。要するに、シンプルでエレガントで、啓発的で明快な何かがそこにあると確信しています.

乾杯＆ありがとう！

4

5 に答える 5

4

最初にリストを並べ替えてみましたか? 多くのデータベースヒットがありますが、提案したアルゴリズムは機能するはずです。

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 とモッド ID のリストを取得したので、操作する完全なオブジェクトが必要な場合は、それぞれに対して単一のクエリを実行して、各モデルの完全なリストを取得し、dictそれらのルックアップを作成して、彼らのID - それで、ボブはあなたのことわざの父の兄弟だと思います.

于 2008-10-02T06:20:53.227 に答える
2

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

于 2008-10-02T01:58:49.957 に答える
1

パフォーマンスが問題になる場合 (つまり、ページに多数の車が表示されている、またはトラフィックの多いサイト)、非正規化は理にかなっていて、副作用として問題を単純化します。

ただし、多対多の関係を非正規化するのは少し難しいかもしれないことに注意してください。私はまだそのようなコード例に出くわしたことがありません。

于 2008-10-06T08:41:56.680 に答える
1

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

groupby を呼び出す前にリストを並べ替えていませんでした。これは必須です。itertools のドキュメントから:

一般に、イテラブルは同じキー関数ですでにソートされている必要があります。

次に、groupby によって返されるリストを複製しません。繰り返しますが、ドキュメントには次のように記載されています。

返されるグループ自体は、基になる iterable を 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))
于 2008-10-02T07:38:59.593 に答える
0

参考になる回答をありがとうございました。私はこの問題に取り組んできました。「最善の」解決策はまだわかりませんが、いくつかの考えがあります。

私が扱っているデータセットの統計について言及する必要があります。ケースの 75% で 1 つの Mod があります。ケースの 24% では、2 つです。1% のケースでは、ゼロまたは 3 つ以上になります。Mod は多数の Car に適用できますが、各 Mod には少なくとも 1 つの固有の Car があります。

そうは言っても、私は次のようなことを検討しました（ただし実装はしませんでした）：

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

車を乗り換えて

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

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

于 2008-10-07T14:17:42.883 に答える