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

╰+攻爆jí腚メ 2023-10-09 11:42 5阅读 0赞

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

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

给定列表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())

## 结尾 ##

以上。

除csdn个人博客外，我使用solo自建了独立的 [个人站点][Link 1]（ https://www.aaronjny.com/ ）。  
感谢开源项目[solo][]！！！

另外，请大佬们眼熟我，多谢～

[Link 1]: https://www.aaronjny.com/
[solo]: https://github.com/b3log/solo