python list/tuple/dict/set/deque的简单比较、优化和时间复杂度（表格）

客官°小女子只卖身不卖艺 2022-06-01 02:29 65阅读 0赞

\#\#\#\#一、关于增删改查

--------------------

<table> 
 <thead> 
  <tr> 
   <th>序列</th> 
   <th align="center">list</th> 
   <th align="center">tuple</th> 
   <th align="center">dict</th> 
   <th align="center">set</th> 
   <th align="center">deque</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>增加方法</td> 
   <td align="center">append、extend、insert</td> 
   <td align="center">×</td> 
   <td align="center">update</td> 
   <td align="center">add、update</td> 
   <td align="center">append/appendleft、extend/extendleft</td> 
  </tr> 
  <tr> 
   <td>删除方法</td> 
   <td align="center">pop、remove</td> 
   <td align="center">× (tuple只有count和index两个方法)</td> 
   <td align="center">pop、clear(这两个是方法)/del（函数） del dict/dict[key]</td> 
   <td align="center">pop、remove</td> 
   <td align="center">和list类似，但多一个popleft（它和其他的区别在于双端，append/extend/pop都多一个left）</td> 
  </tr> 
  <tr> 
   <td>优点（只是部分）</td> 
   <td align="center">功能相对比较齐全</td> 
   <td align="center">可以生成器，占内存小，安全，遍历速度比list快，可一赋多值</td> 
   <td align="center">查找和插入速度快</td> 
   <td align="center">不用判断重复的元素</td> 
   <td align="center">插入速度快</td> 
  </tr> 
  <tr> 
   <td>缺点</td> 
   <td align="center">相对tuple占内存，查找和insert时间较慢</td> 
   <td align="center">不能添加和更改元素</td> 
   <td align="center">占内存大</td> 
   <td align="center">不能存储可变对象，例如list</td> 
   <td align="center">remove和获取索引的时候比较慢</td> 
  </tr> 
 </tbody> 
</table>

--------------------

\#\#\#\#二、关于时间复杂度

**这里简单说一下相对序列关于时间复杂度的意思：**

> · \*O(1)：*常数级别，意思即时间保持在一个固定的范围内，不会随序列的长度和大小而增长。*  
> · \*O(n)：*线性级别，时间与序列的大小成正比，即序列元素越多，越长，所花时间越多*  
> · \*O(k)：*官网上说，“n”是容器中当前的元素的数量。'k’是参数的值或参数中元素的数量。但是目前我还不太清楚它是什么意思，我看到第一个例子用在了pop上，所以猜测是随它变化，具体求哪位大神能给解释一下*  
> · 还有一些类似O(n log n)和O(n^2) ，你画个图就知道了，具体日后有时间补

--------------------

***注意：***

1.  因为tuple不能增删改，所以这里不做比较。
2.  因为deque只是和list样子相似，但作用和queue相似，看名字就知道了，所以它只能从两端增删，不能从中间增删，它也就没有insert或者update这样的方法。
3.  pop各种方法有些不一样，另外我们知道pop的时候它会返回被删掉的数据。因此，pop我们会分为pop last、pop(index\[list\]/key\[dict\])，但实际上他们的命令都是pop：
    
    1.  **deque**：popleft是其独有，但它的pop不能从指定的位置删
    2.  **list**：list/dict都可以从指定位置删，list简单直接给pop(index)即可
    3.  **set**：set其实有pop，但它既不能指定，且没有所谓最后一个，也是随机，其他得用remove或者discard（区别在于如果元素不存在，前者会报错而后者不会）
    4.  **dict**： 根据官网来看，dict的复杂度平均是O(1)，最坏的结果才是O(n)。只是占内存一些，dict的pop比较特殊：
    5.  **- popitem()**：这个尤其特别，它随机返回并删除字典中的一对键和值。为什么随机呢，因为dict是无序的，没有所谓最后一个
    6.  **- pop(key\[,default\])**：删除字典给定键 key 所对应的值，返回值为被删除的值。key值必须给出。 否则，返回default值。
4.  由于无序序列的存在，设置了中括号标注下哪个方法是对应哪个序列的，这里的中括号不代表索引，这里索引直接用index代替

平均情况下：

<table> 
 <thead> 
  <tr> 
   <th>序列</th> 
   <th>list</th> 
   <th>deque</th> 
   <th>dict</th> 
   <th>set</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>insert</td> 
   <td>√ O(n)</td> 
   <td>×</td> 
   <td>×</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>append</td> 
   <td>√ O(1)</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>appendleft</td> 
   <td>×</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>extend</td> 
   <td>√ O(k)</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>extendleft</td> 
   <td>×</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>add</td> 
   <td>×</td> 
   <td>×</td> 
   <td>×</td> 
   <td>√ O(1)</td> 
  </tr> 
  <tr> 
   <td>update</td> 
   <td>×</td> 
   <td>×</td> 
   <td>√ O(1)</td> 
   <td>√O(1)</td> 
  </tr> 
  <tr> 
   <td>remove</td> 
   <td>√</td> 
   <td>√O(n)</td> 
   <td>×</td> 
   <td>√</td> 
  </tr> 
  <tr> 
   <td>clear</td> 
   <td>×</td> 
   <td>√</td> 
   <td>√</td> 
   <td>√</td> 
  </tr> 
  <tr> 
   <td>del</td> 
   <td>√ O(n)</td> 
   <td>√</td> 
   <td>√ O(1)</td> 
   <td>√</td> 
  </tr> 
  <tr> 
   <td>popleft</td> 
   <td>×</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>pop last（pop()[list]）</td> 
   <td>√ O(1)</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>pop（index[list]/key[dict]）</td> 
   <td>√ O(k)</td> 
   <td>√ O(1)</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>popitem()</td> 
   <td>×</td> 
   <td>×</td> 
   <td>√ O(1)</td> 
   <td>×</td> 
  </tr> 
  <tr> 
   <td>Iteration(迭代)</td> 
   <td>√ O(n)</td> 
   <td>√</td> 
   <td>√ O(n)</td> 
   <td>√ O(n)</td> 
  </tr> 
  <tr> 
   <td>x in s （查找）</td> 
   <td>√ O(n)</td> 
   <td>√ O(n)</td> 
   <td>√ O(1)</td> 
   <td>√ O(1)</td> 
  </tr> 
 </tbody> 
</table>

--------------------

**特点：**

1.  tuple：
    
    1.  tuple可哈希，所以它可转换成dict和set，它做dict时——\{():value\}
    2.  tuple的优点：  
        2.1. 函数返回多个值，  
        2.2. 字符串里有多个元素，如果刚好这些元素处于一个列表或tuple内，可以直接用，但是列表需转换，  
        2.3. 可以快速调换赋值，如a,b = b,a
    3.  定义只有一个元素的tuple时候，必须写成这种格式，即加个逗号， 如a = (1,)，否则默认为进行()的运算。
2.  dict：
    
    1.  dict的最好和平均时间是O(1)，最差是O(n)，set大多和dict差不多。
3.  set：
    
    1.  set存储的元素和dict的key类似，必须是不变对象，所以set不支持存储list/dict（set和list/dict可直接相互转换，但set不能直接包含list/dict对象）。但它可以通过update的方式将list的元素一个个添加到set里，但不支持存在整个list（add是添加单个元素，update是批量）。set 和dict转换只会用到它的key而不是value）
    2.  你在最初set(\[1,2,3\])时，它会转换为\{1,2,3\}。
    3.  不过它转换成list很方便，只需要list(set())即可，而不用遍历set中的元素。
    4.  set(i for i in range(n))比set(\[i for i in range(n)\])要快一些，因为前者用到了生成器，来源于，但是如果要遍历，后者可能更快（参考链接9）
4.  查找（即x in s）：dict，set是常数查找时间（O(1)），list、tuple是线性查找时间（O(n)）

**优化：**

1.  list因为占用的内存会随着元素的增大而增大，所以最好不要用 List 来保存中间结果，而是通过 iterable 对象来迭代。（参考链接）
2.  如果想对list进行remove的操作，尽量使用新list保存符合条件的，append的效率高于remove。
3.  由表3可知，在判断某个元素是否在某个序列中的时候，dict是O(1)，list需要遍历，所以是O(n)，这时候尽量不要用list，能够用字典、set进行存储，尽量不要用lis（对顺序没有要求，允许去重）。如果觉得list和dict转换麻烦，可以用set，set和list的转换比较方便，总之可以避开直接用list。存储的时候似情况而定用list还是set，这样可以省去转换。（如果需要求交集、去重之类的用set最好）

--------------------

***参考：***

1.  基于python2.7，不是完全完整，基于目前所学分析，后面有其他会补充，主要也是为了可观性；
2.  关于时间复杂度，参考：  
    · 英文：https://wiki.python.org/moin/TimeComplexity  
    · 中文：http://www.orangecube.net/python-time-complexity
3.  前四种算是基本数据结构，最后一种是from collections这个内置库，是双向队列。它相当于队列和列表的结合，并且支持两端增删。它其实更常用于和多线程，redis使用，之所以放在这里，是因为它和list的相似性；
4.  关于tuple的优点，知乎有很好的答案：https://www.zhihu.com/question/60574107
5.  关于dict的删除：  
    1). http://www.runoob.com/python/python-dictionary.html  
    2). http://www.iplaypy.com/jinjie/jj116.html
6.  关于dict的插入：https://www.zhihu.com/question/62050494
7.  关于set的删除： http://blog.csdn.net/jcjc918/article/details/9359503
8.  性能比较：https://www.cnblogs.com/cfang90/p/6220956.html
9.  优化建议：http://www.jb51.net/article/56699.htm
10. 算法时间复杂度：https://www.ibm.com/developerworks/cn/linux/l-cn-python-optim/