上一节谈了算法的复杂度度量，为了公平度量，给出了抽象模型来度量。





他们就是图灵机和RAM模型，以计算次数来度量复杂度。

模型只是相当于给你度量的尺子，这一节来看尺子怎么用。

大O记号相当于是尺子的刻度。

大O记号并不是精确刻度，是在时间复杂度和空间复杂度取得平衡的一种科学记号，着重看DAS的潜力，而不是细节，快速看DAS的性能。

![在这里插入图片描述](/static/img/images/02555.png)

![在这里插入图片描述](/static/img/images/02556.png)

大O记号描述了趋势，往最坏的情况看算法性能。

小于符号。

![在这里插入图片描述](/static/img/images/02557.png)

大欧米伽符号。描述下届，算法最好的情况。

大于符号。

![在这里插入图片描述](/static/img/images/02558.png)

虽然有很多不同的记号，但我们还是最常用大O，因为它悲观看算法性能，描述了算法最差的度量，算法最差也差不多是大O了。

下面具体学怎么算大O，

也就是“刻度”

![在这里插入图片描述](/static/img/images/02559.png)

![在这里插入图片描述](/static/img/images/02560.png)

![在这里插入图片描述](/static/img/images/02561.png)

![在这里插入图片描述](/static/img/images/02562.png)

![在这里插入图片描述](/static/img/images/02563.png)

举例

![在这里插入图片描述](/static/img/images/02564.png)

这个算法就是指数级别的，而且不好优化。

![在这里插入图片描述](/static/img/images/02565.png)

![在这里插入图片描述](/static/img/images/02566.png)

![在这里插入图片描述](/static/img/images/02567.png)

[数据结构与算法]概论 P7-P9

[https://www.bilibili.com/video/av49361421?p=7](https://www.bilibili.com/video/av49361421?p=7)





![在这里插入图片描述](/static/img/images/02568.png)

![在这里插入图片描述](/static/img/images/02569.png)

![在这里插入图片描述](/static/img/images/02570.png)

![在这里插入图片描述](/static/img/images/02571.png)

**谈谈有穷性**

![在这里插入图片描述](/static/img/images/02572.png)

```
def hailstone(n):
    length = 1
    Hailstone = []
    Hailstone.append(n)
    while (1 < n):
        if (n % 2 == 1):
            n = (int)(3 * n + 1)
            Hailstone.append(n)
        else:
            n = (int)(n / 2)
            length += 1
            Hailstone.append(n)
    return length, Hailstone
print(hailstone(7))
print(hailstone(27))
```

output

![在这里插入图片描述](/static/img/images/02573.png)

![在这里插入图片描述](/static/img/images/02574.png)

其他学科探讨这个算法有穷性问题。（具体数学，专门探究各种算法背后的数学原理的）

我们这门课要研究的是，在正确性、确定性、可行性、有穷性已知的情况下，如何优化算法和数据结构，达到一个更好的计算过程。


**什么才是好算法？**

![在这里插入图片描述](/static/img/images/02575.png)

已知有：

![在这里插入图片描述](/static/img/images/02576.png)

如何度量数据结构和算法的好坏？

![在这里插入图片描述](/static/img/images/02577.png)

![在这里插入图片描述](/static/img/images/02578.png)

DSA

![在这里插入图片描述](/static/img/images/02579.png)

主要考虑时间成本，因为内存条不值钱，算法瓶颈往往卡在时间。

![在这里插入图片描述](/static/img/images/02580.png)

如何定义计算成本？

![在这里插入图片描述](/static/img/images/02581.png)

定义计算成本的时候，需要客观，理想化出一个模型出来，评价算法。

![在这里插入图片描述](/static/img/images/02582.png)

图灵机（抽象模型，为了度量算法复杂度）

![在这里插入图片描述](/static/img/images/02583.png)

如何用图灵机实现非负整数加一

最后复位，是为了规范化。

![在这里插入图片描述](/static/img/images/02584.png)

抽象模型，（抽象模型，为了度量算法复杂度）

![在这里插入图片描述](/static/img/images/02585.png)

![在这里插入图片描述](/static/img/images/02586.png)

[数据结构与算法]概论 P1-P6

之前使用milvus+vgg做图像检索，好像一切都是黑匣子，今日看到一篇pdf介绍图像检索。大体说来，使用一些滤波器提取图像内容的特征表达，然后使用索引加速的一些方式来做图像检索。想来milvus内部也是使用了KD-tree之类的算法搜索树。





- 相似检索

颜色、纹理、形状

局部特征点

词包（Bag of visual word）

- 大数据集的索引加速

KD-tree

局部敏感哈希（Locality Sensitive Hash）

![在这里插入图片描述](/static/img/images/04898.png)

![在这里插入图片描述](/static/img/images/04899.png)



pdf: 
```cpp
链接：https://pan.baidu.com/s/1BvuDhyXkdDKyoB2ofmzXJA 
提取码：4h7j 
--来自百度网盘超级会员V8的分享
```

【基于图像内容】图像检索 Image retrieval

是小波变换的内容，有空得学习一下小波变换：





[https://www.cnblogs.com/picassooo/p/13390115.html](https://www.cnblogs.com/picassooo/p/13390115.html)

【图像处理】Gabor滤波器 纹理特征提取

首先弄一个带宽高的服务器：




```
https://www.aliyun.com/minisite/goods?userCode=28kqeewo&accounttraceid=70263e6b6d5141c4807d779046c7ae45qyor
```

然后参考：

[https://www.cnblogs.com/6324/p/12516047.html](https://www.cnblogs.com/6324/p/12516047.html)

![在这里插入图片描述](/static/img/images/00268.png)

注意这个：

![在这里插入图片描述](/static/img/images/00269.png)

![在这里插入图片描述](/static/img/images/00270.png)

![在这里插入图片描述](/static/img/images/00271.png)

windows10如何使用：

[https://www.kuaidaili.com/doc/using/win10/](https://www.kuaidaili.com/doc/using/win10/)

CentOS 搭建服务器 阿里云使用

（1）用POST方法传输；





（2）用requests.post的json参数传是可以的，直接给，requests.post自动转成json；

（3）用requests.post的data参数传也是可以的，给成json字符串；

（4）POST的请求头部可给可不给，会自动识别，但是接口有自己特殊的请求头部的时候一定得给，比如下图：

![在这里插入图片描述](/static/img/images/00310.png)

写法1
```python
import requests
res = requests.post(url="http://0.0.0.0:8001/items/1",
                    json={
                        "name": "Foo",
                        "description": "A very nice Item",
                        "price": 35.4,
                        "tax": 3.2,
                    },
                    headers={"Content-Type": "application/json; charset=UTF-8"}
                    )
print(res.text)
```

写法2
```python
import json
import requests
res = requests.post(url="http://0.0.0.0:8001/items/1",
                    data=json.dumps({
                        "name": "Foo",
                        "description": "A very nice Item",
                        "price": 35.4,
                        "tax": 3.2,
                    }),
                    headers={"Content-Type": "application/json; charset=UTF-8"}
                    )
print(res.text)
```

Python requests post application/json

# 四种POST 请求方式：





[https://imququ.com/post/four-ways-to-post-data-in-http.html#toc-2](https://imququ.com/post/four-ways-to-post-data-in-http.html#toc-2)

Content-Type: application/x-www-form-urlencoded  最原始表单，参数单一，不能传文件。

Content-Type:multipart/form-data  改进后的表单，能传文件。

Content-Type: application/json  倾向于传json，json规范导致前后端传数据都喜欢用这个，数据生产和消费简单。

# FastAPI 中如何支持

[https://fastapi.tiangolo.com/zh/tutorial/schema-extra-example/](https://fastapi.tiangolo.com/zh/tutorial/schema-extra-example/)

把函数参数改为Body解析即可，而不是FORM解析。

```python
# -*- coding:utf-8 -*-
import traceback
import uvicorn
from typing import Optional
from fastapi import Body, FastAPI
from pydantic import BaseModel
from fastapi.middleware.cors import CORSMiddleware
app = FastAPI(
    title='FastAPI',
    description='FastAPI',
    version='1.0.0',
    docs_url='/docs',
    redoc_url='/redocs',
)
app.add_middleware(
    CORSMiddleware,
    allow_origins=["*"],
    allow_credentials=True,
    allow_methods=["*"],
    allow_headers=["*"],
)
class Item(BaseModel):
    name: str
    description: Optional[str] = None
    price: float
    tax: Optional[float] = None
@app.post("/items/{item_id}")
async def update_item(
        item_id: int,
        item: Item = Body(
            ...,
            example={
                "name": "Foo",
                "description": "A very nice Item",
                "price": 35.4,
                "tax": 3.2,
            },
        ),
):
    results = {"item_id": item_id, "item": item}
    return results
if __name__ == '__main__':
    uvicorn.run('fastapia:app', host='0.0.0.0', port=8001, reload=False, debug=False, workers=1)
```

# PostMan 测试

修改请求头

![在这里插入图片描述](/static/img/images/00319.png)

写raw的原生json字符串

![在这里插入图片描述](/static/img/images/00320.png)


```python
import requests
requests.post(url="http://0.0.0.0:8001/items/1",
              json={
                  "name": "Foo",
                  "description": "A very nice Item",
                  "price": 35.4,
                  "tax": 3.2,
              },
              )
```

FastAPI python content-type: application/json

参考:[https://blog.csdn.net/haveanybody/article/details/86494063](https://blog.csdn.net/haveanybody/article/details/86494063)





# 基础

cv2 打开图片，tensor的shape是（im_height, im_width, channel），BGR格式。**cv2.imread返回的是numpy.ndarray张量。**

pillow 打开图片，RGB格式。Pillow读出来的是PIL.Image.Image对象。

# 打开图片与保存图片

```python
##PIL 读取、保存图片方法
from PIL import Image
img = Image.open("eee.jpg")
img.save("eee_result.jpg")
##cv2 读取、保存图片方法
import cv2
img = cv2.imread("eee.jpg")
cv2.imwrite("eee_result.jpg", img)
##图片文件打开为base64
import base64
def img_base64(img_path):
    with open(img_path, "rb") as f:
        base64_str = base64.b64encode(f.read())
    return base64_str
```

# CV2中的  BGR转RGB

```python
from matplotlib import pyplot as plt
import cv2
img = cv2.imread("eee.jpg")
cv2.imwrite("eee_result.jpg", img)
imgrgb = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)
plt.imshow(imgrgb)
plt.show()
```

# PIL CV2 的相互转换

```python
## PIL转cv2
import cv2
from PIL import Image
import numpy as np
img_rgb = Image.open("eee.jpg")
img_bgr = cv2.cvtColor(np.asarray(img_rgb), cv2.COLOR_RGB2BGR) # 成为cv2的numpy.ndarray
```

```python
## PIL转cv2
import cv2
from PIL import Image
img_bgr = cv2.imread("eee.jpg")
img_rgb = Image.fromarray(cv2.cvtColor(img_bgr, cv2.COLOR_BGR2RGB)) # 成为Pillow的PIL.Image.Image对象
```


# PIL base64 的相互转换

```python
##PIL转base64
import base64
from io import BytesIO
from PIL import Image
def pillow_to_base64(image):
    img_buffer = BytesIO()
    image.save(img_buffer, format='JPEG')
    byte_data = img_buffer.getvalue()
    base64_str = base64.b64encode(byte_data)
    return base64_str
# example
img = Image.open("eee.jpg")
print(pillow_to_base64(img))
```

```python
##PIL转base64
import base64
from io import BytesIO
from PIL import Image
def base64_to_pillow(base64_str):
    image = base64.b64decode(base64_str)
    image = BytesIO(image)
    image = Image.open(image)
    return image
# example
with open("eee.jpg", "rb") as f:
    base64_str = base64.b64encode(f.read())
print(base64_to_pillow(base64_str))
```

# CV2 base64 的相互转换

```python
# cv2 转 base64
import base64
import cv2
def cv2_to_base64(image):
    base64_str = cv2.imencode('.jpg', image)[1].tostring()
    base64_str = base64.b64encode(base64_str)
    return base64_str
# example
image = cv2.imread("eee.jpg")
print(cv2_to_base64(image))
```

```python
# base64 转 cv2
import base64
import numpy as np
import cv2
from PIL import Image
from io import BytesIO
def base64_to_cv2(base64_str):
    imgString = base64.b64decode(base64_str)
    nparr = np.frombuffer(imgString, np.uint8)
    image = cv2.imdecode(nparr, cv2.IMREAD_COLOR)
    return image
# example
with open("eee.jpg", "rb") as f:
    base64_str = base64.b64encode(f.read())
print(base64_to_cv2(base64_str))
```


# FastAPI中bytes 转CV2

```python
img = cv2.imdecode(np.frombuffer(file, dtype=np.uint8), cv2.IMREAD_COLOR)
```

# FastAPI中uploadfile  转CV2

```python
img = cv2.imdecode(np.fromstring(fileb.file.read(), np.uint8), cv2.IMREAD_COLOR)
```


# CV2 numpy  转成 字节流（open("file.jpg",'rb')）

参考：[https://blog.csdn.net/sinat_29957455/article/details/107208432](https://blog.csdn.net/sinat_29957455/article/details/107208432)

```python
img = cv2.imread("lpr1.png")
# 对数组的图片格式进行编码
success, encoded_image = cv2.imencode(".jpg", img)
# 将数组转为bytes
f = encoded_image.tobytes()
```

cv2 pillow base64 bytes uploadfile 图片文件之间的转换 FastAPI

#  FastAPI 服务





下面是代码，

`@app.post("/files/")` 路由让我们可以传文件。

`@app.post("/uploadfiles/")`路由让我们可以传多个文件。

需要保证：

（1） uvicorn.run中写的是文件名：app名，确保自己的文件名。

（2）`# python 3.8   pip install fastapi uvicorn python-multipart`

```python
# -*- coding:utf-8 -*-
import traceback
from typing import List, Optional, Union
import uvicorn
from fastapi.middleware.cors import CORSMiddleware
from fastapi import FastAPI, File, Form, UploadFile
import cv2
import numpy as np
app = FastAPI(
    title='FastAPI Tutorial',
    description='FastAPI教程',
    version='1.0.0',
    docs_url='/docs',
    redoc_url='/redocs',
)
app.add_middleware(
    CORSMiddleware,
    allow_origins=["*"],
    allow_credentials=True,
    allow_methods=["*"],
    allow_headers=["*"],
)
@app.post("/files/")
async def alg_file(
        fileb: UploadFile = File(...),
        token: str = Form(...)
):
    try:
        img = cv2.imdecode(np.fromstring(fileb.file.read(), np.uint8), cv2.IMREAD_COLOR)
        return {
            "token": token,
            "filename": fileb.filename,
            "content_type": fileb.content_type,
            "size": img.shape
        }
    except:
        traceback.print_exc()
        return -1
@app.post("/uploadfiles/")
async def create_upload_files(files: List[UploadFile] = File(...)):
    return {"filenames": [file.filename for file in files]}
@app.post("/filesper/")
def filesper(
        file: Optional[bytes] = File(None),
        fileb: Optional[UploadFile] = File(None),
        filepath: Optional[str] = Form(None),
):
    try:
        if file:
            img = cv2.imdecode(np.frombuffer(file, dtype=np.uint8), cv2.IMREAD_COLOR)
            return {
                "size": img.shape,
                "style": "bytes"
            }
        if fileb:
            img = cv2.imdecode(np.fromstring(fileb.file.read(), np.uint8), cv2.IMREAD_COLOR)
            return {
                "filename": fileb.filename,
                "content_type": fileb.content_type,
                "size": img.shape,
                "style": "UploadFile"
            }
        if filepath:
            return {
                "str": filepath,
                "style": "str"
            }
    except:
        traceback.print_exc()
        return -1
if __name__ == '__main__':
    uvicorn.run('yolo5fastapi:app', host='0.0.0.0', port=8001, reload=False, debug=False, workers=1)
```


#  requests 测试

## requests 单一文件上传

测试上传一个图片文件：

```python
import requests
url = "http://0.0.0.0:8001/files/"
with open("/home/kevin_xie/yifeinfs/pycharm_k/yolov5_v2/kevin/picture/realcamera.jpg", "rb") as f:
    res = requests.post(url=url, data={"token": "sdas"}, files={"fileb": f}, timeout=None)
    print(res.json())
```

返回：

```python
{'token': 'sdas', 'filename': 'realcamera.jpg', 'content_type': '', 'size': [720, 1280, 3]}
```

## requests 多个文件上传

注意给文件参数的方式，元组和列表均可，可自由尝试。
```python
import requests
url = "http://0.0.0.0:8001/uploadfiles/"
with open("/home/kevin_xie/yifeinfs/pycharm_k/yolov5_v2/kevin/picture/realcamera.jpg", "rb") as f:
    res = requests.post(url=url, files=[("files", f), ("files", f), ("files", f)], timeout=None)
    print(res.json())
```

Python fastapi requests 传文件方式 上传文件 上传多个文件 UploadFile模板方式 上传图片

# 1 Flask 路由阻塞





当启动一个Flask APP如下，在同一浏览器开2个窗口访问这个服务（我的是http://172.18.43.32:8001/hello），前一个请求没返回时，另外一个窗口的相同请求不会有反应。

这是浏览器的锅，同一请求会顺序执行，此时可以用同一台电脑的不同浏览器测试，可以发现不会存在路由阻塞。
```python
import time
from flask import Flask
app = Flask(__name__)
@app.route('/hello')
def hello_world():
    print("receive !")
    time.sleep(20)
    return 'Hello World!'
if __name__ == '__main__':
    app.run(host='0.0.0.0', port=8001)
```

# 2 requests访问

- 换个方式，使用requests访问，线程池中100个线程同时执行访问：

```python
import requests
from concurrent.futures import ThreadPoolExecutor
def task():
    res = requests.request(method="GET", url="http://172.18.43.32:8001/hello", timeout=None)
executor = ThreadPoolExecutor(max_workers=100)
for i in range(100):
    executor.submit(task)
```

还是可以看见不会阻塞。


# 3 FastAPI 路由阻塞

下面的情况下，访问就会阻塞。


```python
# -*- coding:utf-8 -*-
import asyncio
import time
import uvicorn
from fastapi.middleware.cors import CORSMiddleware
from fastapi import FastAPI, File, Form, UploadFile
import cv2
import numpy as np
app = FastAPI(
    title='FastAPI Tutorial',
    description='FastAPI教程',
    version='1.0.0',
    docs_url='/docs',
    redoc_url='/redocs',
)
@app.get("/hello")
async def hl():
    print("receive !")
    time.sleep(20)
    return {
        "token": "ads"
    }
def fastweb():
    uvicorn.run('deal:app', host='0.0.0.0', port=8001, reload=False, debug=False, workers=1)
if __name__ == '__main__':
    fastweb()
```

原因：在async标识的函数中使用同步方法time.sleep(20)，这导致了一个异步程序之间的同步问题，出现了错误！这种写法本身就是错误的，加async 是想利用Python的协程机制 将路由变成异步请求， 进一步提高并发量！只要考虑加async ，那么就得好好设计函数内部， 多用一些异步方法，比如可以写成：

```python
@app.get("/hello")
async def hl():
    print("receive !")
    await asyncio.sleep(20)
    return {
        "token": "ads"
    }
```

设计合理就会极大利用起协程异步，从而极大提高并发量，设计不合理就是呆瓜。若是分不清，还是老老实实和Flask一样写法：

```python
@app.get("/hello")
def hl():
    print("receive !")
    time.sleep(20)
    return {
        "token": "ads"
    }
```

这样也是出现不了路由阻塞的。

# 4 总结：同步并发 异步并发

1 Flask 中的属于同步并发，可以无阻塞访问！但要注意别让浏览器欺骗你！

2 FastAPI 支持异步框架，支持是支持，前提是你得用好它，不然就呆瓜。用好了并发量就提升了！

3 FastAPI 中同样支持Flask 那样子的同步并发，和Flask 一样一样的，但要注意写法！

4 FastAPI 貌似比 Flask 更强大！

# 参考

java web

golang 协程