技术

mosn有的没的 负载均衡泛谈 《Mysql实战45讲》笔记 单元测试的新解读 《Redis核心技术与实现》笔记 《Prometheus监控实战》笔记 Prometheus 告警学习 calico源码分析 对容器云平台的理解 Prometheus 源码分析 并发的成本 基础设施优化 hashicorp raft源码学习 docker 架构 mosn细节 与微服务框架整合 Java动态代理 编程范式 并发通信模型 《网络是怎样连接的》笔记 go细节 codereview mat使用 jvm 线程实现 go打包机制 go interface及反射 如何学习Kubernetes 《编译原理之美》笔记——后端部分 《编译原理之美》笔记——前端部分 Pilot MCP协议分析 go gc 内存管理玩法汇总 软件机制 istio流量管理 Pilot源码分析 golang io 学习Spring mosn源码浅析 MOSN简介 《datacenter as a computer》笔记 学习JVM Tomcat源码分析 Linux可观测性 学习存储 学计算 Gotty源码分析 kubernetes operator kaggle泰坦尼克问题实践 kubernetes自动扩容缩容 神经网络模型优化 直觉上理解机器学习 knative入门 如何学习机器学习 神经网络系列笔记 TIDB源码分析 《阿里巴巴云原生实践15讲》笔记 Alibaba Java诊断工具Arthas TIDB存储——TIKV 《Apache Kafka源码分析》——简介 netty中的线程池 guava cache 源码分析 Springboot 启动过程分析 Spring 创建Bean的年代变迁 Linux内存管理 自定义CNI IPAM 副本一致性 spring redis 源码分析 kafka实践 spring kafka 源码分析 Linux进程调度 让kafka支持优先级队列 Codis源码分析 Redis源码分析 C语言学习 《趣谈Linux操作系统》笔记 docker和k8s安全机制 jvm crash分析 Prometheus 学习 容器日志采集 Kubernetes 控制器模型 Kubernetes监控 容器狂占cpu怎么办? Kubernetes资源调度——scheduler 时序性数据库介绍及对比 influxdb入门 maven的基本概念 《Apache Kafka源码分析》——server Kubernetes objects 源码分析体会 《数据结构与算法之美》——算法新解 Kubernetes源码分析——controller mananger Kubernetes源码分析——apiserver Kubernetes源码分析——kubelet Kubernetes介绍 ansible学习 Kubernetes源码分析——从kubectl开始 jib源码分析之Step实现 jib源码分析之细节 线程排队 跨主机容器通信 jib源码分析及应用 为容器选择一个合适的entrypoint kubernetes yaml配置 《持续交付36讲》笔记 mybatis学习 程序猿应该知道的 无锁数据结构和算法 CNI——容器网络是如何打通的 为什么很多业务程序猿觉得数据结构和算法没用? 串一串一致性协议 当我在说PaaS时,我在说什么 《数据结构与算法之美》——数据结构笔记 PouchContainer技术分享体会 harbor学习 用groovy 来动态化你的代码 精简代码的利器——lombok 学习 《深入剖析kubernetes》笔记 编程语言的动态性 rxjava3——背压 rxjava2——线程切换 spring cloud 初识 《深入拆解java 虚拟机》笔记 《how tomcat works》笔记 hystrix 学习 rxjava1——概念 Redis 学习 TIDB 学习 分布式计算系统的那些套路 Storm 学习 AQS1——论文学习 Unsafe Spark Stream 学习 linux vfs轮廓 《自己动手写docker》笔记 java8 实践 中本聪比特币白皮书 细读 区块链泛谈 比特币 大杂烩 总纲——如何学习分布式系统 hbase 泛谈 forkjoin 泛谈 看不见摸不着的cdn是啥 《jdk8 in action》笔记 程序猿视角看网络 bgp初识 calico学习 AQS2——粗略的代码分析 我们能用反射做什么 web 跨域问题 《clean code》笔记 硬件对软件设计的影响 《Elasticsearch权威指南》笔记 mockito简介及源码分析 2017软件开发小结—— 从做功能到做系统 《Apache Kafka源码分析》——clients dns隐藏的一个坑 《mysql技术内幕》笔记2 《mysql技术内幕》笔记1 log4j学习 为什么netty比较难懂? 回溯法 apollo client源码分析及看待面向对象设计 学习并发 docker运行java项目的常见问题 Scala的一些梗 OpenTSDB 入门 spring事务小结 事务一致性 javascript应用在哪里 《netty in action》读书笔记 netty对http2协议的解析 ssl证书是什么东西 http那些事 苹果APNs推送框架pushy apple 推送那些事儿 编写java框架的几大利器 java内存模型 java exception Linux IO学习 netty内存管理 测试环境docker化实践 netty在框架中的使用套路 Nginx简单使用 《Linux内核设计的艺术》小结 Go并发机制及语言层工具 Linux网络源代码学习——数据包的发送与接收 《docker源码分析》小结 docker中涉及到的一些linux知识 hystrix学习 Linux网络源代码学习——整体介绍 zookeeper三重奏 数据库的一些知识 Spark 泛谈 链式处理的那些套路 netty回顾 Thrift基本原理与实践(二) Thrift基本原理与实践(一) 回调 异步执行抽象——Executor与Future Docker0.1.0源码分析 java gc Jedis源码分析 Redis概述 机器学习泛谈 Linux网络命令操作 JTA与TCC 换个角度看待设计模式 Scala初识 向Hadoop学习NIO的使用 以新的角度看数据结构 并发控制相关的硬件与内核支持 systemd 简介 quartz 源码分析 基于docker搭建测试环境(二) spring aop 实现原理简述 自己动手写spring(八) 支持AOP 自己动手写spring(七) 类结构设计调整 分析log日志 自己动手写spring(六) 支持FactoryBean 自己动手写spring(九) 总结 自己动手写spring(五) bean的生命周期管理 自己动手写spring(四) 整合xml与注解方式 自己动手写spring(三) 支持注解方式 自己动手写spring(二) 创建一个bean工厂 自己动手写spring(一) 使用digester varnish 简单使用 关于docker image的那点事儿 基于docker搭建测试环境 分布式配置系统 JVM内存与执行 git spring rmi和thrift maven/ant/gradle使用 再看tcp 缓存系统 java nio的多线程扩展 《Concurrency Models》笔记 回头看Spring IOC IntelliJ IDEA使用 Java泛型 vagrant 使用 Go常用的一些库 Python初学 Goroutine 调度模型 虚拟网络 《程序员的自我修养》小结 VPN(Virtual Private Network) Kubernetes存储 访问Kubernetes上的Service Kubernetes副本管理 Kubernetes pod 组件 Go学习 JVM类加载 硬币和扑克牌问题 LRU实现 virtualbox 使用 ThreadLocal小结 docker快速入门

架构

Scheduler如何给Node打分 Scheduler扩展 controller 组件介绍 openkruise cloneset学习 kubernetes crd 及kubebuilder学习 pv与pvc实现 csi学习 client-go学习 kubelet 组件分析 调度实践 Pod是如何被创建出来的? 《软件设计之美》笔记 mecha 架构学习 Kubernetes events学习及应用 CRI 《推荐系统36式》笔记 资源调度泛谈 系统设计原则 grpc学习 元编程 以应用为中心 istio学习 下一代微服务Service Mesh 《实现领域驱动设计》笔记 serverless 泛谈 《架构整洁之道》笔记 处理复杂性 那些年追过的并发 服务器端编程 网络通信协议 《聊聊架构》 书评的笔记 如何学习架构 《反应式设计模式》笔记 项目的演化特点 反应式架构摸索 函数式编程的设计模式 服务化 ddd反模式——CRUD的败笔 研发效能平台 重新看面向对象设计 业务系统设计的一些体会 函数式编程 《左耳听风》笔记 业务程序猿眼中的微服务管理 DDD实践——CQRS 项目隔离——案例研究 《编程的本质》笔记 系统故障排查汇总及教训 平台支持类系统的几个点 代码腾挪的艺术 abtest 系统设计汇总 《从0开始学架构》笔记 初级权限系统设计 领域驱动理念入门 现有上传协议分析 移动网络下的文件上传要注意的几个问题 推送系统的几个基本问题 用户登陆 做配置中心要想好的几个基本问题 不同层面的异步 分层那些事儿 性能问题分析 当我在说模板引擎的时候,我在说什么 用户认证问题 资源的分配与回收——池 消息/任务队列

标签


《数据结构与算法之美》——数据结构笔记

2018年09月19日

简介

推荐在学习的过程中,放慢速度,比如一天只学一章,尽量将demo中的代码实现下。

在技术圈,我们经常喜欢谈论高大上的架构,比如高可用、微服务、服务治理等等。鲜有人关注代码层面的编程能力,愿意沉下心来花几个月时间啃一啃计算机基础知识,认认真真夯实基础。PS:笔者在学习区块链时,区块链的原理很快就搞懂了,但真要说操盘一个项目还是远远不敢想的,因为面对具体的业务场景,不知道如何将取舍映射到技术上,也就始终跟区块链隔着距离。

像《算法导论》这些经典书籍,虽然很全面,但是过于理论,缺乏真实的开发场景,学起来非常枯燥,过不了几天就忘了。PS:计算机专业都会教《数据库原理》,讲了数据库的历史、三大范式、组成、事务等等,但你最直观的工作感受是什么?数据库压力很大怎么办。所以,描述一个知识有两种方式,一种是how、what、when、why等娓娓道来;一种是拿一个问题将所有的知识点串起来。

人生路上,我们会遇到很多的坎儿。跨过去,你就可以成长,跨不过去就是困难和停滞。而在后面很长一段时间里, 你都需要为这个困难买单。

为什么要学习数据结构和算法

参见为什么很多业务程序猿觉得数据结构和算法没用?

学习的重点:

  1. 复杂度分析,作者将这个事儿提到了一个极其重要的高度
  2. 除了知识本身外,更重要的是它的来历、特点和应用场景

算法的复杂度,

  1. 多项式量级,O(1),O(n),O(n^2),O(logn),O(nlogn)
  2. 非多项式量级,只有两个:O(2^n)和O(n!),这类问题称为NP问题。

考虑一下场景:

  1. 向数组第k个位置插入一个元素。将第k个原有的元素挪到数组最后
  2. 从数组中删除一个元素。将该位置标记为已删除,然后在一个时刻统一删除。想想jvm的标记清理算法
  3. 基于数组实现一个队列

为什么很多人的第一个反应是移动元素?原因就是

  1. 很多人没有将数组 作为存储结构,而是逻辑结构。作为逻辑结构的数组,它的定义是:用一组连续的内存空间,来存储一组具有相同类型的数据。作为存储结构,这就是一段儿空间,爱连续不连续。作为逻辑结构,就必须保持它的连续性。
  2. 我们在说问题的时候,没有说业务场景。如果我跟你说jvm垃圾清理,你肯定知道标记清除算法,无需在每一个时刻都保持数组数据的“纯洁性”。
  3. X/Y 问题。将元素插入数组的第K个位置,并没有说要维持数组原来的数据顺序。

时间复杂度代表的是一个增长趋势,但是,我们前面讲过,在大 O 复杂度表示法中,我们会省略低阶、系数和常数,也就是说,O(nlogn) 在没有省略低阶、系数、常数之前可能是 O(knlogn + c),而且 k 和 c有可能还是一个比较大的数。(尤其是k、c远大于n的时候),比如对于小规模数据的排序,O(n2) 的排序算法并不一定比 O(nlogn) 排序算法执行的时间长。对于小数据量的排序,我们选择比较简单、不需要递归的插入排序算法。

常用的数据结构

栈在函数调用中的应用,一次回收一个数据意思不大,但一次回收一个栈帧,即可实现返回值、参数、局部变量的自动分配与回收。cpu 栈寄存器 + 出入栈指令 这类硬件支持,加上栈操作形式的相对固定,使得编译器层面便可以屏蔽这些细节。甚至反过来说,是硬件特性 + 编译器 造就了“方法/函数”这一抽象,而不是方法利用了栈的特性。jvm 虽说堆内存垃圾回收很高端,但这类复杂的事儿就只能语言的虚拟机层 解决了。

常用算法

以新的角度看数据结构

  1. 数组 + 哈希函数 就成了一个散列表。 对于跳表来说,与其说数据结构本来就是那样子,还不如说为了在链表上提高查询速度而衍生的数据结构。对于B+树,换个角度想,我们可以说先有底层那一条叶子链,再有的上层索引结构。
  2. 阐述了为什么查询和排序是基本的算法,以及教程中提到的为什么散列表经常和链表一起使用。

链表:和数组一样,链表也可以是多维的

排序

快排伪代码

// 快速排序,A 是数组,n 表示数组的大小
quick_sort(A, n) { 
	quick_sort_c(A, 0, n-1)
}
// 快速排序递归函数,p,r 为下标	
quick_sort_c(A, p, r) { 
	if p >= rthen return 
	q = partition(A, p, r) // 获取分区点 
	quick_sort_ck_sort_c(A, p, q-1) 
	quick_sort_c(A, q+1, r)
}

如果我们不考虑空间消耗的话,partition() 分区函数可以写得非常简单。我们申请两个临时数组 X 和 Y,遍历 A[p…r],将小于 pivot 的元素都拷贝到临时数组 X,将大于 pivot 的元素都拷贝到临时数组 Y,最后再将数组X 和数组 Y 中数据顺序拷贝到 A[p…r]。PS:这种表述方式让笔者对快排更有感觉了。

随机选择一个元素做“轴元素”,将所有大于轴元素的移到左边,其余移到右边。关键就是:从这一刻开始,小于“轴元素”的那些数就再也没有机会与大于“轴元素”的数进行两两比较了。

数学之美番外篇:快排为什么那样快

排序的本质可以这样来表述:一组未排序的N个数字,它们一共有N!种重排,其中只有一种排列是满足题意的。将排序问题看成和猜数字(给一定范围,猜测提问者写好的数字)一样,是通过问问题来缩小/排除(narrow down)结果的可能性区间,这样一来,就会发现,“最好的问题”就是那些能够均分所有可能性的问题,因为那样的话不管问题的答案如何,都能排除掉k-1/k(k为问题的答案有多少种输出——猜数字里面是2,称球里面是3)种可能性,而不均衡的问题总会有一个或一些答案分支排除掉的可能性要小于k-1/k。于是策略的下界就被拖累了。

哈希/分治和归并

哈希算法的定义和原理非常简单,基本上一句话就可以概括了:将任意长度的二进制值串映射为固定长度的二进制值串。后者就有很多的意涵了:

  1. 可以视为源数据的特征/标识/摘要
  2. 可以是分桶的桶号
  3. 可以是为了掩盖源数据或防篡改(安全加密)

为什么哈希表能做到 O(1) 时间复杂度呢?哈希表基于数组实现,哈希函数直接把查询关键字转换为数组下标,再通过数组的随机访问特性获取数据。

归并排序和快速排序都是分治,但比较好玩的是

  1. 归并排序是简单的缩小数据规模,或者可以认为是根据数据位置将数据集两两划分。
  2. 快速排序是根据数据特征来将数据集两两划分。

假如我们有 1T 的日志文件,这里面记录了用户的搜索关键词,我们想要快速统计出每个关键词被搜索的次数,该怎么做呢?

  1. 首先就是分治,将数据规模缩小到单机可以处理的程度
  2. 分治就涉及到怎么分的问题?肯定是“快排”的分法更好一些,快排(从小到大)保证了左边整体一定比右边小,将快排的“二分”扩散成“多分”, 同一个搜索关键词按哈希(哈希也是数据特征的一种)被分配到同一个机器上

那么分治后的结果如何归并呢?

  1. 不需要归并,比如上例的统计搜索关键词次数
  2. 大文件排序的归并,堆合并

基于数学图论中的各种模型,例如各种二叉树、多叉树、有向图和无向图等等。通常,这些模型表示了顶点和顶点之间的稀疏关系,所以它们常常是基于指针或者对象引用来实现的。

树的划分方式有很多

  1. 一个是结构的限定,比如分几叉
  2. 一个是内容的限定,比如节点大小必须左<中<右

二叉树既可以用链式存储,也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树,其他类型的二叉树用数组存储会比较浪费存储空间。

二叉查找树,二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。进而带来几个特性:中序遍历二叉查找树,可以输出有序的数据序列,时间复杂度是 O(n)

支持重复数据的二叉查找树,如何处理重复数据:

  • 二叉查找树中每一个节点不只存储数据,还挂一个链表或支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上。恍惚之间跟hashmap异曲同工。数据结构保存的是数据和数据的关系,数组只是保存数据关系的方式之一。
  • 将这个要插入的数据放到等值节点的右子树

二叉树的演化逻辑

平衡二叉树:二叉树中任意一个节点的左右子树的高度相差不能大于 1。发明平衡二叉查找树这类数据结构的初衷是,解决普通二叉查找树在频繁的插入、删除等动态更新的情况下,导致树倾斜,出现时间复杂度退化的问题。

AVL 树是一种高度平衡的二叉树,所以查找的效率非常高,但是有利就有弊,AVL 树为了维持这种高度的平衡,会通过旋转操作将高度保持在logN。每次插入、删除都要做调整,就比较复杂、耗时,旋转算法是不同树的具有区分性的特质之一。那对于频繁插入、删除的场合,如何减少调整呢?

  1. 删除的时候只是标记删除,但不真正删除
  2. 一个节点存储更多的数据(更多的分叉),就减少了左旋、右旋的次数。比如mysql innodb的索引树,一个节点的数据大小直接是一个内存块。以2-3树为例从2-3-4树谈到Red-Black Tree(红黑树)

二叉树与高阶(一个节点多于2个叉)树不同在于,高阶树中每个节点元素的个数,为旋转算法提供了决策依据,体现在:

  1. 是否需要分裂合并等操作
  2. 大多数时候,一个插入和删除操作影响节点本身、父亲和兄弟节点,通过父节点元素个数,可以简单的判断是否波及其他节点。
  插入维持平衡 删除维持平衡
二叉树 旋转 旋转
B+Tree 节点的分裂、元素的上浮 向兄弟节点借元素、合并节点、元素的下沉

Left-Leaning Red-Black Trees2-3-4 树在多数编程语言中实现起来相对困难,因为在树上的操作涉及大量的特殊情况。红黑树通过引入颜色的概念,其存在标识一种平衡状态,通过局部的直接判断,即可进行旋转决策。红黑树与2-3-4树的等价性:2-3-4树最终能转换成一棵红黑树,反过来对于红黑树,将红链接相连的节点合并,得到的就是一颗2-3树。

红黑树只是做到了近似平衡,并不是严格的平衡,所以在维护平衡的成本上,要比 AVL 树要低。

如果红黑树过大,内存中放不下时,可以改用 B 树,将部分索引存放在磁盘上。磁盘访问速度要比内存慢很多,但 B 树充分考虑了机械磁盘寻址慢、顺序读写快的特点,通过多分支降低了树高,减少了磁盘读写次数。

二叉树的演化逻辑

要实现一个堆,我们先要知道,堆都支持哪些操作以及如何存储一个堆。这句话体现的思维方式很重要,你设计一个系统,也要分析用户对这个系统有哪些操作系统设计的一些体会

堆的结构通过最小的代价时刻对外保持最大值或最小值。堆是完全二叉树,可用数组存储,一样是数组存储,但不是按序插入/删除,便可以使得第一个元素永远是最大/小值,其它部分依然是无序的(当然堆的上层都比下层大,也不能说是完全无序)。不讲堆排序,单单是建堆的话,完全无序 ==> 最大/小值 + 其它部分无序 ==> 完全有序。这个特性

  1. 你用一部分就是topk
  2. 你全用就是排序
  3. 如果最大值 指的不是元素本身,而是元素附带的优先级的话, 便是一个优先级队列

    • 队列的两个基本操作:push和poll
    • 优先级队列的两个基本操作:push和pull优先级最高的元素
  4. 你用一半就是中位数(你要证明一半数比它小,一半数比它大),即用一个数组的一半元素建个大顶堆,另一半建一个小顶堆(所有元素都比大顶堆大),那么大顶堆堆顶一定是中位数。它的一个变形是 求 99 百分位数据(比如监控系统的99%响应时间)

  数组 链表 存储效率
线性表     链表略差
节点间关系通过位置表示 x叉树 不是“完全的”树时数组较差
二维数组/邻接矩阵 邻接表 稀疏矩阵时数组较差

总的来说,相对数组,链表的方式对计算机缓存命中不友好。

邻接表乍一看还有点像散列表,在基于链表法解决冲突的散列表中,如果链过长,为了提高查找效率,我们可以将链表换成其他更加高效的数据结构,比如平衡二叉查找树、红黑树、跳表等,邻接表同理。数据结构是为算法服务的,所以具体选择哪种存储方法,与期望支持的操作有关系。比如我们假设微博使用图来存储好友关注关系,需要分页返回粉丝列表,邻接表中的链表就可以使用跳表,因为跳表的数据本来就是有序的。如果只有几十万用户,社交关系可以存在内存中,若是上亿用户,则可以把邻接表存储在不同的机器上。

邻接表链表方案的选择 是一个直观的“兵无定式,水无常形”。妹子说喜欢吃“麻婆豆腐”犯不着没有麻婆豆腐就不点菜了,麻的、辣的、豆腐都可以点。我们看到邻接表教科书上用的链表,也不是就定死了不能换其它结构,实际上无所谓是链表、数组、红黑树、跳表。“链表”部分用什么结构“无定式”,“定式”是操作需求。

从这个角度再来看,为什么很多书花很多篇幅将查找和排序?因为很多需求最终都可以归结为查找和排序,然后才是,在极致的查找、排序效率亦或者两者平衡的数据结构之间选择。数据结构就像是设计模式,不是为了用设计模式而用设计模式,而是你知道这应该有一个事件通知的设计,然后才是去应用一个观察者模式。

索引的门道

索引真是个好东西。索引的英文名字叫:index,这个英文单词让我们联想到什么?在实际的编程中,index这个单词真是到处可见。例如:数组的下标就是index。计算机大部分工作都是在Addressing,所以,在计算机中,索引到处存在。小到操作系统虚拟内存到真实内存的映射,就是索引嘛,大到分布式系统、网络,都是这个原理。

小结

学习数据结构最难的不是理解和掌握原理,而是能灵活地将各种场景和问题抽象成对应的数据结构和算法。

知识的学习是一个反复迭代、不断沉淀的过程

该教程的几个很大的意义

  1. 重新组织了数据结构的知识,比如数据结构课本上的查找只说了一个(基于数组的)二分查找。而教程在“查找”章节 讲了 基于链表的查询的跳表。笔者在最开始接触跳表时,则没有将两者联系在一起。联系在一起有什么好处呢?“基于有序链表的查找”便是对跳表信息量的 降维。
  2. 为很多结构找到工程上实际的例子,比如图与微博好友关注业务的关联,再引出不同的业务需求对图实现结构的影响。

从系统设计和业务设计中来看待数据结构的话,我们一般从需求出发,先提炼“用户接口”,已有的结构 一般只能满足简单的信息存储需求, 对于其它需求则需添加辅助存储结构 或者根本上改变存储结构。如果一些“用户接口” 怎么实现都纠结,则通常意味着 信息不够,以笔者现在的经验看,这些信息一般意味着一些中间状态。中间状态(在内存中)或许不需要存储到db,但对于特定接口很有必要。

算法一般作用于特定的数据结构之上,比如二分查找是基于数组的,在链表上就玩不转了。

三篇文章了解 TiDB 技术内幕——说计算SQL 和 KV 结构之间存在巨大的区别,那么如何能够方便高效地进行映射,就成为一个很重要的问题。一个好的映射方案必须有利于对数据操作的需求。那么我们先看一下对数据的操作有哪些需求,分别有哪些特点。

情商比智商更重要,而情商中最重要的,我觉得就是逆商(逆境商数,Adversity Quotient),也就是,当你遇到困难时,你会如何去面对,这将会决定你的人生最终能够走多远。

如果单单是存储数据,可以用线性表。若是存储数据间略微复杂的关系,便要用到树和图。不存复杂关系,但要兼顾对数据各种操作的性能,也要用树等结构。熵的概念

个人微信订阅号