python - 根据内部列表元素的比较从列表列表中删除重复项

Question

我有一个很大的列表列表，需要根据特定条件删除重复元素:

1. 唯一性由列表的第一个元素决定。
2. 去除重复是通过比较重复列表的第二个元素的值来确定的，即保留列表中第二个元素最低的列表。

[[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 实现这一点的见解吗？

Answer 1

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

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 :

A SortedDict provides the same methods as a dict. Additionally, a SortedDict efficiently maintains its keys in sorted order. Consequently, the keys method will return the keys in sorted order, the popitem method will remove the item with the highest key, etc.

An optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each dict key. If no function is specified, the default compares the dict keys directly. The key argument must be provided as a positional argument and must come before all other arguments.

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等..