利用subquery()实现分组获取最新的数据

```python
analogs = center_session.query(Analog).join(Module,Module.id==Analog.module_id).filter(Module.model=='RobotModel').all()
analog_map = {i.id:(i.name,i.descr,i.unit) for i in analogs}
his_analog_sub =his_session.query(AnalogValue.analog_id,func.max(AnalogValue.ts).label('ts')).filter(AnalogValue.guid==guid).group_by(AnalogValue.analog_id).subquery()
       


his_analog=his_session.query(AnalogValue.analog_id,AnalogValue.value,AnalogValue.ts).filter(AnalogValue.ts==his_analog_sub.c.ts,AnalogValue.analog_id==his_analog_sub.c.analog_id).all()
for item in his_analog:
    if analog_map.get(item[0]):
        all.append({'name':analog_map[item[0]][0],'descr':analog_map[item[0]][1],'value':round(item[1],2),'timestamp':str(item[2]),'unit':analog_map[item[0]][2]})
```

sqlalchemy分组取最新的数据

首先先梳理思路：
关于p中包含的内容有以下几种情况：

1. p中不包含. 和*
    `例如：s=aa,p=a;s=aa,p=aa,第一种结果失败，因为不能覆盖整个字符串；第二个：成功`
2. P中仅包含.
    `例如：s=aa,p=ab.;s=aa,p=a.;s=aa,p=b. 第一种：失败，长度不同，第二种：成功，第三种：长度相同，但是元素不同，失败`
3. p中仅包含*
    `例如：s=aaa,p=aaa*;s=aaa,p=a*;s=aaa,p=b* 第一种成功，第二种成功，第三种失败，因为有不同元素`
4. p中包含* .
    `例如：s=aab,p=a.*，p只要从有字母的时候开始，跟s一样，都能成功；s=aab,p=.a* s=aab,p=a*a.`


## 第一次写出来的代码
* 
```python
class Solution:
    def isMatch(self, s: str, p: str):
        if '*' not in p and '.' not in p:
            if s==p:
                return True
            else:
                return False
        elif '*' not in p and '.' in p:
            if len(s)==len(p):
                p = p.replace('.','')
                if set(s)-set(p):
                    return False
                else:
                    return True
            else:
                return False
        elif '.' not in p and '*' in p:
            p = p.replace('*','')
            if set(s)-set(p):
                return False
            else:
                return True
        elif '.*' in p:
            p = p.replace('.*','')
            if not p:
                return True
            if set(s)-set(p):
                return False
            else:
                return True
        else:
            p = p.split('*')
            r = 0
            for i in p:
                if i:
                    if set(s[:len(i)]) -set(i):
                        r-=1
                    if len(s):
                        pass
                
通过测试用例：177 / 353
```

## 第二次修改的代码
* 只将最后的逻辑补充了一下
```python
elif '.*' in p:
    p = p.replace('.*','')
    if not p:
        return True
    if set(s)-set(p):
        return False
    else:
        return True
else:
    p = p.split('*')
    r = 0
    start = 0
    for i in p:
        if i:
            if set(s[start:len(i)]) -set(i):
                r-=1
        start=len(i)
    if r>=0:
        return True
    else:
        return False
通过测试用例：
200 / 353
```
## 第三次
* 取值范围修改
```python
p = p.split('*')
r = 0
start = 0
for i in p:
    if i:
        if set(s[start:start+len(i)]) -set(i):
            r-=1
    start=len(i)
if r>=0:
    return True
else:
    return False
通过测试用例：
201 / 353
```

力克刷题（一）正则表达式匹配

## 环境
* python 3.6以上
## 1.schedule的非适用场景

## 2. 每分钟运行任务
```python



import schedule
import time

def job():
    print("I'm working...")

# Run job every 3 second/minute/hour/day/week,
# Starting 3 second/minute/hour/day/week from now
schedule.every(3).seconds.do(job)
schedule.every(3).minutes.do(job)
schedule.every(3).hours.do(job)
schedule.every(3).days.do(job)
schedule.every(3).weeks.do(job)

# Run job every minute at the 23rd second
schedule.every().minute.at(":23").do(job)

# Run job every hour at the 42rd minute
schedule.every().hour.at(":42").do(job)

# Run jobs every 5th hour, 20 minutes and 30 seconds in.
# If current time is 02:00, first execution is at 06:20:30
schedule.every(5).hours.at("20:30").do(job)

# Run job every day at specific HH:MM and next HH:MM:SS
schedule.every().day.at("10:30").do(job)
schedule.every().day.at("10:30:42").do(job)

# Run job on a specific day of the week
schedule.every().monday.do(job)
schedule.every().wednesday.at("13:15").do(job)
schedule.every().minute.at(":17").do(job)

while True:
    schedule.run_pending()
    time.sleep(1)
```

schedule的使用

## 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后面。这被称为拓扑排序，使用它可根据图创建一个有序列表。

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


准备第七章