Python中等价类的排序

Question

假设我有一个定制的数据结构Data，它显示了两个相关的属性：tag表示这个项属于哪个等价类，rank表示这个项有多好。你知道吗

我有一个无序的Data对象集，希望检索具有最高rank的n对象，但每个等价类中最多有一个对象。你知道吗

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

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

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

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

这个问题的解药是什么？

玩具示例：

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

我认为取每个组的max元素（O(|elements|)），然后取n个最大的列（O(|groups|.lg n)，堆的大小是n），而不是先排序（O(|elements|.lg |elements|)），然后取n元素（O(|elements|)）：

创建一个dictmax_by_tag，用于存储带有max rank by标记的项：

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

然后使用^{}模块：

>>> 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 2

您可以使用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 3

将排序后的输入存储在OrderedDict（以tag作为键，Data作为值）。这将导致每个等价类中只有一个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)}