Python 3.8中dict.fromkeys()时间复杂度及有序集合最优实现问询

一、dict.fromkeys()的时间复杂度 #

dict.fromkeys()的时间复杂度为O(n)，其中n是输入列表的长度。它会遍历列表中的每个元素一次，而字典的哈希表结构保证了每次添加键的操作平均时间复杂度为O(1)，因此整体是线性时间开销。

二、是否为最高效的实现方案？ #

在Python 3.8中，dict.fromkeys()已经是获取保留插入顺序的唯一元素的高效方案之一，不过也有其他可选方案，可根据场景选择：

• 当前使用的dict.fromkeys() + 转列表：这是最简洁的写法，底层基于Python内置的C实现，执行速度快，适合绝大多数常规场景。
• collections.OrderedDict：在Python 3.7之前，普通字典不保证插入顺序，OrderedDict是官方推荐的有序字典实现；但3.7+之后普通字典已默认保留顺序，OrderedDict仅在需要move_to_end等特殊方法时才有优势。用它去重的写法稍繁琐，效率和普通字典相近：

  from collections import OrderedDict
  lst = [4,2,4,5,6,2]
  unique_lst = list(OrderedDict.fromkeys(lst))
  

• 手动遍历去重：自行维护集合记录已出现元素，同时用列表保存结果，时间复杂度同样是O(n)，但因为是纯Python代码实现，速度会比内置的C实现慢：

  lst = [4,2,4,5,6,2]
  seen = set()
  unique_lst = []
  for item in lst:
      if item not in seen:
          seen.add(item)
          unique_lst.append(item)
  

总结 #

如果你的需求只是单纯的去重并保留插入顺序，dict.fromkeys()是Python 3.8里的最优选择之一，代码简洁且性能优异，频繁使用完全没问题。

内容的提问来源于stack exchange，提问作者Mohammad Rifat Arefin