0%

最近重新刷了树相关的题目,然后发现一个很有意思的点。

###1、题目列表如下:

  • 层序遍历二叉树
  • 层序遍历二叉树,按层输出
  • 层序遍历n叉数
  • 层序遍历n叉数,按层输出
  • 获取二叉树/n叉数最左/最右下角的值
  • 求二叉树或者n叉数的深度

2、分析

乍一看这些题目似乎都没啥联系,但只要分析一下,就不难发现,其实都是一个套路。

我们来分析遍历n叉数,按层输出这道题。

我们遍历每一层,然后标记当前到了哪一层,如果遍历到下一层的话,对应level进行累加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<List<Integer>> result = new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
if(root == null)return 0;
bfs(root,0);
return result;
}
private void bfs(TreeNode node,int level){
if(node == null)return;
if(level > result.size()-1){
result.add(new ArrayList());
}
result.get(level).add(node.val);
bfs(node.left,level+1);
bfs(node.right,level+1);
}

3、再来回顾其他题目

我们来看其他题目,无非就是返回值少做更改而已。

比如返回二叉树/n叉数最左下角的值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<List<Integer>> result = new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
if(root == null)return 0;
bfs(root,0);
return result.get(result.size()-1).get(0); // 返回值稍微有些不同
}
private void bfs(TreeNode node,int level){
if(node == null)return;
if(level > result.size()-1){
result.add(new ArrayList());
}
result.get(level).add(node.val);
bfs(node.left,level+1);
bfs(node.right,level+1);
}

比如计算树的深度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<List<Integer>> result = new ArrayList<>();
public int findBottomLeftValue(TreeNode root) {
if(root == null)return 0;
bfs(root,0);
return result.size(); // 返回result的大小即可
}
private void bfs(TreeNode node,int level){
if(node == null)return;
if(level > result.size()-1){
result.add(new ArrayList());
}
result.get(level).add(node.val);
bfs(node.left,level+1);
bfs(node.right,level+1);
}

骚操作不断,但是挺好玩的。我觉得学习、刷题,就是一个扩展思维、大胆猜想的过程。多多总结、多多进步!

学习一个技术,只是纯粹在泛泛而学的话,其实没有多大意思,很容易忘记的,最好的方式就是进行梳理和实践分析,在深度的思考和实践中吃透!

1
2
本文让我们来探索一下,在单机模式下,从跟server建立连接、到执行一句get/set命令,是怎么执行的。
通过剖析这些底层内核,加深我们对redis的理解!

一、客户端是如何跟redis server建立连接的?

我们思考一下,平时我们写的业务系统,是如何跟服务器端的redis server建立连接的?

拿 Java 的业务系统来说,大致步骤如下:

1、引入对应的客户端 jar 包

常见的redis 客户端包括 jedis、redisson、lettuce

拿jedis为例,建立好maven工程后,引入对应的pom依赖:

1
2
3
4
5
<dependency>
<groupId>redis.clients</groupId>
<artifactId>jedis</artifactId>
<version>3.3.0</version>
</dependency>

2、进行对应的redis相关配置

要想跟redis建立连接,肯定需要知道redis server的对应配置信息吧?

像服务端的ip地址、对应redis的端口号、密码等信息你得知道吧,不然咋跟远方的redis服务建立起网络连接!

1
2
3
4
redis:
host: 192.xx.xx.xx // 对应ip地址
password: // redis对应密码
port: 6379 // redis对应的服务端口

3、socket 概念

两个设备之间建立网络连接,双方都会基于各自的某个端口建立对应的socket套接字。

然后基于这个socket连接通信链路来发送和传递数据消息。

4、总结一下

1)我们的业务系统这边,通常会使用一个客户端比如说jedis,通过tcp三次握手,跟服务器那边的redis server建立好网络连接。

2)建立连接时,各自会创建一个socket监听对应的端口,以后的数据传输都是通过该socket端口来进行发送。

3)客户端现在要请求某条数据,那么此时就通过socket通信链路发送给server端

4)server端收到客户端请求后,进行一些处理,然后返回响应数据。

这篇文章讲述了建立连接时业务系统(客户端)这边会做的事情。

下一篇文章来讲下redis server端会发生什么!

[TOC]

如何给20G大小的高考成绩文件进行排序?

这个问题很值得思考,每年高考/考研之后,几百甚至几千万考生的成绩,如何才能排好序呢?这是个值得思考的问题,这篇文章来进行一波分析。

一 问题分析

  1. 问题的要求是对给定的一份20G的成绩文件进行排序,不存在说文件内存在其他特殊字符之类的异常数据。
  2. 进行排序的环境不确定,可能是单机(在一台机器上完成)、也可能是多机集群同时进行处理。
  3. 单机的内存是有限的,假设每台机器的内存只有3GB。
  4. 排完序后要求得到一份排好序的文件。
  5. 假设磁盘不低于50GB。

二 单机情况下的处理

1、首先由于内存有限,没有办法一次性将所有20GB的文件都读取到内存中。

2、所以考虑每次只加载2G到内存中,为了保证数据区间能够均匀地分布,采用哈希分片将文件分批读取到内存

为什么每次不加载3G呢?

注意,内存总量为3GB,如果将3GB都用来放成绩数据,其他程序和数据就没地放了。

3、对内存中的数据进行排序(使用堆排序/快速排序或者Tim排序)

4、将排好序的内容单独生成一个文件,放到硬盘上

5、继续重复将剩下的18G数据按照①、②、③、④步骤进行处理,处理10次之后,此时硬盘上有10份排完序的成绩小文件

6、将这10份排好序的小文件合并成一份大文件

首先创建一个大小为10的数组,然后依次从10个文件中找出第一个数,写到原来文件中(直至最终排序完成)

(由于前面有将数据进行哈希分片,所以数据区间是均匀的,能够保证每个文件的第一个数值是这段区间内的最小值/最大值,而且不会存在于其他区间上

7、由于每次只从文件中读取一行效率太低了,可以考虑给每个文件都加一个缓存,每次都读取这个前置缓存中的值,这样效率性能会大大提高。

三 多机集群环境下的处理

多机情况下也是类似的,可以考虑将文件数据均匀放到各个机器上,每个数据都落到对应的数据区间中。

然后进行排序,排完序后有多个有序的小文件,再考虑将这些个小文件给合并成大文件就好了(思路跟单机处理中的大差不差)

四 总结

1、单机情况下由于内存资源限制,只能一步一步对文件进行排序,然后再将小文件合并成大文件。

2、多机情况要好得多,可以一次批量排序多组文件,排序效率会明显提升。

通过上面的学习,你也可以很轻松地对高考后的考生成绩进行排序了。不过好像我们也没有必要操这份心,毕竟我也不想知道我高考或者考研之后的排名 : )

[TOC]

1、来解决一个问题

Q:给定一组学生数据,数据格式为学号-学生姓名;现在要求:输入学生的学号,能够快速查询出学生的姓名。

A:如何解决上面的问题?思路有如下:

  • 遍历,直接暴力遍历,直到找到学生姓名
  • 使用哈希表,通过哈希表的key-value映射来查找
  • 使用数组下标映射的关系,通过将id作为学生下标来存储学生姓名。

位图1

2、位图

通过上面的问题,我们知道可以通过一 一映射的关系来进行数据快速存储查询。

**==位图:==**位图位图,就是只存储一位(0/1),通过0/1来判断true/false

Q:现在又有一个问题,假设有100万个整数,整数范围为0~3千万。问:如何快速确定某个数据是否在这100万个数据中?

A:来思考下如何解决,常见方案如下:

① 基于数组: 这种方式的话就要直接暴力遍历,伪代码如下:

1
2
3
for(int i = 0;i < nums.length;i++){
if(nums[i] == target)return i;
}

② 基于排序数组:这种方式是对上面方法的改进,通过排序后可以进行二分查找,提高查找效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Arrays.sort(nums);// 进行排序
// 二分查找伪代码
boolean binarySearch_r(int[] nums,int left,int right,target){
while(left <= right){
int mid = left+(right-left)/2;
if(nums[mid] == target)return true;
if(nums[mid] < target){
binarySearch_r(nums,mid+1,right);
}else{
binarySearch_R(nums,left,mid-1);
}
}
return false;
}

③ 基于哈希表:基于哈希表实现的话,维护对应的数值关系即可。

④ 基于一一映射的数组:就是使用数组,将有值的下标标记为true,否则标记为false。

⑤ 基于位图:基于上面方式的话,可以,但是true/false还是很占空间啊

我的需求只是要知道是不是有没有存在这个数而已

只有想不到没有做不到,我们思考一下能不能直接用0/1来存储每一位上的值。

实际上是可以的,通过使用char类型的数组,char是16个字节,64位,每位来保存对应的数据。

赋值:a[charIdx] |= (1<<bitIdx)

取值:a[charIdx] & (1<<bitIdx)

让每位的0/1表示有没有这个值

3、布隆过滤器

接着上面题目进行延伸,假设有1000万个整数,整数范围为0~1亿。问:如何快速确定某个数据是否在这1000万个数据中?

如果要接着使用位图的话,就要存储相当大的存储空间了。

但是我们转念一想,如果使用位图,并且对应的下标为哈希计算之后的值,这样可以减少存储空间。

只是,这样的话就很容易导致哈希冲突,也就是两次计算之后的值是一样的。

所谓的布隆过滤器,其实就是位图+容忍存在hash冲突的误判

我们假设使用上面图中的布隆过滤器判断某个值是否存在,如果存在的话例如:hash(354) == 1,hash(654) == 1,而hash(200) 肯定是0

这样的话,就算存在哈希冲突,也造不成多大的关系。

4、布隆过滤器的常见使用

通过使用布隆过滤器,我们可以快速地知道某个值是否存在数据中,大大提高查询速度。

比如,在判断某个数据是否存mysql中时,先访问缓存中的位图判断是否存在,如果数据压根不存在mysql中的话,就不用走库区查询了,减少数据库的操作。

总结

1、通过对数组对了解,我们知道数组的下标可以得到更好的利用

2、位图采用更少的空间消耗来存储数据,实现数据和一些业务目的一一映射

3、布隆过滤器是“粗糙版”的位图,通过布隆过滤器可以实现海量数据下的数据是否存在判断

[TOC]

1 回顾

通过上文 cpu多级缓存模型及存在问题 ,对 cpu 的结构和对应的多级缓存模型进行了介绍。

同时留下了一个问题,就是当多个 cpu 对同一数据进行操作时,由于数据没有从缓存刷回内存,导致计算后的数据不一致了。

cpu多级缓存模型存在的问题

2 mesi 缓存一致性协议

固本培元,我们思考问题的根本原因:发生数据不一致性的原因,就是另外的 cpu 没有办法及时感知到数据被改动了,没办法进行及时的数据更新

那么,有没有什么办法,在一个 cpu 进行数据修改时,及时感知到改动后的值并进行修改呢?

有的,mesi 缓存一致性协议就是用来解决数据不一致性问题的。

mesi协议要求:要求只要cpu改了本地的缓存,便立即将修改后的结果强制刷新会回主内存

3 实现数据一致

mesi 缓存一致性协议 是结合cpu嗅探技术来实现数据一致性的。

所谓的 cpu嗅探技术:嗅探嗅探,就是跟监听差不多嘛;一个cpu如果嗅探到其他cpu对某个变量做了修改,便将本地缓存中的数据给过期掉;那么,当该cpu读取本地缓存数据的时候,发现过期了,就会从主内存中取新的数据到缓存中。

如图,我们对int i = 0 进行计算,cpu1、cpu2都对 i 执行累加操作

1、首先cpu1、cpu2从内存读取数据到自己的缓存中此时,cpu1、cpu2中的i = 0

2、cpu1进行计算,并将结果放到缓存中,由于mesi协议,将修改过后的值强制刷回内存 此时,内存的值为1

3、cpu2 嗅探到值发生了改变,于是进行值过期 cpu2中的i过期掉,并且重新从内存中读取值

4、cpu2此时缓存中的值为 i = 1

总结

1、首先我们知道因为多个cpu同时对同一数据进行计算时,容易导致数据不一致性的问题。

2、解决这个问题需要保证:当一个cpu进行数据修改时,强制将修改后的数据刷回内存。同时其他cpu能够嗅探到数据发生了改变并进行过期掉,重新从内存中读取值。

这就是通过 mesi 缓存一致性协议和cpu嗅探技术,实现数据一致性。

最后,欢迎大家关注我的个人公众号(白话编程),一起学习、一起进步!

[TOC]

1、cpu的结构

我们来看看cpu的构造:

cpu包括:寄存器、控制单元、算数逻辑单元

cpu结构及对应功能

其中:

  • 控制单元:负责控制cpu工作
  • 逻辑运算单元:负责计算
  • 寄存器:存储要被计算的数字,包括通用寄存器、特殊寄存器、指令寄存器

总结:cpu就是用来计算和执行指令的,cpu从内存中读取数据和指令,然后进行对应的计算。

(我们屏蔽其他细节,知道cpu的职能即可)

2、cpu多级缓存模型

我们所知道的存储材料就包括:内存、硬盘

但是事实上,为了加快计算速度,每个cpu都有对应的cpu缓存(包括L1缓存、L2缓存和L3缓存)

cpu缓存结构

分级为:寄存器、L1、L2、L3、内存、硬盘 (就放在离cpu越远的位置,使用的制造材料也越便宜)

这些L1、L2、L3缓存价格相对更加昂贵,但是其执行速度要比内存快很多

3、cpu多级缓存和计算的关系

我们现在的电脑上,基本都是多核的(说人话也就是有多个cpu)

那么在进行计算时,每个cpu都会从主内存中读取数据到自己的缓存中

我们不能忘了cpu的核心就是计算和执行指令:cpu从内存中读取数据到对应的cpu缓存中,这样就能加快自己的运算速度

4、上面的cpu缓存模型有什么问题?

cpu缓存模型的问题可以看到,当cpu1从内存中读取值,并且进行了计算,但是此时结果还在自己的缓存中,没有刷回主内存

此时,cpu2读到修改前的值,并进行修改,这样数据就不一致了

总结

通过上面的学习,我们知道:

1、cpu是用来计算和执行指令的;

2、这些指令和对应的数据存放在内存中,为了加快计算速度,cpu从内存中读取这些数据到自己的缓存中

3、因为每个cpu都有对应的缓存,当一个cpu计算后、没来得及将计算的结果刷回内存中,就很容易导致数据不一致性问题。

那么对于cpu存在的这个问题要怎么解决呢?可以想想思路,下篇文章进行揭秘 : )

最后,欢迎大家关注我的个人公众号(白话编程),一起学习、一起进步!