# Introduction-to-Python

**Repository Path**: tangzhihong/Introduction-to-Python

## Basic Information

- **Project Name**: Introduction-to-Python
- **Description**: 学习Python
- **Primary Language**: Python
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2016-11-15
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

#Introduction-to-Python

python基础介绍

1、数据结构

引用于微信公众号Python开发者《Python 中的高级数据结构》一文。
原文链接：
http://mp.weixin.qq.com/s?__biz=MzA4MjEyNTA5Mw==&mid=2652564314&idx=1&sn=db15968a0f7a9f00c9068f1aa3e96bd0&chksm=8464c310b3134a06e623c15b061c53db8a714f1d3a81493421d59d80a0f92cd67b603115ea9f&scene=0#wechat_redirect

在Python中有四种内建的数据结构，分别是List、Tuple、Dictionary以及Set。大部分的应用程序不需要其他类型的数据结构，但若是真需要也有很多高级数据结构可供选择，例如Collection、Array、Heapq、Bisect、Weakref、Copy以及Pprint。本文将介绍这些数据结构的用法，看看它们是如何帮助我们的应用程序的。

1.1 Collections

collections模块包含了内建类型之外的一些有用的工具，例如Counter、defaultdict、OrderedDict、deque以及nametuple。其中Counter、deque以及defaultdict是最常用的类。

1.1.1 Counter()

如果你想统计一个单词在给定的序列中一共出现了多少次，诸如此类的操作就可以用到Counter。

Counter的运用，可见示例程序DataStructureCounter.py。

1.1.2 Deque

Deque是一种由队列结构扩展而来的双端队列(double-ended queue)，队列元素能够在队列两端添加或删除。因此它还被称为头尾连接列表(head-tail linked list)，尽管叫这个名字的还有另一个特殊的数据结构实现。

Deque支持线程安全的，经过优化的append和pop操作，在队列两端的相关操作都能够达到近乎O(1)的时间复杂度。虽然list也支持类似的操作，但是它是对定长列表的操作表现很不错，而当遇到pop(0)和insert(0, v)这样既改变了列表的长度又改变其元素位置的操作时，其复杂度就变为O(n)了。


Deque的运用，可见示例程序DataStructureDeque.py。

1.1.3 Defaultdict

这个类型除了在处理不存在的键的操作之外与普通的字典完全相同。当查找一个不存在的键操作发生时，它的default_factory会被调用，提供一个默认的值，并且将这对键值存储下来。其他的参数同普通的字典方法dict()一致，一个defaultdict的实例同内建dict一样拥有同样地操作。

defaultdict对象在当你希望使用它存放追踪数据的时候很有用。例如，追踪一个单词在字符串中的位置时，参见示例程序DataStructureDefaultdict.py。

1.2 Array

array模块定义了一个很像list的新对象类型，不同之处在于它限定了这个类型只能装一种类型的元素。array元素的类型是在创建并使用的时候确定的。

如果你的程序需要优化内存的使用，并且你确定你希望在list中存储的数据都是同样类型的，那么使用array模块很合适。举个例子，如果需要存储一千万个整数，如果用list，那么你至少需要160MB的存储空间，然而如果使用array，你只需要40MB。但虽然说能够节省空间，array上几乎没有什么基本操作能够比在list上更快。

在使用array进行计算的时候，需要特别注意那些创建list的操作。例如，使用列表推导式(list comprehension)的时候，会将array整个转换为list，使得存储空间膨胀。一个可行的替代方案是使用生成器表达式创建新的array。因为使用array是为了节省空间，所以更倾向于使用in-place操作。

一种更高效的方法是使用enumerate。对于较大的array，这种in-place修改能够比用生成器创建一个新的array至少提升15%的速度。这在示例程序DataStructureArray.py中做了比较。

那么什么时候使用array呢？是当你在考虑计算的因素之外，还需要得到一个像C语言里一样统一元素类型的数组时。

1.3 Heapq

heapq模块使用一个用堆实现的优先级队列。堆是一种简单的有序列表，并且置入了堆的相关规则。

堆是一种树形的数据结构，树上的子节点与父节点之间存在顺序关系。二叉堆(binary heap)能够用一个经过组织的列表或数组结构来标识，在这种结构中，元素N的子节点的序号为2*N+1和2*N+2(下标始于0)。简单来说，这个模块中的所有函数都假设序列是有序的，所以序列中的第一个元素(seq[0])是最小的，序列的其他部分构成一个二叉树，并且seq[i]节点的子节点分别为seq[2*i+1]以及seq[2*i+2]。当对序列进行修改时，相关函数总是确保子节点大于等于父节点。

heapq模块有两个函数nlargest()和nsmallest()，详细的用法见示例程序DataStructureHeapq.py。

1.4 Bisect

bisect模块能够提供保持list元素序列的支持。它使用了二分法完成大部分的工作。它在向一个list插入元素的同时维持list是有序的。在某些情况下，这比重复的对一个list进行排序更为高效，并且对于一个较大的list来说，对每步操作维持其有序也比对其排序要高效。详细用法见示例程序DataStructureBisect.py。