Pythonic方法删除列表中的反向重复项

Question

我有一对配对列表:

[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]

我想删除任何重复的地方

[a,b] == [b,a]

所以我们最终只是

[0, 1], [0, 4], [1, 4]

我可以做一个内部和外部循环检查反向对,并附加到列表,如果不是这样,但我敢肯定有更多的Pythonic方式来实现相同的结果.

Answer 1

如果你需要保留列表中元素的顺序,那么你可以使用sorted函数和set comprehension,map如下所示:

lst = [0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]
data = {tuple(item) for item in map(sorted, lst)}
# {(0, 1), (0, 4), (1, 4)}

或者根本没有map这样:

data = {tuple(sorted(item)) for item in lst}

另一种方法是使用frozenset如此处所示的,但请注意,这仅在列表中包含不同元素时才有效.因为喜欢set, frozenset总是包含唯一的值.因此,您最终会在子列表中丢失唯一的值(丢失数据),这可能不是您想要的.

要输出列表,您始终可以使用list(map(list, result))结果只是在Python-3.0或更新版本中的一组元组.

Answer 2

如果您只想删除反向对并且不想要外部库,则可以使用简单的生成器函数(基于itertools "unique_everseen"配方):

def remove_reversed_duplicates(iterable):
    # Create a set for already seen elements
    seen = set()
    for item in iterable:
        # Lists are mutable so we need tuples for the set-operations.
        tup = tuple(item)
        if tup not in seen:
            # If the tuple is not in the set append it in REVERSED order.
            seen.add(tup[::-1])
            # If you also want to remove normal duplicates uncomment the next line
            # seen.add(tup)
            yield item

>>> list(remove_reversed_duplicates(a))
[[0, 1], [0, 4], [1, 4]]

生成器函数可能是解决此问题的一种非常快速的方法,因为set-lookups非常便宜.这种方法也使您的初始列表的顺序,只删除重复反转,同时快比大多数替代品!

如果您不介意使用外部库并且想要删除所有重复项(反向和相同),则替代方法是: iteration_utilities.unique_everseen

>>> a = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]

>>> from iteration_utilities import unique_everseen

>>> list(unique_everseen(a, key=set))
[[0, 1], [0, 4], [1, 4]]

这将检查任何项目是否具有与其他项目相同的仲裁顺序(因此key=set).在这种情况下,这可以按预期工作,但它也删除重复[a, b]而不是仅[b, a]发生.你也可以使用key=sorted(像其他答案一样).在unique_everseen这样有一个不好的算法复杂度,因为结果key函数不是哈希的,因此快速查找被一慢的查找替换.为了加快这一点,你需要使密钥可以清洗,例如将它们转换为已排序的元组(如其他一些答案所示):

>>> from iteration_utilities import chained
>>> list(unique_everseen(a, key=chained(sorted, tuple)))
[[0, 1], [0, 4], [1, 4]]

该chained不是别的,只是以一个更快的替代方案lambda x: tuple(sorted(x)).

编辑:正如@ jpmc26所提到的,可以使用frozenset而不是普通集:

>>> list(unique_everseen(a, key=frozenset))
[[0, 1], [0, 4], [1, 4]]

为了了解性能,我timeit对不同的建议进行了一些比较:

>>> a = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]

>>> %timeit list(remove_reversed_duplicates(a))
100000 loops, best of 3: 16.1 µs per loop
>>> %timeit list(unique_everseen(a, key=frozenset))
100000 loops, best of 3: 13.6 µs per loop
>>> %timeit list(set(map(frozenset, a)))
100000 loops, best of 3: 7.23 µs per loop

>>> %timeit list(unique_everseen(a, key=set))
10000 loops, best of 3: 26.4 µs per loop
>>> %timeit list(unique_everseen(a, key=chained(sorted, tuple)))
10000 loops, best of 3: 25.8 µs per loop
>>> %timeit [list(tpl) for tpl in list(set([tuple(sorted(pair)) for pair in a]))]
10000 loops, best of 3: 29.8 µs per loop
>>> %timeit set(tuple(item) for item in map(sorted, a))
10000 loops, best of 3: 28.5 µs per loop

包含许多重复项的长列表:

>>> import random
>>> a = [[random.randint(0, 10), random.randint(0,10)] for _ in range(10000)]

>>> %timeit list(remove_reversed_duplicates(a))
100 loops, best of 3: 12.5 ms per loop
>>> %timeit list(unique_everseen(a, key=frozenset))
100 loops, best of 3: 10 ms per loop
>>> %timeit set(map(frozenset, a))
100 loops, best of 3: 10.4 ms per loop

>>> %timeit list(unique_everseen(a, key=set))
10 loops, best of 3: 47.7 ms per loop
>>> %timeit list(unique_everseen(a, key=chained(sorted, tuple)))
10 loops, best of 3: 22.4 ms per loop
>>> %timeit [list(tpl) for tpl in list(set([tuple(sorted(pair)) for pair in a]))]
10 loops, best of 3: 24 ms per loop
>>> %timeit set(tuple(item) for item in map(sorted, a))
10 loops, best of 3: 35 ms per loop

并且重复次数较少:

>>> a = [[random.randint(0, 100), random.randint(0,100)] for _ in range(10000)]

>>> %timeit list(remove_reversed_duplicates(a))
100 loops, best of 3: 15.4 ms per loop
>>> %timeit list(unique_everseen(a, key=frozenset))
100 loops, best of 3: 13.1 ms per loop
>>> %timeit set(map(frozenset, a))
100 loops, best of 3: 11.8 ms per loop


>>> %timeit list(unique_everseen(a, key=set))
1 loop, best of 3: 1.96 s per loop
>>> %timeit list(unique_everseen(a, key=chained(sorted, tuple)))
10 loops, best of 3: 24.2 ms per loop
>>> %timeit [list(tpl) for tpl in list(set([tuple(sorted(pair)) for pair in a]))]
10 loops, best of 3: 31.1 ms per loop
>>> %timeit set(tuple(item) for item in map(sorted, a))
10 loops, best of 3: 36.7 ms per loop

因此,与变体remove_reversed_duplicates,unique_everseen(key=frozenset),并set(map(frozenset, a))似乎是迄今为止速度最快的解决方案.哪一个取决于输入的长度和重复的数量.

Answer 3

TL; DR

set(map(frozenset, lst))

说明

如果这些对在逻辑上是无序的,则它们更自然地表示为集合.在你达到这一点之前把它们作为集合会更好,但是你可以像这样转换它们:

lst = [[0, 1], [0, 4], [1, 0], [1, 4], [4, 0], [4, 1]]
lst_as_sets = map(frozenset, lst)

然后,在迭代中消除重复的自然方法是将其转换为set:

deduped = set(lst_as_sets)

(这是我frozenset在第一步中选择的主要原因.Mutable sets不可清除,因此无法添加到set.)

或者你可以在TL; DR部分中的单行中完成.

我认为这更简单,更直观,与您对数据的思考方式更加匹配,而不是与排序和元组混淆.

转换回来

如果由于某种原因,你真的需要list的listS作为最终结果,转换回很简单:

result_list = list(map(list, deduped))

但是,set尽可能长时间地保留它可能更合乎逻辑.我只能想到你可能需要这个的一个原因,那就是与现有代码/库的兼容性.