《Python高性能编程》——列表、元组、集合、字…

2018-06-18 03:07:52来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

  这里的内容仅仅是本人阅读《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的目的是快速实现功能,且代码能够稳定运行。至于优化,所花费的时间可能是产品初创到诞生的数倍时间。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:浅copy与深copy举例

下一篇:正则表达式