基于内部列表元素比较，从一个列表的列表中删除重复项

Question

基于内部列表元素比较，从一个列表的列表中删除重复项

python

6

我有一个包含多个列表的大列表，需要根据特定条件删除重复元素：

唯一性是由列表的第一个元素决定的。
删除重复项是通过比较重复列表的第二个元素的值来确定的，即保留第二个元素最小的列表。

[[1, 4, 5], [1, 3, 4], [1, 2, 3]]

由于它们的第一个元素相等，上述所有列表都被视为重复。需要保留第三个列表，因为它的第二个元素是最小的。请注意，实际的列表包含超过400万个元素，已经进行了双重排序，需要保留顺序。

该列表首先基于内部列表的第二个元素进行排序，并以相反（降序）顺序排序，然后按照第一个元素的正常（升序）顺序排序：

sorted(sorted(the_list, key=itemgetter(1), reverse=True), key=itemgetter(0))

以下是三个重复列表的实际排序示例：

[...
[33554432, 50331647, 1695008306],
[33554432, 34603007, 1904606324],
[33554432, 33554687, 2208089473],
...]

目标是为二分搜索准备列表。有人能够提供使用Python实现这个目标的见解吗？

- Aaron

如果第一个和第二个元素相等会发生什么？ - SiHa

第一和第二元素分别代表一个范围的起始和结束。所有重复的元素要么是另一个范围的超集，要么是它的子集。不应该有两个或更多的重复元素，它们的第一元素相等且第二元素相等。然而，可能会有具有相等第一和第二元素的单独子列表，表示范围为1，但它们从不出现两次，因为特定的范围始终是唯一的。 - Aaron

2个回答

1

如果我理解正确，解决方案可能是这样的：

mylist = [[1, 2, 3], [1, 3, 4], [1, 4, 5], [7, 3, 6], [7, 1, 8]]

ordering = []
newdata = {}

for a, b, c in mylist:
    if a in newdata:
        if b < newdata[a][1]:
            newdata[a] = [a, b, c]
    else:
        newdata[a] = [a, b, c]
        ordering.append(a)

newlist = [newdata[v] for v in ordering]

因此，在newlist中，我们将收到缩小后的列表[[1, 2, 3]，[7, 1, 8]]。

- baldr

当你将键存储在字典中时，为什么要使用列表？ - Padraic Cunningham

我没有进行测量，但我认为list可能比OrderedDict更快。请参阅https://dev59.com/iGsz5IYBdhLWcg3wADIm - baldr

另一方面，在字典的键中查找元素会更快，感谢这个想法，我会稍微修改代码。 - baldr

一个字典查找的时间复杂度是O(1)，而列表扫描的时间复杂度是O(n)。如果你已经拥有所有键来进行查找，那么如果它在字典中，它也一定在列表中。 - Padraic Cunningham

我不再在列表中进行查找。ordering 是一个只添加元素的列表，用于保持元素的顺序。它只被迭代一次。看看 Python 中 OrderedDict 的实现 - 我不确定它是否更快。 - baldr

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Padraic Cunningham · Accepted Answer

你可以使用字典对元素进行分组，始终保持第二个元素较小的子列表:

l = [[1, 2, 3], [1, 3, 4], [1, 4, 5], [2, 4, 3], [2, 5, 6], [2, 1, 3]]
d = {}
for sub in l:
    k = sub[0]
    if k not in d or sub[1] < d[k][1]:
        d[k] = sub

此外，您可以将两个键传递给sorted，而无需调用两次sorted：

In [3]:  l = [[1,4,6,2],[2,2,4,6],[1,2,4,5]]
In [4]: sorted(l,key=lambda x: (-x[1],x[0]))
Out[4]: [[1, 4, 6, 2], [1, 2, 4, 5], [2, 2, 4, 6]]

如果您希望按照顺序保留字典中的顺序，可以这样做：

需要保留顺序。

from collections import OrderedDict

l = [[1, 2, 3], [1, 3, 4], [1, 4, 5], [2, 4, 3], [2, 5, 6], [2, 1, 3]]
d = OrderedDict()
for sub in l:
    k = sub[0]
    if k not in d or sub[1] < d[k][1]:
        d[sub[0]] = sub

但是不确定如何适应排序数据，因为您在排序之后将失去任何顺序。

您可能会发现sortedcontainers.sorteddict非常有用：

SortedDict提供与dict相同的方法。此外，SortedDict有效地维护其键以排序顺序。因此，keys方法将按排序顺序返回键，popitem方法将删除具有最高键的项等。

可选的key参数定义一个可调用对象，例如Python的sorted函数的key参数，从每个dict键中提取比较键。如果未指定函数，则默认直接比较dict键。key参数必须作为位置参数提供，并且必须位于所有其他参数之前。

from sortedcontainers import SortedDict

l = [[1, 2, 3], [1, 3, 4], [1, 4, 5], [2, 4, 3], [2, 5, 6], [2, 1, 3]]
d = SortedDict()
for sub in l:
    k = sub[0]
    if k not in d or sub[1] < d[k][1]:
        d[k] = sub


print(list(d.values()))

它包含了你所需要的所有方法，例如bisect，bisect_left等。