图的存储形式

一. 图的2种存储形式:

1. 邻接矩阵法，底层依赖一个二维数组。每个顶点都有自己的一个独立的行，其他顶点作为自己的列，与自己有关系的，就在当前行所在的列做标记，可以表示有向图、无向图、加权图。

图的遍历方式

堆的存储结构可以想象成一个数组，索引i为顶点，2i为左节点，2i+1为右节点，堆是一种特殊的树，首先它是一个完全二叉树，其次每个顶点要么大于等于，要么小于等于其叶子节点。叶子节点均靠左排列。

堆的应用场景

top k 问题

堆是维护动态集合最值的利器，需要从业务场景中分析是用大顶堆还是小顶堆， 如top k, 需要维护一个小顶堆，数据到来时，判断是否大于堆顶元素，如果大于将堆顶元素替换堆顶元素，然后重新堆化，从堆顶元素开始堆化，可能会使堆的结构产生空洞，可以采用尾插法，将新来的元素插入堆尾，然后堆尾与堆顶交换重新堆化。

优先级队列

准备python环境

1. 用brew安装

1

brew install python3

1. 查看bin目录位置

   • brew 安装后的软件通常会在 /usr/local/bin有指向/usr/local/Cellar相对应软件的软连，而/usr/local/bin 通常情况下已经在你的环境变量中，如果你的系统没有其他版本的python的话，直接使用即可。
   • 由于mac系统下可能会存在其他版本的python.如果启用自定义安装的版本需要覆盖掉默认的版本，可以配置环境变量 ~/.bash_profile 或 ~/.zshrc 配置你的别名指向位置

1
2

alias python="/usr/local/bin/python3.9"
alias pip=/usr/local/bin/pip3.9

安装 django

pip install —upgrade pip

python -m pip install Django

pip install mysqlclient #mac 使用mysqlclient 需要找到libmysqlclient.21.dylib路径并导入环境变量 e.g export LD_LIBRARY_PATH=/usr/local/mysql-8.0.22-macos10.15-x86_64/lib/

pip install pytz

pip install djangorestframework # see: https://www.django-rest-framework.org/

pycharm install djangorestframework

体验

todo 

OpenResty 中有两个缓存的组件：shared dict 缓存和 lru 缓存。前者只能缓存字符串对象，缓存的数据有且只有一份，每一个 worker 都可以进行访问，所以常用于 worker 之间的数据通信,同时还支持对过期的数据进行访问获取。后者则可以缓存所有的 Lua 对象，但只能在单个 worker 进程内访问，有多少个 worker，就会有多少份缓存数据。

lua-resty-mlcache

这个库可以作为 key/value存储来处理，也可以缓存Lua类型和表，构建在lua_shared_dict，lua-resty-lrucache上 ，这种组合可以实现高性能和灵活的缓存。

软件包准备

1.RabbitMQ版本 和 Erlang 版本兼容性关系

1

https://www.rabbitmq.com/which-erlang.html

2.官方下载地址

1
2
3
4
5

【erlang下载地址】：https://github.com/rabbitmq/erlang-rpm/releases
 
【socat下载地址】：http://www.rpmfind.net/linux/rpm2html/search.php?query=socat(x86-64)
 
【rabbitmq下载地址】：https://github.com/rabbitmq/rabbitmq-server/releases

3.安装包中说明，请下载对应的安装包

1
2
3

el6：CentOS 6.x 的下载
el7：CentOS 7.x 的下载
el8：CentOS 8.x 的下载

安装步骤

hashtable是由数组和列表两种数据结构组合而成的，这里面有两个重要的知识点需要掌握，一个是如何对哈希表进行动态扩容，第二个如何巧妙的设计一个散列性和性能都非常好的散列函数。

数组的特点是在内存中地址是连续的，所以在随机访问一个数组中的地址的时间复杂度是O(1),寻址公式大概是：

1
2
3
4
5
6
7
8
9

	
int a[3] = {1,2,3};

a[i]_address = begin_address + i * data_type_size

int a[3][2] = {{1,2},{6,7},{3,5}};

address = begin_address + ( i * n + j) * data_type_size

数组由于对内存的要求比较苛刻，带来的一个问题就是低效的“插入”和“删除”，在做数据的插入和删除的时候要频繁的进行数据的迁移。对于数组的动态扩容策略的实现可以参考redis的字符串底层实现原理或者java中的arrayList<>.

:cherries: Linux下默认字节对齐是以int类型变量所占字节数对齐，也就是说会申请被4整除的内存地址写入int类型，所以这就是我们每次看int类型的地址不会看到有奇数的。

什么叫对齐

计算机中内存空间都是按照byte划分的，从理论上讲似乎对任何类型的变量的访问可以从任何地址开始，但实际情况是在访问特定类型变量的时候经常在特 定的内存地址访问，这就需要各种类型数据按照一定的规则在空间上排列，而不是顺序的一个接一个的排放，这就是对齐。

为什么要进行对齐