从列表中删除重复元组，取决于元组中的值。

Question

我有一个元组列表，每个元组包含2个元素：

• 第1个元素是一个包含一些数字的元组，例如(1, 4, 2)。事实上这是一条路径，其中的数字是节点的ID。
• 第2个元素是一个数字，表示该路径的得分。

例如，列表可能为：

pathList = [
    ((1, 2),    4),
    ((1, 4, 2), 2),
    ((1, 2),    6),
    ((1, 2),    3),
    ((1, 4, 2), 3)
]

现在我想要移除具有相同路径（第一个元素）的元组，同时保留其中得分最高的元组（第二个元素）。

例如，在此过程之后，pathList应该是这样的：

pathList = [
    ((1, 2),    6),
    ((1, 4, 2), 3)
]

顺序不重要。

有没有一种高效的方法来完成它？

- Roger Wu

Answer 1

你可以使用字典（dict.setdefault 方法）将路径作为键和相对分数作为值的集合（添加值的复杂度为O(1)）进行保存，然后选择每个唯一路径的最大分数：

>>> pathList = [
...     ((1, 2),    4),
...     ((1, 4, 2), 2),
...     ((1, 2),    6),
...     ((1, 2),    3),
...     ((1, 4, 2), 3)
... ]
>>> 
>>> d={}
>>> for i,j in pathList:
...   d.setdefault(i,set()).add(j)
... 
>>> [(i,max(j)) for i,j in d.items()]
[((1, 2), 6), ((1, 4, 2), 3)]

- Mazdak

---

O(1)复杂度用于添加值 - 即使使用列表的原始版本，由于使用了“append”，其添加值的复杂度也为O(1)。 - thefourtheye

@thefourtheye 的确，但是调用 list.append 比 set.add() 花费更多的时间。 - Mazdak

Answer 2

或者您可以使用 Pandas 和 groupby：

import pandas as pd

pathList = [
    ((1, 2),    4),
    ((1, 4, 2), 2),
    ((1, 2),    6),
    ((1, 2),    3),
    ((1, 4, 2), 3)
]

df = pd.DataFrame(pathList, columns=["elements", "occurences"])

max_only = []

for name, group in df.groupby("elements"):
    max_only.append([name, group.occurences.max()])

print max_only

- mattions

Answer 3

我认为 Python 最好的一点是脚本总是可以很简单，这里我只是在对列表进行排序。

newPathList =[]
pathList = sorted(pathList, reverse =True)
oldx = 0
for i in pathList:
    x,y = i
    if x!= oldx:
        newPathList.append(i)
        oldx = x
print newPathList

- Sujay Narayanan