FinkykyBlog

finkyky的个人博客

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存在的这个问题要怎么解决呢？可以想想思路，下篇文章进行揭秘 : )

最后，欢迎大家关注我的个人公众号（白话编程），一起学习、一起进步！