## 1.基础

时序数据TimeSeries是一连串随时间推移而发生变化的相关事件

常见的时序数据有：
* 监控日志：机器的 CPU 负载变化
* 用户行为：用户在电商网站上的访问记录
* 金融行情：股票的日内成交记录



此类数据的特点:
* 必然带有时间戳，可能存在时效性
* 数据量巨大，并且生成速度极快
* 更关注数据变化的趋势，而非数据本身

## 2. 关系型数据库的不足
当面对时序数据时，传统的关系型数据就显得力不从心


| 关系型数据模型 | 时序数据库需求 |
| --- | --- |
|数据按住建索引组织、存储  |数据按时间戳进行组织、存储，便于按时间维度查询  |
|数据持久后永久存在  |数据具有的生命周期，定期清理过期数据  |
|支持复杂的OLTP功能（点查、改、删）  | 支持的OLAP操作（基于时间窗口） |
|并发修改加锁，提供事务保证  | Last Write Win解决写冲突，无需事务 |

### 两者之间的存在的冲突：

* 如果主键设计的不好，时序数据的顺序插入可能变为随机写入，影响写入性能
* 传统关系型数据为提高数据生命周期管理功能，需要定时执行清理任务，避免磁盘空间耗尽
* 关系型数据库对事务的支持，对于时序数据来说略显多余，还会影响写入能力

除此之外，关系型数据库还存在以下天然短板：
* 需要通过分表分库sharding实现横向扩展

    分库分表引入额外复杂度，需要维护映射关系。 此时 SQL 语言的查询优势不复存在，多数查询都会退化为 KV 查找
    
* 写时模式schema on write灵活度不足
    关系数据库新增字段属于 DDL 操作，会导致锁表锁库。 频繁的库表变更影响系统稳定，无法适应快速的业务变更。

> 注意，修改表结构的操作，MySQL8.0之前的版本默认是会锁表的，所以，不要在业务高峰期做这些操作，而是选择在晚间进行操作，当然，我们也可以在晚间使用在线的DDL工具来处理这些事情，避免锁表对业务造成影响。

**常用的在线DDL工具**
* MySQL的Online。
* pt-osc，推荐使用。



## 3. redis的不足

  存储时序数据库的另一个挑战就是其夸张的数据生成速度。以用户行为数据为例，如果一个接口的QPS是1万。就意味着一秒钟内会生成1万条用户行为记录。假设这样的接口有100个，那么每秒钟生成的记录数可达100万。

　一种解决方式是将消息积压至 Kafka 这类中间件，然后进行异步处理。但对于某些业务场景来说，这一处理方式则显得不合时宜。以股票成交数据为例，为了保障行情的时效性，无法采用异步批处理的方式实现。为了实现极高的写入吞吐量，通常会考虑使用 Redis 实现这一功能。
 
 然而这一方案也存在以下问题：

* redis 不适合存储大 Key，删除 Key 的内存释放操作可能导致长时间的阻塞
* 假设数据以 list 的形式存储，执行 lrange 命令的时间复杂度为O(S+N)，访问性能较差
* 内存空间有限，无法存储大量的数据


## 3. 时序数据库
时序数据库是一类专门用于存储时序数据的数据管理系统，这类数据库的设计思想大致可以总结为下面几条：
* 使用特殊设计的外存索引来组织数据
* 强制使用 timestamp 作为唯一的主键
* 不检查写冲突，避免加锁，提高写入性能
* 对按时间顺序写入进行优化，提高写入性能
* 不支持细粒度的数据删除功能，提高查询写入性能
* 牺牲强一致性来提高系统的查询吞吐量，提高查询性能
* 提供基于时间窗口的 OLAP 操作，放弃关联查询等高级功能
* 通过无模式schemaless设计使系统更易于水平扩展

### 1. 时序数据模型

类似于关系型数据库，时序数据库也有自己的数据模型，并且两者直接存在不少相似之处：

| 关系模型 |时序模型  |含义 |
| --- | --- |--- |
|table  | metric/measurement |表——指标（时间序列） |
|column  |value/field  |列——值（无索引序列） |
|index  |tag  |索引——标签（索引列） |
|row  |point  |记录行——数据点（时间序列中某个时刻的数据） |
|primary key  |timestamp  |行主键——点时间戳（时间序列内唯一标识） |

其中 tag 的概念较为重要：
* tag 是一个字符串类型的键值对
* tag 并不是时序数据，而是元数据
* tag 的唯一组合确定一个时间序列
* tag 可以方便实现粗粒度的聚合
* tag 决定了索引的组织形式
* tag 组合的数量数量不宜过多

### 2. 常见的时序数据库
#### OpenTSDB
OpenTSDB 是一种基于 HBase 来构建的分布式、可扩展的时间序列数据库。OpenTSDB 被广泛应用于存储、索引和服务从大规模计算机系统（网络设备、操作系统、应用程序）采集来的监控指标数据，并且使这些数据易于访问和可视化。


![image.png](https://www.choumaomi.com/static/img/fc782ad4de868126eced14debeead728.image.png)

OpenTSDB 由时间序列守护程序 (TSD) 以及一组命令行实用程序组成。每个 TSD 都是独立的。 没有主节点，没有共享状态。

* 优点

    TSD 是无状态的，所有状态数据保存在 HBase 中，天然支持水平扩展
* 缺点
    1. Hadoop 全家桶运维难度较大，需要专人负责。新版本的 OpenTSDB 底层支持 Cassandra
    2. 存储模型过于简化。单值模型且只能存储数值类型数据，单个 metric 最多支持 8 个 tag key
    3. 虽然利用了 HBase 作为底层存储，但是没有提供对 MapReduce 的支持。可以通过 Spark 实现复杂的处理逻辑

#### InfluxDB
时序数据库 InfluxDB 是一款专门处理高写入和查询负载的时序数据库，基于 InfluxDB 能够快速构建具有海量时序数据处理能力的分析和监控软件。该项目的发起者是 influxdata 公司，该公司提供了一套用于处理时序数据的完整解决方案，InfluxDB 是该解决方案中的核心产品。


![image.png](https://www.choumaomi.com/static/img/cd621a788796fa93d10df242d3c923e6.image.png)

* 优点

    1. 开箱即用，运维简单
    2. 多值存储模型、丰富的数据类型
    3. 提供了类 SQL 的查询语言
    4. 独创 TSM 索引
* 缺点
    1. 开源版本不支持集群部署，对于大规模应用来说，使用前需要慎重考虑

### 3. 深入influxDB

#### 数据模型
InfluxDB 的数据模型已经很接近传统的关系模型：

| database | 命名空间，相互隔离 |
| --- | --- |
|retention policy  | 保存策略，定义数据生命周期  |
|bucket  |database+retention policy  |
|measurement  |相关时间序列集合  |
|tag  |标签索引，索引列  |
|field  |时序数据，无索引列  |
|point  |数据点，时间序列中某个时刻的数据  |
|time  |时间戳，时间序列内唯一标识  |


![image.png](https://www.choumaomi.com/static/img/9b12ccc4b997f7c7172da1ddb3646aa7.image.png)

保留策略retention policy 用于管理数据生命周期，其中包含了：
* 持续时间duration：指定了数据保留时间，过期的数据将自动从数据库中删除

* 副本个数replication factor：指定了集群模式下，需要维护数据副本的个数（仅在集群模式下有效）

* 分片粒度hard duration)：指定了 shard group 的时间跨度（影响数据分片大小）

保留策略与 database 存在以下关系：
* 一个 database 可以有多个 RP，每个 RP 只属于一个 database 1:N
* 创建 point 时可以指定 RP，一个 measurement 可以有不同的 RP N:N

这意味着：
> 同个 measurement 可能存在两个有着完全相同的 time 的 point。为了解决数据重复的问题，InfluxDB 2 引入了一个 bucket 的概念，用于避免这一情况。


#### series
时间序列 Series 在 InfluxDB 中也是个核心概念：

| series key |measurement+tag+field key  |
| --- | --- |
| series |时间序列，serial key相同的数据集合  |
| seriescardinality | 序列基数，series key的数量 |

为了唯一标识一个时间序列，InfluxDB 引入了 Serieskey 的概念：
> 每个数据点都有 Serieskey，Serieskey 相同的数据点属于同个时间序列，会存储在同一个文件中，方便后续查询


Serieskey 的数量称为序列基数 series cardinality：
> 序列基数是一个重要的性能指标，InfluxDB 会为每个 Serieskey 在内存中维护一个索引记录，因此序列基数能够直观反映当前数据的内存压力



![image.png](https://www.choumaomi.com/static/img/df1074a3bc97405a593247922139e664.image.png)


上图的 series cardinality 为 4，其中包含以下 series key：

| measurement + tags + field | 
| --- | 
| census, location=1, scientist=langstroth, butterflier
census, location=1, scientist=langstroth, honeybees
census, location=1, scientist=perpetual, butterflier
census, location=1, scientist=perpetual, honeybees | 


注意：即便两条记录的 measurement、time、tag、field 完全一致，但只要使用的是不同的 RP，那么它们就属于不同的 series，会被存储在不同的 bucket 中。


#### 查询语言

InfluxDB 提供了两种查询语言：

* InfluxQL：类 SQL 的声明式查询语言，同时具有 DDL 与 DML 功能
* Flux：函数式查询语言，仅支持 DML 功能，能支持复杂的查询条件，但不支持增删改操作
下面通过一些实际操作来熟悉一下 InfluxQL：

```sql
# 创建数据库
CREATE DATABASE "sample_data"
USE sample_data
 
# 插入样例数据，格式参考：https://docs.influxdata.com/influxdb/v1.8/write_protocols/line_protocol_tutorial
INSERT census,location=1,scientist=langstroth butterflies=12i,honeybees=23i 1439827200000000000
INSERT census,location=1,scientist=perpetua butterflies=1i,honeybees=30i 1439827200000000000
INSERT census,location=1,scientist=langstroth butterflies=11i,honeybees=28i 1439827560000000000
INSERT census,location=1,scientist=perpetua butterflies=3i,honeybees=28i 1439827560000000000
INSERT census,location=2,scientist=langstroth butterflies=2i,honeybees=11i 1439848440000000000
INSERT census,location=2,scientist=langstroth butterflies=1i,honeybees=10i 1439848800000000000
INSERT census,location=2,scientist=perpetua butterflies=8i,honeybees=23i 1439849160000000000
INSERT census,location=2,scientist=perpetua butterflies=7i,honeybees=22i 1439849520000000000

# 显示数据库中的表
# measurement 无需预先定义，由 InfluxDB 动态创建
SHOW MEASUREMENTS
 
# 显示数据库中的 field key
SHOW FIELD KEYS
 
 
# 显示数据库中的 tag key
SHOW TAG KEYS
 
# 显示数据库中的 tag value
SHOW TAG VALUES WITH KEY = scientist
 
# 查询所有数据
SELECT * FROM census;
 
# 对 location = 1 的数据求和
SELECT SUM(butterflies) AS butterflies, SUM(honeybees) AS honeybees FROM census WHERE location = '1';
 
# 删除 location = 1 的数据
DELETE FROM census WHERE location = '1';
SELECT * FROM census;
 
# 更新特定数据
SELECT * FROM census;
INSERT census,location=2,scientist=perpetua butterflies=10i,honeybees=50i 1439849520000000000
SELECT * FROM census;

# 更新数据时要保证数据类型一致，否则会报错
INSERT census,location=2,scientist=perpetua butterflies=abc,honeybees=efg 1439849520000000000
 
# 删除数据库
DROP DATABASE sample_data;

```
Flux 无命令行支持，只能通过 http 接口请求。有兴趣可以参考下面的脚本，动手尝试一下：

```
curl -XPOST 127.0.0.1:8086/api/v2/query -sS \
-H 'Accept:application/csv' \
-H 'Content-type:application/vnd.flux' \
-H 'Authorization: Token root:123456' \
-d '
from(bucket:"sample_data")
|> range(start:time(v: 1439827200000), stop:time(v: 143984952000))
|> filter(fn:(r) => r._measurement == "census" and r.location == "1" and (r._field == "honeybees" or r._field == "butterflies"))
|> limit(n: 100)'

```

#### 整体架构
在了解完查询语言之后，接下来看看 InfluxDB 的整体架构：


![image.png](https://www.choumaomi.com/static/img/47e0e1f4a8de2255c2d721ec59a51413.image.png)

上图将 InfluxDB 分为了 4 层，上面 database 与 RP 这两层之前已经介绍过，我们重点关注下面两层：


|shard|	存储的时序数据的磁盘文件|
| --- | --- |
|shard group|	shard 容器，责管理数据的生命周期，清除过期的数据|
|shard duration|	shard duration|
由于时序数据的数据量通常十分巨大，因此 InfluxDB 的设计中引入了分片的策略。并且同时采用了两种分片策略：
* shard group 层采用了基于时间的分片策略，方便实现按照时间条件范围查询
* shard 层则是基于 hashmod 进行分片，避免出现写热点产生性能瓶颈
　
每个 shard 由 WAL、Cache、TSM文件 3 部分组成：

![image.png](https://www.choumaomi.com/static/img/20a680411f7d525f83bfc2a363d58975.image.png)

整个数据的写入流程简化为 3 个步骤：

1. 先写入 WAL
1. 然后写入 Cache
1. 最终持久化为 TSM File



##### WAL
　预写日志Write-Ahead-Log是一种常见的提高数据库优化手段，能够在保证数据安全的同时，提升系统的写入性能。
　InfluxDB WAL 由一组定长的 segement 文件构成，每个文件大小约为 10MB。这些 segment 文件只允许追加，不允许修改。

##### Cache
Cache 是 WAL 的一个内存快照，保证 WAL 中的数据对用户实时可见。
当 Cache 空闲或者过满时，对应的 WAL 将被压缩并转换为 TSM，最终释放内存空间。
每次重启时会根据 WAL 重新构造 Cache。

##### TSM File
TSM 是一组存储在磁盘上的外存索引文件，细节将在后续进行介绍。

它们之间的关系可以简单描述为：

* Cache = WAL
* Cache + TSM = 完整的数据
[更多内容](https://www.cnblogs.com/buttercup/p/15204096.html)


[influxdb的安装](https://www.cnblogs.com/chenwolong/p/influxdb.html)
[python操作influxdb](https://blog.csdn.net/xiligey1/article/details/104530893/)

时序数据库

## 快速排序
快速排序是一种常用的排序，比选择排序。



基线条件为：数组为空或只包含一个元素，这种情况下根本不用排序。
```python
def quicksort(array):
	if len(array) <2:
	return array
```
基准值：将任意一个元素作为基准值


### 两个元素的排序
检查第一个元素是否比第二个元素小，如果不比第二个小，就变换他们的位置

### 三个元素的数组
要使用D&C（分而治之），需要将数组分解，直到满足基线条件。下面介绍快速排序的工作原理：
1. 从数据中选择一个元素，这个元素被称为基准值
2. 找出比基准值小的元素以及比基准值大的元素
	> 分为三个区（两个子数组是无序的）：
	* 一个由所有小于基准值的数字组成的子数组
	* 基准值 
	* 一个由所有大于基准值的数字组成的子数组
3. 如果子数组是有序的，左边的数组+基准值+右边的数组
4. 如何对子数组进行排序呢？对于包含两个元素的数组以及空数组，快速排序知道如何将他们排序，因此只要对两个子数组进行快速排序，再合并结果，就能得到一个有序数组！
	
> 归纳证明

归纳证明是一种证明算法行之有效的方式，它分为两步：基线条件和归纳条件

是不是有点似曾相识的感觉？例如，假设我要证明我能爬到梯子的最上面。

递归条件是这样的：如果我站在一个横档上，就能将脚放到下一个横档上。换言之，如果站在第二个横档上，就能爬到第三个横档。 这就是归纳条件。

而基线条件是这样的，即我已经站在第一个横档上。因此，通过每次爬一个横档，我就能爬到梯子最顶端

对于快速排序，可使用类似的推理。

在基线条件中，我证明这种算法对空数组或包含一个元素的数组管用。在归纳条件中，我证明如果快速排序对包含一个元素的数组管用，对包含两个元素的数组也将管用；如果它对包含两个元素的数组管用，对包含三个元素的数组也将管用，以此类推。

因此，我可以说，快速排序对任何长度的数组都管用。

快速排序的代码
```python
# coding:utf-8
def quicksort(li):
    if len(li)<2:
        return li
    else:
        pivot = li[0]
        less = [i for i in li[1:] if i <= pivot]
        greater = [i for i in li[1:] if i > pivot]

        return quicksort(less)+[pivot]+quicksort(greater)

print(quicksort([10,5,3,6,9]))
```
### 大O表示法
快速排序的独特之处在于，其速度取决于选择的基准值。

大O的表示法，分平均情况和最糟的情况，像快速排序平均的情况是nlogn，最糟的是n方
```
题目练习：
使用大O表示法时，下面各种操作都需要多长时间？
4.5 打印数组中每个元素的值。
o(n)

4.6 将数组中每个元素的值都乘以2。
o(n)

4.7  只将数组中第一个元素的值乘以2。
o(1)

4.8 根据数组包含的元素创建一个乘法表，即如果数组为[2, 3, 7, 8, 10]，首先将每个元素
都乘以2，再将每个元素都乘以3，然后将每个元素都乘以7，以此类推。
o(n方)
```

##总结
1. D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元
素的数组。
2. 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
3. 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
4. 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n)
快得多。

## 散列表
目标：
* 学习散列表——最有用的基本数据结构之一
* 学习散列表的内部机制：实现、冲突和散列函数

### 定义
散列函数是这样的函数，即无论给它什么数据，它都还你一个数字。如果用专业术语来表达，散列函数是“将输入映射到数字”

要满足的要求：
1. 它必须是一致的。例如，假设你输入apple时得到的是4，那么每次输入apple时，得到的都
必须为4。如果不是这样，散列表将毫无用处。
2. 它应将不同的输入映射到不同的数字。例如，如果一个散列函数不管输入是什么都返回1，
它就不是好的散列函数。最理想的情况是，将不同的输入映射到不同的数字。

结合散列函数和数组创建了一种被称为散列表的数据结构。数组和链表都被直接映射到内存，但散列表更复杂，它使用散列函数来确定元素的位置。


python提供的散列表实现为——字典，你可以使用函数dict来创建散列表

63页
**练习**
对于同样的输入，散列表必须返回同样的输出，这一点很重要。如果不是这样的，就无法找到你在散列表中添加的元素！
请问下面哪些散列函数是一致的？
5.1 f(x) = 1 一致 不是理想的情况，但是属于散列函数
5.2 f(x) = rand() 不一致 输入一样的时候，输出必须一样
5.3 f(x) = next_empty_slot()-返回散列表中下一个空位置的索引 不一致 还不了数字
5.4 f(x) = len(x) 一致

### 应用案例

* 应用于查找
* 防止重复
* 用作缓存
    
    缓存是一种常用的加速方式，所有大型网站都使用缓存，而缓存的数据则存储在散列表中！
    
    仅当URL不在缓存中时，你才让服务器做些处理，并将处理生成的数据存储到缓存中，再返
回它。这样，当下次有人请求该URL时，你就可以直接发送缓存中的数据，而不用再让服务器进
行处理了。

**总结**
1. 模拟映射关系
2. 防止重复
3. 缓存/记住数据，以免服务器再通过处理来生成他们

### 冲突
冲突：给两个键分配的位置相同。

冲突很糟糕，必须要避免，不然就会出现输入与输出的不匹配

处理冲突的最简单的方法：如果两个键映射到了同一个位置，就再这个位置存储一个链表，但是这种情况会影响到散列表的查询速度


这里有两个经验教训：
1. 散列函数很重要。前面的散列函数将所有的键都映射到一个位置，而最理想的情况是，
散列函数将键均匀地映射到散列表的不同位置。
2. 如果散列表存储的链表很长，散列表的速度将急剧下降。然而，如果使用的散列函数很
好，这些链表就不会很长！


### 性能


在平均情况下，散列表的查找（获取给定索引处的值）速度与数组一样快，而插入和删除速
度与链表一样快，因此它兼具两者的优点！


但在最糟情况下，散列表的各种操作的速度都很慢。
因此，在使用散列表时，避开最糟情况至关重要。为此，需要避免冲突。而要避免冲突，需要有：

* 较低的填装因子（数组中被占用的位置数。例如：散列表中有5个位置，只有2个被占用，因子为0.4）
    一旦填装因子大于1，就超出了数组的位置，这个时候就需要调整长度，调整长度是需要很长的工作时间的，一旦超过0.7就该调整列表的长度
    
* 良好的散列函数
    良好的散列函数让数组中的值呈均匀分布，糟糕的散列函数让值扎堆，导致大量的冲突
    

 
## 广度优先
目标
* 使用新的数据机构图来建立网络模型
* 可对图使用算法回答“到X的最短路径是什么？”等问题
* 有向图和无向图
* 拓扑排序，这种排序算法指出了节点之间的以来关系


### 初识
广度优先搜索让你能够找出两样东西之间的最短距离，使用广度优先搜索可以：
* 编写国际跳棋AI，计算最少走多少步就可获胜；
* 编写拼写检查器，计算最少编辑多少个地方就可将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方；
* 根据你的人际关系网络找到关系最近的医生。

### 图模型
图是什么？

图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为令居。图用于模拟不同的东西是如何相连的。

### 广度优先搜索
广度优先搜索是一种用于图的查找算法，可帮助回答两类问题：
1. 从节点A出发，有前往节点B的路径吗？
2. 从节点A出发，前往节点B的哪条路径最短？


假设你经营着一个芒果农场，需要寻找芒果销售商，以便将芒果卖给他。在Facebook，你与
芒果销售商有联系吗？为此，你可在朋友中查找。

这种查找很简单。首先，创建一个朋友名单。

然后，依次检查名单中的每个人，看看他是否是芒果销售商。

假设你没有朋友是芒果销售商，那么你就必须在朋友的朋友中查找。

检查名单中的每个人时，你都将其朋友加入名单。


这样一来，你不仅在朋友中查找，还在朋友的朋友中查找。别忘了，你的目标是在你的人际
关系网中找到一位芒果销售商。因此，如果Alice不是芒果销售商，就将其朋友也加入到名单中。
这意味着你将在她的朋友、朋友的朋友等中查找。使用这种算法将搜遍你的整个人际关系网，直
到找到芒果销售商。这就是广度优先搜索算法。


#### 查询最短路径
谁是关系最近的芒果销售商。例如，朋友是一度关系，朋友的朋友是二度关系

你按顺序依次检查名单中的每个人，看看他是否是芒果销售商。这将先在一度关系中查找，
再在二度关系中查找，因此找到的是关系最近的芒果销售商。广度优先搜索不仅查找从A到B的
路径，而且找到的是最短的路径。

注意，只有按添加顺序查找时，才能实现这样的目的。

#### 队列
队列只支持两种操作：入队和出队。

如果你将两个素加入队列，先加入的元素将在后加入的元素之前出队。因此，你可使用队
列来表示查找名单！这样，先加入的人将先出队并先被检查。——保证了添加顺序


### 实现图
表示这种映射关系的python代码如下：
```python
graph = {} 
graph["you"] = ["alice", "bob", "claire"]
```
注意：“你”被映射到了一个数组，因此graph[“you”]是一个数组，其中包含了“你”的所有邻居

表示图的代码：
```python
graph = {} 
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"] 
graph["alice"] = ["peggy"] 
graph["claire"] = ["thom", "jonny"] 
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = []
```
### 实现算法

![image.png](https://www.choumaomi.com/static/img/ca0437151fbbbb7c23a7406f27b3f44e.image.png)

首选，创建一个队列。在python中，可以使用函数deque来创建一个双端队列
```python
from collection import deque
search_queue = deque()
search_queue+=graph['you']

```
其次，将你的这些邻居加入到搜索队列中
```python
while search_queue: # 只要队列不为空
    person = search_queue(person) # 就取出其中的第一个人
    if person_is_seller(person):  # 检查这个人是否是芒果商
        print(person+"is a mango seller") # 是芒果销售商
        return True
    else:
        search_queue+=graph[person]  # 不是芒果商，将找个人的朋友都加入搜索队列

def person_is_seller(name):
    return name[-1] == 'm'
```
算法的结束条件：
* 找到一位芒果销售商
* 队列变成空的，这意味着你的人际关系网中没有芒果销售商

优化：检查一个人之前，要确认之前没检查过他

```python
# coding:utf-8
from collections import deque

def search(name): 
    search_queue = deque() 
    search_queue += graph[name]
    print(search_queue)
    searched = [] 
    while search_queue:
        person = search_queue.popleft() 
        if not person in searched:
            if person_is_seller(person): 
                print(person + " is a mango seller!" )
                return True 
            else: 
                search_queue += graph[person] 
                searched.append(person)
    return False
def person_is_seller(name): 
 return name[-1] == 'm'
graph = {} 
graph["you"] = ["alice", "bob", "claire"] 
graph["bob"] = ["anuj", "peggy"] 
graph["alice"] = ["peggy"] 
graph["claire"] = ["thom", "jonny"] 
graph["anuj"] = [] 
graph["peggy"] = [] 
graph["thom"] = [] 
graph["jonny"] = []
search("you")
```
### 运行时间

如果你在你的整个人际关系网中搜索芒果销售商，就意味着你将沿每条边前行（记住，边是
从一个人到另一个人的箭头或连接），因此运行时间至少为O(边数)。

你还使用了一个队列，其中包含要检查的每个人。将一个人添加到队列需要的时间是固定的，
即为O(1)，因此对每个人都这样做需要的总时间为O(人数)。所以，广度优先搜索的运行时间为
O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。


![image.png](https://www.choumaomi.com/static/img/af3472b7c2907f47f32c20154ac3a1f0.image.png)

从某种程度上说，这种列表是有序的。如果任务A依赖于任务B，在列表中任务A就必须在任务B后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。

假设你正在规划一场婚礼，并有一个很大的图，其中充斥着需要做的事情，但却不知道要从哪里开始。这时就可使用拓扑排序来创建一个有序的任务列表。


准备第七章

算法图解-读书笔记

python异步同步

## 简介及定义

aiohttp是一个为Python提供异步HTTP 客户端/服务端编程，基于asyncio(Python用于支持异步编程的标准库)的异步库。



**核心功能**
* 同时支持客户端使用和服务端使用。
* 同时支持服务端WebSockets组件和客户端WebSockets组件，开箱即用呦。
* web服务器具有中间件，信号组件和可插拔路由的功能。

## 安装
```shell
pip install aiohttp
```
用安装更快的cchardet来替代chardet进行解码
```bash
pip install cchardet
```
对于更快的客户端API DNS解析方案，aiodns是个很好的选择，极力推荐: 
```bash
$ pip install aiodns
```

## 快速开始
client.py
```python
# coding:utf-8
"""
文件直接运行
"""
import aiohttp
import asyncio
import async_timeout

# 定义异步函数=协程
async def fetch(session, url):
    with async_timeout.timeout(10):
        async with session.get(url) as response:
            # 必须使用await，不能使用yield from;如果是使用yield from ，需要采用@asyncio.coroutine相对应
            return await response.text()

async def main():
    async with aiohttp.ClientSession() as session:
        # 建立一个session对象，用session对象去打开网页
        html = await fetch(session, 'http://www.baidu.com')

        print(html.encode('utf-8'))
'''
async def 用来定义异步函数，其内部有异步操作。每个线程有一个事件循环，主线程调用asyncio.get_event_loop()时会创建事件循环，把异步的任务丢给这个循环的run_until_complete()方法，事件循环会安排协同程序的执行。
'''
loop = asyncio.get_event_loop() #获取“事件循环”对象
loop.run_until_complete(main()) #通过事件循环，去调用协程函数
loop.close()  # 结束时间循环
```

server.py
```python
# coding:utf-8
"""
1. 运行文件
2. 在8080端口访问
"""
from aiohttp import web

async def handle(request):
    name = request.match_info.get('name', "Anonymous")
    text = "Hello, " + name
    return web.Response(text=text)

app = web.Application()
app.router.add_get('/', handle)
app.router.add_get('/{name}', handle)

web.run_app(app)
```
## 客户端使用
### 1.发起请求
client2.py
```python
#coding:utf-8
import asyncio
import aiohttp
async  def main():
    async with aiohttp.ClientSession() as session:
        async with session.get('https://api.github.com/events') as resp:
            print(resp.status)
            # print(type(resp.text()))
            a = await resp.text()
            a = a.encode('utf-8')
            print(a)

loop = asyncio.get_event_loop() #获取“事件循环”对象
loop.run_until_complete(main()) 

```
其他请求:
* session.post('http://httpbin.org/post', data=b'data')
* session.put('http://httpbin.org/put', data=b'data')
* session.delete('http://httpbin.org/delete')
* session.head('http://httpbin.org/get')
* session.options('http://httpbin.org/get')
* session.patch('http://httpbin.org/patch', data=b'data')

**注意**
不要为每个请求都创建一个会话。大多数情况下每个应用程序只需要一个会话就可以执行所有的请求。 每个会话对象都包含一个连接池，可复用的连接和持久连接状态(keep-alives，这两个是默认的)可提升总体的执行效率。

### 2.发送json请求
每个会话的请求方法都可接受json参数
```python
async with aiohttp.ClientSession() as session:
    async with session.post(json={'test':'object'})
```
默认情况下，会话session使用Python标准库里的json模块解析json信息。但还可使用其他的json解析器。可以给clientsession制定json_serlialize参数实现
```python
import ujson
async with aiohttp.ClientSession(json_serialize=ujson.dumps) as session:
    async with session.post(json={'test':'object'})
```
### 3.传递url中的参数
```python
params = {'key1': 'value1', 'key2': 'value2'}
async with session.get('http://httpbin.org/get',
                       params=params) as resp:
    assert str(resp.url) == 'http://httpbin.org/get?key2=value2&key1=value1'
```
同键不同值的**并联字典（MultiDict） **也同样支持。 可使用带有两个tuples(元组，python中的数据类型)的list(列表，python中的数据类型)来构建:
```python
params = [('key', 'value1'), ('key', 'value2')]
async with session.get('http://httpbin.org/get',
                       params=params) as r:
    assert str(r.url) == 'http://httpbin.org/get?key=value2&key=value1'
```
同样也允许你传递str（字符串）给params，但要小心一些不能被编码的字符。+就是一个不能被编码的字符:
```python
async with session.get('http://httpbin.org/get',
                       params='key=value+1') as r:
        assert str(r.url) == 'http://httpbin.org/get?key=value+1'
```
**注意**
aiohttp会在发送请求前标准化URL。 域名部分会用IDNA 编码，路径和查询条件会重新编译(requoting)。 比如:URL('http://example.com/путь%30?a=%31') 会被转化为URL('http://example.com/%D0%BF%D1%83%D1%82%D1%8C/0?a=1') 如果服务器需要接受准确的表示并不要求编译URL，那标准化过程应是禁止的。 禁止标准化可以使用encoded=True:
```python
await session.get(URL('http://example.com/%30', encoded=True))
```

*传递params时不要用encode=True，这俩参数不能同时使用。*

### 4.获取响应内容
我们可以读取服务器的响应内容
```python
async with session.get('https://api.github.com/events') as resp:
    print(await resp.text())
```
aiohttp将会自动解码内容。你可以为text()方法指定编码(使用encoding参数):
```python
await resp.text(encoding='windows-1251')
```
#### 获取二进制响应内容
```python
print(await resp.read())
b'[{"created_at":"2015-06-12T14:06:22Z","public":true,"actor":{...
```
#### 获取json响应内容
```python
async with session.get('https://api.github.com/events') as resp:
    print(await resp.json())
```
**注意**
这些方法会读出内存中所有响应的内容。如果你要读非常多的数据，考虑使用流式响应方法进行读取。

#### 获取流失响应内容
read(), json(), text()等方法使用起来很方便，但也要注意谨慎地使用。上述方法会将所有的响应内容加载到内存。举个例子，如果你要下载几个G的文件，这些方法还是会将所有内容都加载到内存，内存会表示"臣妾做不到啊~"(如果内存不够的话)。作为代替你可以用content属性。content其实是 aiohttp.StreamReader类的实例。gzip和deflate传输编码同样会自动解码。
```python
async with session.get('https://api.github.com/events') as resp:
    await resp.content.read(10)
```
一般情况下，你可以使用下列模式将内容保存在一个文件中：
```python
with open(filename, 'wb') as fd:
    while True:
        chunk = await resp.content.read(chunk_size)
        if not chunk:
            break
        fd.write(chunk)
```


### 5.获取请求信息
ClientResponse（客户端响应）对象含有request_info(请求信息)，主要是url和headers信息。 raise_for_status结构体上的信息会被复制给ClientResponseError实例。

#### 自定义headers信息
```python
import json
url = 'https://api.github.com/some/endpoint'
payload = {'some': 'data'}
headers = {'content-type': 'application/json'}

await session.post(url,
                   data=json.dumps(payload),
                   headers=headers)
```

#### 自定义Cookies
```python
url = 'http://httpbin.org/cookies'
cookies = {'cookies_are': 'working'}
async with ClientSession(cookies=cookies) as session:
    async with session.get(url) as resp:
        assert await resp.json() == {
           "cookies": {"cookies_are": "working"}}
```
### 6.发起更复杂的post请求
如果你想发送非表单形式的数据你可用str(字符串)代替dict(字典)。这些数据会直接发送出去。 例如，GitHub API v3 接受JSON编码POST/PATCH数据:
```python
import json
url = 'https://api.github.com/some/endpoint'
payload = {'some': 'data'}

async with session.post(url, data=json.dumps(payload)) as resp:
    ...
```
#### 发送多部分编码文件
```python
url = 'http://httpbin.org/post'
files = {'file': open('report.xls', 'rb')}

await session.post(url, data=files)
```
你也可以显式地设置文件名，文件类型：
```python
url = 'http://httpbin.org/post'
data = FormData()
data.add_field('file',
               open('report.xls', 'rb'),
               filename='report.xls',
               content_type='application/vnd.ms-excel')

await session.post(url, data=data)
```

### 7.流式上传
aiohttp 支持多种形式的流式上传，允许你直接发送大文件而不必读到内存。
```python
with open('massive-body', 'rb') as f:
   await session.post('http://httpbin.org/post', data=f)
```
或者使用aiohttp.streamer对象：
```python
@aiohttp.streamer
def file_sender(writer, file_name=None):
    with open(file_name, 'rb') as f:
        chunk = f.read(2**16)
        while chunk:
            yield from writer.write(chunk)
            chunk = f.read(2**16)

# 之后你可以使用’file_sender‘传递给data:

async with session.post('http://httpbin.org/post',
                        data=file_sender(file_name='huge_file')) as resp:
    print(await resp.text())
```
同样可以使用StreamReader对象.

我们来看下如何把来自于另一个请求的内容作为文件上传并计算其SHA1值:
```python
async def feed_stream(resp, stream):
    h = hashlib.sha256()

    while True:
        chunk = await resp.content.readany()
        if not chunk:
            break
        h.update(chunk)
        stream.feed_data(chunk)

    return h.hexdigest()

resp = session.get('http://httpbin.org/post')
stream = StreamReader()
loop.create_task(session.post('http://httpbin.org/post', data=stream))

file_hash = await feed_stream(resp, stream)
```
因为响应对象的content属性是一个StreamReader实例，所以你可以将get和post请求连在一起用:
```python
r = await session.get('http://python.org')
await session.post('http://httpbin.org/post',
                   data=r.content)
```

### 8.上传预压缩过的数据
上传一个已经压缩过的数据，需要为Headers中的Content-Encoding指定算法名(通常是deflate或者是zlib).
```python
async def my_coroutine(session, headers, my_data):
    data = zlib.compress(my_data)
    headers = {'Content-Encoding': 'deflate'}
    async with session.post('http://httpbin.org/post',
                            data=data,
                            headers=headers)
        pass
```

### 9.持久连接(keep-aliver)，连接池和cookies共享
ClientSession可以在多个请求之间共享cookies
```python
async with aiohttp.ClientSession() as session:
    await session.get(
        'http://httpbin.org/cookies/set?my_cookie=my_value')
    filtered = session.cookie_jar.filter_cookies('http://httpbin.org')
    assert filtered['my_cookie'].value == 'my_value'
    async with session.get('http://httpbin.org/cookies') as r:
        json_body = await r.json()
        assert json_body['cookies']['my_cookie'] == 'my_value'
```
你也可以为所有的会话请求设置headers:
```python
async with aiohttp.ClientSession(
    headers={"Authorization": "Basic bG9naW46cGFzcw=="}) as session:
    async with session.get("http://httpbin.org/headers") as r:
        json_body = await r.json()
        assert json_body['headers']['Authorization'] == \
            'Basic bG9naW46cGFzcw=='
```
### 10.安全cookies
ClientSession中的默认的aiohttp.CookiesJar使用的是严苛模式，RFC 2109明确禁止使用ip地址形式的URL携带cookies信息。比如: http://127.0.0.1:80/cookie 这样很好，不过有些时候我们测试时需要允许携带cookies。在aiohttp.CookiesJar中传递unsafe=True来实现这一效果:

```python
jar = aiohttp.CookieJar(unsafe=True)
session = aiohttp.ClientSession(cookie_jar=jar)
```
### 11. 使用虚假Cookie Jar
有时不想处理cookie。这时可以在会话中使用aiohttp.DummyCookieJar来达到目的。
```python
jar = aiohttp.DummyCookieJar()
session = aiohttp.ClientSession(cookie_jar=jar)
```

### 12. 使用连接器
想要调整请求的传输层你可以为ClientSession及其同类组件传递自定义的连接器。例如:
```python
conn = aiohttp.TCPConnector()
session = aiohttp.ClientSession(connector=conn)
```
#### 限制连接池的容量
限制同一时间打开的连接数可以传递limit参数:
```python
conn = aiohttp.TCPConnector(limit=30)
```
这样就将总数限制在30.

默认情况下是100.

如果你不想有限制，传递0即可:

限制同一时间在同一个端点((host, port, is_ssl) 3者都一样的情况)打开的连接数可指定limit_per_host参数:
```python
conn = aiohttp.TCPConnector(limit_per_host=30)
```
#### 使用自定义域名服务器
底层需要aiodns支持：
```python
from aiohttp.resolver import AsyncResolver

resolver = AsyncResolver(nameservers=["8.8.8.8", "8.8.4.4"])
conn = aiohttp.TCPConnector(resolver=resolver)
```
#### 为Tcp sockets添加ssl控制
默认情况下aiohttp总会对使用了HTTPS协议(的URL请求)查验其身份。但也可将verify_ssl设置为False让其不检查:
```python
r = await session.get('https://example.com', verify_ssl=False)
```
如果你需要设置自定义SSL信息(比如使用自己的证书文件)你可以创建一个ssl.SSLContext实例并传递到ClientSession中:
```python
sslcontext = ssl.create_default_context(
   cafile='/path/to/ca-bundle.crt')
r = await session.get('https://example.com', ssl_context=sslcontext)
```

如果你需要忽略所有SSL的错误:
```python
try:
    await session.get('https://expired.badssl.com/')
except aiohttp.ClientSSLError as e:
    assert isinstance(e, ssl.SSLError)

try:
    await session.get('https://wrong.host.badssl.com/')
except aiohttp.ClientSSLError as e:
    assert isinstance(e, ssl.CertificateError)
```
### 13. unix域套接字
如果你的服务器使用UNIX域套接字你可以用UnixConnector:
```python
conn = aiohttp.UnixConnector(path='/path/to/socket')
session = aiohttp.ClientSession(connector=conn)
```

> 什么是套接字？

TCP用主机的IP地址加上主机上的端口号作为TCP连接的端点，这种端点就叫做套接字（socket）或插口。套接字用（IP地址：端口号）表示，区分不同应用程序进程间的网络通信和连接,主要有3个参数：通信的目的IP地址、使用的传输层协议(TCP或UDP)和使用的端口号。

### 14. 代理支持
aiohttp 支持 HTTP/HTTPS形式的代理。你需要使用proxy参数:
```python
async with aiohttp.ClientSession() as session:
    async with session.get("http://python.org",
                           proxy="http://some.proxy.com") as resp:
        print(resp.status)
```
同时也支持认证代理
```python
async with aiohttp.ClientSession() as session:
    proxy_auth = aiohttp.BasicAuth('user', 'pass')
    async with session.get("http://python.org",
                           proxy="http://some.proxy.com",
                           proxy_auth=proxy_auth) as resp:
        print(resp.status)
```
```python
session.get("http://python.org",
            proxy="http://user:pass@some.proxy.com")
```
### 15.查看响应状态码
```python
async with session.get('http://httpbin.org/get') as resp:
    assert resp.status == 200
```
### 16.获取响应cookies
```python
url = 'http://example.com/some/cookie/setting/url'
async with session.get(url) as resp:
    print(resp.cookies['example_cookie_name'])
```
### 17.使用websockets
客户端
```python
session = aiohttp.ClientSession()
async with session.ws_connect('http://example.org/websocket') as ws:

    async for msg in ws:
        if msg.type == aiohttp.WSMsgType.TEXT:
            if msg.data == 'close cmd':
                await ws.close()
                break
            else:
                await ws.send_str(msg.data + '/answer')
        elif msg.type == aiohttp.WSMsgType.CLOSED:
            break
        elif msg.type == aiohttp.WSMsgType.ERROR:
            break
```

你只能使用一种读取方式(例如await ws.receive() 或者 async for msg in ws:)和写入方法，但可以有多个写入任务，写入任务也是异步完成的(ws.send_str('data'))。

[官方文档](https://www.cntofu.com/book/127/aiohttp%E6%96%87%E6%A1%A3/ClientReference.md)

aiohttp的使用

## 前言
如果我们要把程序部署到其他地方的服务器上，供更多人访问，可能会出现失去的问题，所以可以使用flask-moment来解决。



首先使用pipenv 安装
```
pipenv install flask-moment
```

然后我们实例化扩展提供的Moment类，并传入程序实例app，以完成扩展的初始化；
```
from flask_moment import Moment
app = Flask(__name__)
moment = Moment(app)
```

**Flask-Moment默认以英文显示时间，我们可以传入区域字符串到locale()方法来更改显示语言**
```
{{ moment.locale('zh-cn')}}
```
**更合理的方式是根据用户浏览器或计算机的语言来设置语言**
```
{{ moment.locale(auto_detect=True)}}
```

## 渲染时间日期
**format()方法接受特定的格式字符串来渲染时间格式**，比如：
```
{{ moment(timestamp).format('格式字符串') }}
```


| 格式字符串 | 输出示例 |
| --- | --- |
|L  |2017-07-26  |
|LL  |2017年7月26日  |
|LLL  |2017年7月26日早上8点00分  |
|LLLL  |2017年7月26日星期三早上8点00分  |
|LT  |早上8点00分  |
|LTS  |早上8点0分0秒  |
|lll  |2017年8月10日 03:23  |
|llll  |2017年8月10日 星期四03:23  |

**支持输出相对时间**。比如相对于当前时间的”三分钟前“等。
```
<small>{{ moment(moment.timestamp).fromNow(refresh=True) }}</small>
```
**当鼠标悬停再问候消息的时间日期上时，希望能够显示一个包含具体的绝对时间的弹出窗口**
```
<small data-toggle="tooltip” data- placement= "top " data delay=” 500 ”data- timestamp= ” {{ message timestamp strftime dT sz ’） ｝｝
{ { moment (message . times tamp) . fromNow (refresh=True) } }
</small>
```
我们js中将时间日期对应元素的tooltip内容设置为渲染后的时间日期：
```
$(function(){
    function render_time() {
    return moment($(this).data('timestamp').format('lll'))
    }
    $('[data-toggle="tooltip"]').tooltip)
    {title:render_time});
});

```

1.基础

快速排序

python的并发与异步模块

1.异步与同步的概念

简介及定义

前言