理解Python各种顺序容器

Last Updated: 2023-05-03 07:31:14 Wednesday

-- TOC --

list，array和deque性能测试比较
使用array时的数据转换
比较array与bytes和bytearray
理解deque的thread-safe

不同的数据结构在进行同样操作的时候，性能有所不同。我们应该根据业务场景选择最适合的数据结构。虽然都是顺序存储类结构，但C++中还是有vector，list和array的区分，同样在Python中，也有list，tuple，array，bytes，bytearray，以及deque的不同。

简要总结一下Python内各种顺序容器的特点和应用场景。

名称	.	.	Commments
`list`	mutable, container		最常用的万能型顺序容器，支持\(O(1)\)任意访问，可以对应C++的vector。没有对内部元素数据类型一致性的强制要求。尾部的操作很快，但在头部做insert就比较慢了。适合快速的固定长度的操作。
`tuple`	immutable, container		不仅仅是immutable list，tuple常常被用来当做各种record数据使用，each item in tuple holds the data for one field, and the position of the item gives its meaing.
`collections.namedtuple`	immutable/container		Named tuples assign meaning to each position in a tuple and allow for more readable, self-documenting code. They can be used wherever regular tuples are used, and they add the ability to access fields by name instead of position index.
`array.array`	mutable, flat		类似list，Efficient arrays of numeric values. This module defines an object type which can compactly represent an array of basic values: characters, integers, floating point numbers. Arrays are sequence types and behave very much like lists, except that the type of objects stored in them is constrained. 支持存放基础数据类型，要求元素类型一致，内存消耗与存放数据类型有关，比list少。
`bytearray`	mutable, flat		array of byte，Python专门针对byte对象优化的array，性能比`array('b',[])`更好。
`bytes`	immutable, flat
`str`	immutable, flat		存放Unicode编码的字符
`collections.deque`	mutable, container	thread-safe	双端队列，可以对应C++的list，虽然任意位置访问是\(O(n)\)级别，但在头部操作速度极快。deque并非内置，需要import，`from collections import deque`。可以指定maxlen。（The deque's append(), appendleft(), pop(), popleft(), and len(d) operations are thread-safe in CPython）
`queue.Queue`	mutable, container	thread-safe	实现建立在deque基础上，因此比deque慢一点。The Queue is slowed down a bit through locks, function indirection, and additional features such as maxsize, join, and task_done.

Python标准库中的collections模块中全是各种container。

list，array和deque性能测试比较

append(x)

测试在尾部添加元素，即append操作。

>>> tcode = """\
... for i in range(1000):
...     a.append(i)
... """
>>>
>>> sum(repeat(tcode, setup="a=[]", timer=time.process_time, number=10000))/5
0.6905808886000001
>>> sum(repeat(tcode, setup="from array import array;a=array('i',[])", timer=time.process_time, number=10000))/5
1.3353027202000003
>>> sum(repeat(tcode, setup="from collections import deque;a=deque()", timer=time.process_time, number=10000))/5
0.7210645022000008

repeat默认重复5次。

list最快，deque次之，但非常接近，array要慢一些，但都在一个数量级上，差距不算特别大。

insert(0,x)

测试在头部添加元素，即在index=0的位置做insert。

>>> tcode02 = """\
... for i in range(1000):
...     a.insert(0,i)
... """
>>>
>>> sum(repeat(tcode02, setup="a=[]", timer=time.process_time, number=100))/5
2.1469489754000035
>>> sum(repeat(tcode02, setup="from array import array;a=array('i',[])", timer=time.process_time, number=100))/5
0.9068540007999986
>>> sum(repeat(tcode02, setup="from collections import deque;a=deque()", timer=time.process_time, number=100))/5
0.011628347800001392

deque由于数据结构非常适合在头部做insert，它的速度超快！array比list要快一些，但与deque相比，完全不在一个数量级上。

>>> sum(repeat(tcode02, setup="a=[]", timer=time.process_time, number=200))/5
9.177822828399963
>>> sum(repeat(tcode02, setup="from array import array;a=array('i',[])", timer=time.process_time, number=200))/5
4.232576406399971
>>> sum(repeat(tcode02, setup="from collections import deque;a=deque()", timer=time.process_time, number=200))/5
0.022309611000014228

测试代码的特点，每次for迭代，a并没有被清空，因此number越大，a就越长。当把number从100增加到200后，可以看到，只有deque的执行时间是线性增加的，list和array的耗时增加，都是非线性的。因为a越长，每次在头部insert，需要移动的数据量就越大！

使用array时的数据转换

在访问array容器中的数据时，存在一种转换，从C primitive type转Python type，多种C primitive type转成Python的int或float。这种转换有一定消耗。

>>> timeit('t = a[1]', setup='a=[1,2,3]',timer=time.process_time, number=int(1e9), globals=globals())
15.515625
>>> timeit('t = a[1]', setup="a=array('i',[1,2,3])",timer=time.process_time, number=int(1e9), globals=globals())
19.75

比较array与bytes和bytearray

先看一下各自的内存占用情况：

>>> sys.getsizeof(bytes(10000))
10033
>>> sys.getsizeof(bytearray(10000))
10057
>>> ab = array('b',[])
>>> ab.frombytes(bytes(10000))
>>> sys.getsizeof(ab)
11774

bytes和bytearray比array稍好一些。

再来看看速度，此时只能跟bytearray比较。

append

>>> tcode03 = """\
... for i in range(127):
...     a.append(i)
... """
>>>
>>> sum(repeat(tcode03, setup="a=bytearray()", number=100000))/5
0.7459419548511506
>>> sum(repeat(tcode03, setup="from array import array;a=array('b',[])", number=100000))/5
1.5112565837800502

bytearray更快一些，不愧是专门为byte数据优化过的。

insert(0,x)

>>> tcode04 = """\
... for i in range(127):
...     a.insert(0,i)
... """
>>>
>>> sum(repeat(tcode04, setup="a=bytearray()", number=1000))/5
0.28905207812786105
>>> sum(repeat(tcode04, setup="from array import array;a=array('b',[])", number=1000))/5
0.303518009185791

在头部的insert，耗时差不多，但还是bytearray要快一丢丢。

理解deque的thread-safe

只有获取了GIL锁的线程才能操作Python对象或调用Python/C API。

CPython解释器每执行若干条python指令（缺省值100）后会尝试做线程切换（释放GIL）。注意这跟用Python/C API实现的函数不同，C函数中如果没有主动释放GIL，是不会有机会切走的。

deque的那几个接口实现，是C代码，在C代码中，没有释放GIL的机制。

要看源码呀....

本文链接：https://cs.pynote.net/sf/python/202212082/

-- EOF --

-- MORE --