如何根据嵌套列表中的元素删除列表列表的重复项

Question

我想从列表列表中删除重复项。对于嵌套列表中的每个第二个元素，第一个元素并不总是唯一的。第一个值对于整个列表列表是唯一的。这些数字在整个列表中只出现一次，但没有排序。

my_list = [[4, 'C'], [1, 'A'], [3, 'B'], [2, 'A'], [5, 'C']]

删除重复项基于嵌套列表中的第二个元素。我需要每个唯一的第二个元素的最小值，例如：

my_unique_list = [[1, 'A'], [3, 'B'], [4, 'C']]

输出的顺序无关紧要。

因此，选择1for 'A'（因为 1 小于 2 from [2, 'A']）、3for 'B'（没有其他值'B'）和4for 'C'（因为 4 小于 5， from [5, 'C']）。

Answer 1

使用字典将唯一字母（第二个值）映射到每个字母的最小值，然后简单地[value, key]从该字典中获取对作为输出：

minimi = {}
inf = float('inf')
for val, key in my_list:
    # float('inf') as default value is always larger, so val is picked
    # if the key isn't present yet.
    minimi[key] = min(val, minimi.get(key, inf))

my_unique_list = [[v, k] for k, v in minimi.items()]

通过使用字典作为中介，您可以在线性时间内过滤输入。

演示：

>>> my_list = [[4, 'C'], [1, 'A'], [3, 'B'], [2, 'A'], [5,'C']]
>>> minimi, inf = {}, float('inf')
>>> for val, key in my_list:
...     minimi[key] = min(val, minimi.get(key, inf))
...
>>> minimi
{'C': 4, 'A': 1, 'B': 3}
>>> my_unique_list = [[v, k] for k, v in minimi.items()]
>>> my_unique_list
[[4, 'C'], [1, 'A'], [3, 'B']]

为什么要关心运行时间？因为随着您输入的增加，您的运行时间也会增加。对于需要 O(N^2)（二次）时间的方法，当您从 1000 个项目增加到 100 万个（大小是 1000 倍）时，您的运行时间将增加 100 万倍！对于 O(N logN) 方法（使用排序的方法），运行时间将增加约 2000 倍，而上述线性方法将花费 1000 倍的时间，随着输入的缩放而线性缩放。

对于大量输入，这可以区分“需要一两个小时”到“需要数百万年”。

这是此方法与 zamir 的排序和设置方法 (O(N logN)) 以及 TJC World 的 Pandas 方法（也是 O(N logN)）之间的时间试验比较：

from string import ascii_uppercase
from functools import partial
from timeit import Timer
import random
import pandas as pd

def gen_data(N):
    return [[random.randrange(1_000_000), random.choice(ascii_uppercase)] for _ in range(N)]

def with_dict(l, _min=min, _inf=float('inf')):
    minimi = {}
    m_get = minimi.get
    for val, key in l:
        minimi[key] = _min(val, m_get(key, _inf))
    return [[v, k] for k, v in minimi.items()]

def with_set_and_sort(l):
    already_encountered = set()
    ae_add = already_encountered.add
    return [i for i in sorted(l) if i[1] not in already_encountered and not ae_add(i[1])]

def with_pandas(l):
    return (
        pd.DataFrame(l)
        .sort_values(by=0)
        .drop_duplicates(1)
        .to_numpy()
        .tolist()
    )

for n in (100, 1000, 10_000, 100_000, 1_000_000):
    testdata = gen_data(n)
    print(f"{n:,} entries:")
    for test in (with_dict, with_set_and_sort, with_pandas):
        count, total = Timer(partial(test, testdata)).autorange()
        print(f"{test.__name__:>20}: {total/count * 1000:8.3f}ms")
    print()

我已经使用了我所知道的所有性能小技巧；通过将它们缓存在循环之外的本地名称中，避免重复查找全局变量和属性。

这输出：

minimi = {}
inf = float('inf')
for val, key in my_list:
    # float('inf') as default value is always larger, so val is picked
    # if the key isn't present yet.
    minimi[key] = min(val, minimi.get(key, inf))

my_unique_list = [[v, k] for k, v in minimi.items()]

因此，只有 100 个输入时，排序方法可能看起来一样快（两种方式都有几毫秒的差异），但是随着输入的增加，这种方法会以加速的速度失去优势。

熊猫在这里在所有方面都输了。数据框是一个很好的工具，但这里是错误的工具。它们是庞大的数据结构，因此对于小输入，它们的高开销将它们置于毫秒范围内，远远落后于其他两个选项。在 10k 个条目时，它开始击败排序和设置方法，但即使数据帧操作高度优化，具有更大输入的排序运行时间的增长仍然无法击败线性方法。