0

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

我有一组无序的Data对象，并且想要检索n最高的对象rank- 但每个等价类最多有一个对象。

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

我的第一种方法看起来像这样：

  • 按降序对列表进行排序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) }
4

4 回答 4

1

您可以使用itertools.groupby（文档）。首先，我们按照您的标准对项目进行排序，然后按标签对它们进行分组（并且只存储每个组中的第一个项目）：

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

编辑：更改了排序键。

于 2019-07-20T21:32:18.810 回答
1

将排序后的输入存储在 a 中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)}
于 2019-07-20T22:40:55.960 回答
1

我认为取每个组的O(|elements|)最大元素（O(|groups|.lg n)nO(|elements|.lg |elements|)nO(|elements|)

创建一个字典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)]
于 2019-07-20T22:04:04.473 回答
0

如果它是您控制的类定义，我相信最 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]

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

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

于 2019-07-20T21:41:55.900 回答