欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

《Python高性能编程》——列表、元组、集合、字典特性及创建过程

程序员文章站 2022-07-02 14:03:40
这里的内容仅仅是本人阅读《Python高性能编程》后总结的一些知识,用于自己更好的了解Python机制。本人现在并不从事计算密集型工作:人工智能、数据分析等。仅仅只是出于好奇而去阅读这本书。很多人因为Python不能同时使用多颗CPU(全局解释器锁GIL),而觉得它不能实现高性能。书中有很多介绍避开 ......

  这里的内容仅仅是本人阅读《Python高性能编程》后总结的一些知识,用于自己更好的了解Python机制。本人现在并不从事计算密集型工作:人工智能、数据分析等。仅仅只是出于好奇而去阅读这本书。很多人因为Python不能同时使用多颗CPU(全局解释器锁GIL),而觉得它不能实现高性能。书中有很多介绍避开GIL或者Python虚拟机的方式,例如Cython,PyPy等。

首先我们要说一下时间复杂度,可以帮助我们理解CPython编译器怎么干活:

时间复杂度

  在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度, 这里进行归纳一下它们代表的含义:
  这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。比如时间复杂度为O(n),就代表数据量增大几倍,耗时也增大几倍。比如常见的遍历算法。再比如时间复杂度O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。比如冒泡排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n×n次。再比如O(logn),当数据增大n倍时,耗时增大logn倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。O(nlogn)同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
O(1)就是最低的时空复杂度了,也就是耗时/耗空间与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标(不考虑冲突的话)
 
列表和元组
 
1、列表是动态数组,它们可变且可以重设长度(改变其内部元素个数)。
2、元组是静态的数组,它们不可变,且其内部数据一旦创建便无法改变。
3、元组缓存与Python 运行时环境,这以为着我们每次使用元组都无需访问内核去分配内存。
 
当创建的数据量及,达到百万千万级以上,合并多个元组,会比一个列表占用更少的空间。
 
列表在进行append()操作时,会Copy原列表,创建一个更大的列表,然后销毁原列表。在append时,编译器会预创建一部分数据空间,用于以后的添加。
元组在进行合并操作(+)时,会创建一个新的元组,然后销毁旧的元组,元组数据集前后不会发生改变
 
字典和集合
 
字典和集合适合于存储能够被索引的数据。当你在使用字典和集合处理可以索引的数据时它的时间复杂度是O(1),但是对于那些不能被索引的数据是徒劳无功的。
 
  字典与集合在CPython创建时,会像系统申请定量内存块默认最小长度是8,每次改变大小增加到原来的4倍。每次插入数据时会生成索引(二进制数),会在申请的内存存储块中随机插入,如果目标存储块已有数据,那就换个位置,这叫做散列碰撞。
 
由于字典与集合在插入数据不是每一次都会扩增集合体积,所以会比列表效率高效、省内存空间。虽然会有散列碰撞,但是每次散列碰撞都是二进制数的比较。
 
集合:在对一批数据进行去重时,不如把这批数据放入集合中。因为在你使用列表存储这批数据时,你需要手动判断是否重复,而且列表会预创建空桶用于存接下来的数据。而集合是一个纯Key的数组,里面的数据时唯一的。
 
字典:是key:value的形式存储
 
散列函数:在散列函数中会对字典和列表生成二进制数作为掩码(可以理解为索引,因为在插入、查询时是依靠这个值)。
 
  应该有一种——而且最好只有唯一的一种——明显的方式去完成它。虽然这种方式可能一开始并不明显,除非你是荷兰人。
——Tim Peters
Python之禅
使用Python的目的是快速实现功能,且代码能够稳定运行。至于优化,所花费的时间可能是产品初创到诞生的数倍时间。