目录

AaronJny

诗酒繁华,书剑天涯。

X

使用python,在保留相对顺序的情况下,对列表去重

在开发工作中,难免会遇到需要在保留相对顺序的情况下,对列表进行去重的需求。今天,就简单讲一下这个。

“在保留相对顺序的情况下,对列表去重”是指什么?请看示例:

给定列表 1:

a = [1,2,2,3,4,4,5,6,7,7]

去重后输出:

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

给定列表 2:

b = [3,3,1,2,9,5,6,6,3,9,8,'a',5,'c','a']

去重后输出:

[3,1,2,9,5,6,8,'a','c']

大概就是这个意思。下面说几种实现思路。

1. 暴力

字面意思,无脑暴力处理,开一个新列表,用来保存去重后的数据。

def duplicate_v1(objs):
    # 开一个新列表,用来保存去重后的数据
    res = []
    # 遍历原始列表
    for obj in objs:
        # 如果这个元素已经在新列表中了
        if obj in res:
            # 就直接忽略,处理下一个
            continue
        # 否则将该元素加入到新列表中
        res.append(obj)
    # 返回新列表
    return res

简单计算一下,假设n=len(objs)这个函数的时间复杂度为 O(n^2),太慢了。

2. 使用集合优化

让我们思考一下,上面的方法可以改进吗?显然是可以的。

在上面的方法中,我们使用了obj in res来判断一个元素是否在新列表中,而在 python 里面,对 list 进行 in 操作属于遍历,时间复杂度为 O(n)。

我们可以使用集合(set)来辅助记录重复数据,这样可以把每次判断的时间复杂度降低到 O(1)~O(logn)。

def duplicate_v2(objs):
    # 开一个新列表,用来保存去重后的数据
    res = []
    # 再开一个集合,用来辅助去重
    assist_set = set()
    # 遍历原始列表
    for obj in objs:
        # 如果这个元素已经在新列表中了(我们使用集合判断)
        if obj in assist_set:
            # 就直接忽略,处理下一个
            continue
        # 否则将该元素加入到新列表中
        res.append(obj)
        # 同时加入到集合里面去
        assist_set.add(obj)
    # 返回新列表
    return res

3. 有序集合、dict、OrderedDict

上面的方法好用吗?我觉得不好用。

一是同时新开了 list 和 set,二是编码繁琐。

大部分情况下,使用空间换时间,都是值得的,所以问题一尚可接受。但编码繁琐,就很让人难受了。有什么优雅的方式吗?

那么这里先提出一个问题,为什么在 2 中,需要同时使用 list 和 set,只是用 set 不行嘛?

很遗憾,答案是不行。因为如果只是用 set 的话,虽然也能够达到去重的效果,但会丢失序列的相对顺序。set 是无序的。

那么问题来了,既然这个问题是由 set 是无序的导致的,那存在有序集合吗?

有序集合是存在的,但 python 标准库中并未实现。但不要沮丧,OrderedDict(有序字典)完全可以实现相关功能。

这里有个小 tips:

从 python 3.6 起,dict 的实现已经默认为有序的,不需要使用 OrderedDict 也可以达到相同的效果。而在 python 3.6 以下的版本,请依然使用 OrderedDict。

这里为了考虑兼容性的问题,使用 OrderedDict 实现。

from collections import OrderedDict


def duplicate_v3(objs):
    # 开一个有序字典
    ordered_dict = OrderedDict()
    # 遍历原始列表
    for obj in objs:
        # 将元素加入到有序字典中,元素作为键,值统一设置为1
        ordered_dict[obj] = 1
    # 将有序字典的键作为列表返回
    return list(ordered_dict.keys())

小 tips2:

有小伙伴可能会问,为什么不写成ordered_dict=OrderedDict({obj:1 for obj in objs}),这样一句话搞定,不是更 Pythonic 吗?
然而,这样写是有风险的,这种写法相当于先创建了 dict,再将 dict 转成了 OrderedDict,而在 python 3.6 以下的版本中 dict 是无序的,可能会导致丢失初始列表的顺序。

当然,如果是使用 python 3.6 及以上版本的话,这么写是完全可以的,还会更简洁。不过,出于兼容性考虑,一般不建议这么写:

# 只能运行在python 3.6+上
def duplicate_v4(objs):
    # 开一个有序字典,对列表进行去重
    ordered_dict = OrderedDict({obj: 1 for obj in objs})
    # 将有序字典的键作为列表返回
    return list(ordered_dict.keys())

甚至,如果有必要的话,你还可以直接这么写:

# 只能运行在python 3.6+上
def duplicate_v5(objs):
    return list({obj: 1 for obj in objs}.keys())

结尾

以上。

我使用 solo 自建了独立的 个人站点https://www.aaronjny.com/ )。
感谢开源项目solo!!!

另外,请大佬们眼熟我,多谢 ~


标题:使用python,在保留相对顺序的情况下,对列表去重
作者:AaronJny
地址:https://aaronjny.com/articles/2019/09/25/1569389591225.html