算法:深度优先搜索(DFS)
算法:深度优先搜索(DFS)在算法:广度优先搜索(BFS)(最短路径)中,我们提到了按照广度优先遍历的搜索方式,使用队列作为常规的搜索方式,与之相对应的为深度优先搜索(DFS) 如果说BFS对应着树结构的前中后序遍历 但是DFS相对解法较为多元一些,有些时候不得不使用递归进行求解 同时,有很多求解只是进行图的遍历,不关心是广度还是深度优先,其解都是相同的 在这里我们暂且不讨论的基于栈而是侧重基于递归的遍历实现 对于二叉树,最常见的遍历方式有前序(又称 先序)遍历、中序遍历、后序遍历、层次遍历 前中后序只为取得的值先后顺序不同,即递归有先后 依赖栈实现的的深度优先是前序遍历 以下是一个二叉树的前序遍历代码实现:
![算法:深度优先搜索(DFS)]()
2020-06-27鱼鱼
盘点redis中特殊的数据类型 HyperLogLog Bitmap
盘点redis中特殊的数据类型 HyperLogLog Bitmap 基数计数(cardinality counting)通常用来统计一个集合中不重复的元素个数,例如统计某个网站的UV,或者用户搜索网站的关键词数量 数据分析、网络监控及数据库优化等领域都会涉及到基数计数的需求 要实现基数计数,最简单的做法是记录集合中所有不重复的元素集合S_uSu,当新来一个元素x_ixi,若S_uSu中不包含元素x_ixi,则将x_ixi加入S_uSu,否则不加入,计数值就是S_uSu的元素数量 这种做法存在两个问题: 当统计的数据量变大时,相应的存储内存也会线性增长 当集合S_uSu变大,判断其是否包含新加入元素x_ixi的成本变大 大数据量背景下,要实现基数计数,首先需要确定存储统计数据的方案,以及如何根据存储的数据计算基数值;另外还有一些场景下需要融合多个独立统计的基数值,例如对一个网站分别统计了三天的UV,现在需要知道这三天的UV总量是多少,怎么融合多个统计值
![盘点redis中特殊的数据类型 HyperLogLog Bitmap]()
2022-01-12鱼鱼
并发之AQS全解析
并发之AQS全解析我们知道juc(java.util.concurrent)包下有很多实用的类,提供了很多并发工具,例如线程池、原子类、并发工具、信号量工具、锁等,可以说基本实现都为悲观锁,底层原理基本都使用了AQS(AbstractQueuedSynchronizer),AQS不是一种概念,是并发中实打实的工具类 本篇文章针对AQS做解析 AQS是多线程访问共享资源的同步器框架 AQS的资源可以是独占的也可以是共享的 我们先来简单看一下它的使用方式和ApI(因为是抽象类,是不能直接使用的),下图是AQS的整体脉络 AQS核心就是一个状态值state,同时维护了一个线程的阻塞队列,队列的节点为有两种状态:SHARED(共享)和EXCLUSIVE(独占),节点状态有五种:
![并发之AQS全解析]()
2021-03-12鱼鱼
多线程应用提高(IV) 线程安全的集合类
多线程应用提高(IV) 线程安全的集合类在Java中的数据结构一篇中,列举了Java中一些常见的集合,此文主要梳理线程安全的相关集合 我们知道,当一个实例对象只能被一个线程访问时(线程私有),无论如何都不会有线程安全的问题,但在多线程的情境下,多个线程操作同一个对象时,可能会出现更新丢失、读写数据不同步、计数击穿等现象,此时这种操作就是非线程安全的 相应地,线程安全的集合有这样的特点:在多个线程操作同一集合时,能保证每一步操作都是安全的,与串行执行的结果一致,不会出现数据不同步等预料之外的问题 可以先看这个小例子Java-lab/ListT.java at master · fishstormX/Java-lab,我在里面解释了
![多线程应用提高(IV) 线程安全的集合类]()
2019-07-13鱼鱼
Redis高级特性:事务和pipelined以及在RedisTemplate中的应用
Redis高级特性:事务和pipelined以及在RedisTemplate中的应用Redis Pipelined是由Client提供的(是防止client端 阻塞的操作)一种请求redis的方式 Redis本身具有很高的吞吐量,因此性能最大的考察便是网络状况,如果应用到redis的网络状况不好,每次请求都将会出现轻微的 阻塞和延迟,这种延迟对于批量请求是很可怕的,譬如要进行数千次数据插入,或是批量获取数据时,我们就需要用到Pipelined Pipelined可以将多个请求无 阻塞的发出并按顺序将请求结果“打包”返回,这有点类似于并发请求,可以有效地利用等待结果的 阻塞时间 注意,Pipelined并不能保证原子性,即pipelined执行的内容可能会被其他客户端或是线程的指令"插队",若想要原子性操作,需要使用事务
![Redis高级特性:事务和pipelined以及在RedisTemplate中的应用]()
2020-06-21鱼鱼
JVM与GC
JVM与GCJMM,长下面这个样子: 其中,堆和栈区自然不做介绍了,主要介绍: 程序计数器:线程私有的,记录正在执行的字节码地址,换言之,它告诉我们某线程执行到了那里,分支、循环等也会依赖这个来执行,这一区域不会发生OOM问题 栈:就是正常所指的栈,每个方法被执行的时候都会同时创建一个栈帧(Stack Frame )用于存储局部变量表、操作栈、动态链接、方法出口等信息 每一个方法被调用直至执行完成的过程,就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程,这一区域会发生StackOverflow问题 堆:就是正常所指的堆,这里是GC的主要区域 方法区:线程私有的,是各个线程共享的内存区域,它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据,运行时常量池也包含在里面

2019-03-28鱼鱼
Elasticsearch 入门
Elasticsearch 入门(注:本篇文章基于Elasticsearch7.7.0版本,由于版本的差异性造成的内容不一致我会尽量在文中标出,但是) Elasticsearch是基于Lucene扩展的全文搜索引擎,当我们有对大数据量的处理和搜索时,全文搜索引擎是最佳的选择,同时他提供了高扩展性、高可用性、RestFul风格的API和友好的分布式部署配置,在此我们不予详述 我们日常使用的数据库索引是数据库一种编排数据(逻辑上)从而加快查询的手段,我们暂且将这种索引方式称为正排索引,他通过对待搜索字符寻址从而找到对应的数据 但是这种索引方式对于模糊匹配会出现"断档"现象(模糊符号后的片段无法走索引查找),并且对于海量数据无论在存储上还是在查找上都略显吃力,于是在Elasticsearch中引入了倒排索引来加快查询速度

2020-03-06鱼鱼
算法1
算法1给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水) 木板组成水桶装水,定义高度为一数组,间隔为1,求水桶最大容量如[1,5,1,2,6,3]为15,解题思路:自两边木板向中间遍历求容量,每次相对短的木板向内移动,共比较n-2次 将水灌满,求灌满后的高度,其实就是从最高点向左右两个方向向中间遍历,依次求经过的最大值,这样一来就是从最高点向两侧递减的,再减去柱子原高度即可 容易理解的想法还有按高度分层计算,但是时间复杂度过高

2019-03-14Sherlock
Spring的事务
Spring的事务Spring事务将一系列操作绑定为具有原子性的操作,此篇文章讲基于Spring提供的声明式事务 MySQL的事务我们已经明白,Spring的事务是委派了ORM框架来解决相应的问题,在jdbc中,体现的就是在Mybatis框架中,体现的就是SqlSession的建立到提交 声明式事务:在方法或是实现类上加上以下注解: 其中一些常用参数: propagation:配置事务传播行为;(后面详细解读) isolation:事务隔离级别; timeout:超时时间; roolbackFor:导致事务回滚的异常类设置; readOnly:boolean,是否只读 有七种事务传播行为,用来决策当发生事务嵌套时的解决方案
![Spring的事务]()
2019-07-18鱼鱼
ELK实战(Ⅰ) 基于ELK整合分布式业务日志
ELK实战(Ⅰ) 基于ELK整合分布式业务日志大多情况下,我们可能都习惯了使用linux指令查看日志,很多时候一句简简单单的tail、grep能定位绝大多数问题 但是面临复杂的目录结构和分布式系统产生的“分布式日志文件”,如果还要我们一个一个去查日志,就会耗费很多没必要的时间 可以利用ELK这套组件快速搭建一个日志系统 注意此文仅针对可能很多情况下格式不确定的业务日志,对于某些组件日志我们有更好的可视化实践方式,可以参考此系列的其他文章 对于一个日志系统,我们要确认我们的诉求,在不同的场景下采用不同的收集方式: 是否是分布式系统需要合并多个节点的日志 如果需要,则需要用分布式组件收集并合并日志,这也是一个日志系统最基本的要求;

2020-03-14鱼鱼
Consul高级应用:多数据中心,模板与Client(Zuul)
Consul高级应用:多数据中心,模板与Client(Zuul)此文整理了Consul比较实用的高级功能:多数据中心,模板与维护模式 Consul提供了多数据中心联动的特性,目前看来多数据中心只是在查询阶段提现,各个数据中心的数据持久化和数据目录(k-v对)的更新不相干扰 也就是说,多数据中心的特性目前看来不能作为可用性的保障,当然 不排除可以手动热切换数据中心 最好判断是否使用多数据中心的情形是判断服务是否属于同一系统下,是否相同serviceId能提供相同的无状态服务,以下列举一些情景: 一个系统拥有多个域名的多套部署,提供版本一致的服务(建议使用多数据中心) 一个系统由多个服务器提供的不同服务提供(视服务具体情况,不建议使用多数据中心)

2020-01-28鱼鱼
IO与NIO
IO与NIO我们都知道IO流传输,其实IO模型有很多,例如BIO、NIO、AIO等,传统的IO都是同步的 IO为各种流操作 IO操作分类 I IO操作分类 II 其中,输入流可以为InputStream和Reader,分别为字节流和字符流,对应地,输出流为OutputStream和Writer,具体的使用在此不详述 NIO是IO模型中后推出的新IO模型 NIO并不一定是多线程的,但是NIO是多管道的,利用缓冲作为中间介质进行数据传输,运用的其实是多路复用技术,它恰恰是通过减少线程数量从而减少上下文的频繁切换,提高性能 Channel:通道,相当于一个连接,不能直接输出数据,只能与Buffer交换数据

2019-05-11鱼鱼