8

这是部分算法逻辑问题（如何做），部分实施问题（如何做到最好！）。我正在与 Django 一起工作，所以我想我会与它分享。

在 Python 中，值得一提的是，该问题与how-do-i-use-pythons-itertoolsgroupby有点相关。

假设你有两个 Django 模型派生类：

from django.db import models

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

和

from django.db import models

class Mods(models.Model):
   ...

一个人如何获得一个汽车列表，按汽车和一组通用的 Mod 分组？

即我想像这样上课：

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 集分组。我猜必须对 mod_list 进行排序才能与 groupby 一起使用。总而言之，我相信那里有一些简单而优雅的东西，既具有启发性又具有启发性。

干杯&谢谢！

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 和 mod id 的列表，如果您需要使用完整的对象，您可以为每个对象执行一个查询以获得每个模型的完整列表并dict为这些对象创建一个查找，由他们的身份证——那么，我相信，鲍勃是你众所周知的父亲的兄弟。

于 2008-10-02T06:20:53.227 回答
2

检查重组。它仅适用于模板，但我想这种分类无论如何都属于表示层。

于 2008-10-02T01:58:49.957 回答
1

你在这里有几个问题。

在调用 groupby 之前您没有对列表进行排序，这是必需的。从itertools 文档：

通常，iterable 需要已经在相同的 key 函数上排序。

然后，您不会复制 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))
于 2008-10-02T07:38:59.593 回答
1

如果性能是一个问题（即一个页面上有很多汽车，或者一个高流量的站点），非规范化是有意义的，并将您的问题简化为副作用。

请注意，非规范化多对多关系可能有点棘手。我还没有遇到任何这样的代码示例。

于 2008-10-06T08:41:56.680 回答
0

谢谢大家的有用回复。我一直在解决这个问题。一个“最好的”解决方案仍然让我望而却步，但我有一些想法。

我应该提到我正在使用的数据集的统计数据。在 75% 的情况下，会有一个 Mod。在 24% 的情况下，两个。在 1% 的情况下，将有 0 个或三个或更多。对于每个 Mod，至少有一辆独特的汽车，尽管一个 Mod 可以应用于许多汽车。

话虽如此，我已经考虑过（但未实施）类似的事情：

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 回答