在 Python 中用类等价排序

Question

假设我有一个自定义数据结构 Data，它揭示了两个相关属性：tag 表示该项目属于哪个等价 class，rank 表示有多好此项是。

我有一组无序的 Data 个对象，我想检索具有最高 rank 的 n 个对象——但每个等价项最多有一个对象 class.

(相同等价class的对象不一定比较相等，也不一定相同rank，但我不希望输出中的任何两个元素来自同一个 class。换句话说，产生这些等价 class 的关系不是 ==。）

我的第一个方法是这样的：

按降序排列列表 rank
创建空集s
对于列表中的每个元素：
- 检查它的 tag 是否在 s 中；如果是，继续前进
- 将其 tag 添加到 s
- 产生该元素
- 如果我们已经生成 n 个元素，请停止

然而，这感觉很尴尬，好像应该有更好的方法（可能使用 itertools 和高阶函数）。结果 n 元素的顺序并不重要。

这个问题的 Pythonic 解决方案是什么？

玩具示例：

Data = namedtuple('Data', ('tag', 'rank'))
n = 3

algorithm_input = { Data('a', 200), Data('a', 100), Data('b', 50), Data('c', 10), Data('d', 5) }
expected_output = { Data('a', 200), Data('b', 50), Data('c', 10) }

Answer 1

您可以使用 itertools.groupby (doc)。首先，我们根据您的标准对项目进行排序，然后按标签对它们进行分组（并且仅存储每组中的第一项）：

from itertools import groupby
from collections import namedtuple

Data = namedtuple('Data', ('tag', 'rank'))

n = 3

algorithm_input = { Data('a', 200), Data('a', 100), Data('b', 50), Data('c', 10), Data('d', 5) }

# 1. sort the data by rank (descending) and tag (ascending)
s = sorted(algorithm_input, key=lambda k: (-k.rank, k.tag))

# 2. group the data by tag and store first item from each group to 'out', limit the number of groups to 'n'
out = []
for (_, g), _ in zip(groupby(s, lambda k: k.tag), range(n)):
    out.append(next(g))

print(out)

打印：

[Data(tag='a', rank=200), Data(tag='b', rank=50), Data(tag='c', rank=10)]

编辑：更改了排序键。

Answer 2

如果它是您控制的 class 定义，我相信最 Pythonic 的方式是这样的：

from random import shuffle

class Data:

    def __init__(self, order=1):
        self.order = order

    def __repr__(self):
        return "Order: " + str(self.order)

if __name__ == '__main__':
    import sys
    d = []
    for i in range(0,10):
        d.append(Data(order=i))
    shuffle(d)

    print(d)

    print(sorted(d, key=lambda data: data.order))

输出：

[Order: 5, Order: 2, Order: 6, Order: 0, Order: 4, Order: 7, Order: 3, Order: 9, Order: 1, Order: 8]
[Order: 0, Order: 1, Order: 2, Order: 3, Order: 4, Order: 5, Order: 6, Order: 7, Order: 8, Order: 9]

因此，从本质上讲，添加一个属性作为 class 的排序依据。定义字符串 rep（只是为了更容易看到发生了什么）。然后在具有 lambda 函数的那些对象的列表上使用 python 的 sorted() 来指示应该对每个对象进行排序的属性。

注意：必须定义该属性类型的比较 - 这里是一个 int。如果未定义属性，则必须为该属性实现 gt、let 等。有关详细信息，请参阅 docs。

Answer 3

创建一个字典 max_by_tag 来存储具有标签最高排名的项目：

>>> from collections import namedtuple
>>> Data = namedtuple('Data', ('tag', 'rank'))
>>> n = 3
>>> algorithm_input = { Data('a', 200), Data('a', 100), Data('b', 50), Data('c', 10), Data('d', 5) }
>>> max_by_tag = {}
>>> for item in algorithm_input:
...     if item.tag not in max_by_tag or item.rank > max_by_tag[item.tag].rank:
...         max_by_tag[item.tag] = item

>>> max_by_tag
{'a': Data(tag='a', rank=200), 'b': Data(tag='b', rank=50), 'c': Data(tag='c', rank=10), 'd': Data(tag='d', rank=5)}

然后使用heapq模块：

>>> import heapq
>>> heapq.nlargest(n, max_by_tag.values(), key=lambda data: data.rank)
[Data(tag='a', rank=200), Data(tag='b', rank=50), Data(tag='c', rank=10)]

Answer 4

将排序后的输入存储在OrderedDict中（以tag为键，Data为值）。这将导致每个等效 class 中只有一个 Data 存储在 OrderedDict

中

>>> from collections import namedtuple, OrderedDict
>>> Data = namedtuple('Data', ('tag', 'rank'))
>>> n = 3
>>> algorithm_input = { Data('a', 200), Data('a', 100), Data('b', 50), Data('c', 10), Data('d', 5) }
>>> 
>>> set(list(OrderedDict((d.tag, d) for d in sorted(algorithm_input)).values())[:n])
{Data(tag='b', rank=50), Data(tag='a', rank=200), Data(tag='c', rank=10)}

在 Python 中用类等价排序

Sorting with equivalence classes in Python

python

sorting

algorithm

equivalence-classes

这个问题的 Pythonic 解决方案是什么？

在 Python 中用 类 等价排序

Sorting with equivalence classes in Python

python

sorting

algorithm

equivalence-classes

这个问题的 Pythonic 解决方案是什么？

在 Python 中用类等价排序