XIAOSUO 记录个人学习的足迹

摘要：Go语言GC算法主要是基于Mark and Sweep (标记清除)算法，在此基础上进行改进和优化。 1). Mark and Sweep(标记清除)算法主要是以下2个步骤： 标记(Mark): 找出所有不可达对象，然后做上标记 清除(Sweep): 回收标记好的对象 标记清除具体步骤如下： a). 开始标记，程序暂停 b). 找到所有可达对象，并做上标记 c). 标记完成后开始清除未标记的对象 d). 清除完成 2). 标记清除算法存在以下几个问题 a). STW (stop the world) 标记对象的时候程序需要暂停，导致程序出现卡顿 (最主要的问题) b). 标记需要扫描整个堆 c). 清除对象会产生堆碎片 STW指的是runtime把所有的协程都冻结了，意味着用户逻辑是暂停的，这样所有的对象都不会被修改，这个时候去扫描是绝对安全的。 3). Tri-color Marking 为了解决标记清除算法带来的问题，Go在标记清除算法基础上提出来Tri-color Marking(三色标记法)算法来优化GC过程，大体流程如下： a). 最开始所有的对象都是白色的 b). GC开始，扫描所有可达的对象，标记为灰色 c). 从灰色对象中找到其引用对象并标记为灰色，自己标记为黑色 d). 监控对象修改，循环上一步骤，直到没有任何灰色对象 e). GC回收白色对象 f). 最后把所有黑色对象变成白色 4). 三色标记法通过2点来优化STW问题 a). 标记操作和用户逻辑并行: 用户逻辑经常会生成或改变对象引用，那如何保证标记和用户逻辑并行呢？Go为了解决这个问题引入了写屏障机制，在GC的过程中会监控对象的内存修改，并对对象进行重新标记，这个时候用户逻辑也可以执行 (实际上是很短暂的STW，然后对对象重新标记)，所以标记操作可以做到一定程度和用户逻辑并行。 b). 清除操作和用户逻辑并行: 三色标记法中最后只剩下的黑白两种对象，黑色对象是程序恢复后接着使用的对象，如果不碰触黑色对象，只清除白色的对象，肯定不会影响程序逻辑，所以清除白色对象和用户逻辑可以并行。 通过允许用户逻辑在标记和清除操作上做到并行处理来缩短STW的时间，提升整体GC的性能。 阅读全文

摘要：什么是哈希算法 定义 将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。 如何设计一个优秀的哈希算法 单向哈希： 从哈希值不能反向推导出哈希值（所以哈希算法也叫单向哈希算法）。 篡改无效： 对输入敏感，哪怕原始数据只修改一个Bit，最后得到的哈希值也大不相同。 散列冲突： 散列冲突的概率要很小，对于不同的原始数据，哈希值相同的概率非常小。 执行效率： 哈希算法的执行效率要尽量高效，针对较长的文本，也能快速计算哈希值。 哈希算法的常见应用 安全加密 常用于加密的哈希算法： MD5：MD5 Message-Digest Algorithm，MD5消息摘要算法 SHA：Secure Hash Algorithm，安全散列算法 DES：Data Encryption Standard，数据加密标准 AES：Advanced Encryption Standard，高级加密标准 对用于加密的哈希算法，有两点格外重要，第一点是很难根据哈希值反向推导出原始数据，第二点是散列冲突的概率要小。 在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 唯一标识 通过哈希算法计算出数据的唯一标识，从而用于高效检索数据。 数据校验 利用哈希算法对输入数据敏感的特点，可以对数据取哈希值，从而高效校验数据是否被篡改过。 散列函数 散列函数中用到的哈希算法更加关注散列后的值能不能平均分布，以及散列函数的执行快慢。 负载均衡 需求 如何实现一个会话粘滞（session sticky）的负载均衡算法？也就是说，在一次会话中的所有请求都路由到同一个服务器上。 解决方案 通过哈希算法对客户端IP或会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是应该被路由到的服务器编号。这样，就可以把同一个IP过来的请求都路由到同一个后端服务器上。 数据分片 如何统计“搜索关键词”出现的次数？ ①需求描述 假如我们有1T的日志文件，这里面记录了用户的搜索关键词，我们想要快速统计出每个关键词被搜索的次数，该怎么做呢？ ②问题分析 这个问题有两个难点，第一个是搜索的日子很大，没办法放到一台机器的内存中。第二个是只用一台机器来处理这么巨大的数据，处理时间会很长。 ③解决方案 先对数据进行分…… 阅读全文

摘要：什么是跳表 为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。 跳表的时间复杂度 计算跳表的高度 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2^k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。 计算跳表的时间复杂度 假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢？假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。 跳表的空间复杂度及如何优化 计算索引的节点总数 如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的空间复杂度为O(n)。 如何优化时间复杂度 如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。 高效的动态插入和删除 跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是O(logn)，所以，跳表的插入和删除操作的是时间复杂度也是O…… 阅读全文

摘要：什么是二分查找 二分查找针对的是一个有序的数据集合，每次通过跟区间中间的元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间缩小为0。 时间复杂度分析 时间复杂度 假设数据大小是n，每次查找后数据都会缩小为原来的一半，最坏的情况下，直到查找区间被缩小为空，才停止。所以，每次查找的数据大小是：n，n/2，n/4，…，n/(2^k)，…，这是一个等比数列。当n/(2^k)=1时，k的值就是总共缩小的次数，也是查找的总次数。而每次缩小操作只涉及两个数据的大小比较，所以，经过k次区间缩小操作，时间复杂度就是O(k)。通过n/(2^k)=1，可求得k=log2n，所以时间复杂度是O(logn)。 认识O(logn) 这是一种极其高效的时间复杂度，有时甚至比O(1)的算法还要高效。为什么？ 因为logn是一个非常“恐怖“的数量级，即便n非常大，对应的logn也很小。比如n等于2的32次方，也就是42亿，而logn才32。 由此可见，O(logn)有时就是比O(1000)，O(10000)快很多。 如何实现二分查找 循环实现 func binarySearch1([]int a, val int) int { start := 0 end := len(a) - 1 for start = end { // 不要使用（start + end）/ 2 防止超出边界 mid := start + (end - start) / 2 if a[mid] val { end = mid - 1 } else if a[mid] val { start = mid + 1 } else { return mid } } return -1 } 注意事项： 循环退出条件是：start=end，而不是startend。 mid的取值，使用mid=start + (end - start) / 2，而不用mid=(start + end)/2，因为如果start和end比较大的话，求和可能会发生int类型的值超出最大范围。为了把性能优化到极致，可以将除以2转换成位运算，即start + ((end - start) 1)，因为相比除法运算来说，计算机处理位运算要快得多。 start和end的更新：sta…… 阅读全文

摘要：一、如何选择合适的排序算法？ 排序算法一览表 时间复杂度 是稳定排序？ 是原地排序？ 冒泡排序 O(n^2) 是 是 插入排序 O(n^2) 是 是 选择排序 O(n^2) 否 是 快速排序 O(nlogn) 否 是 归并排序 O(nlogn) 是 否 桶排序 O(n) 是 否 计数排序 O(n+k)，k是数据范围 是 否 基数排序 O(dn)，d是纬度 是 否 为什选择快速排序？ 线性排序时间复杂度很低但使用场景特殊，如果要写一个通用排序函数，不能选择线性排序。 为了兼顾任意规模数据的排序，一般会首选时间复杂度为O(nlogn)的排序算法来实现排序函数。 同为O(nlogn)的快排和归并排序相比，归并排序不是原地排序算法，所以最优的选择是快排。 二、如何优化快速排序？ 导致快排时间复杂度降为O(n)的原因是分区点选择不合理，最理想的分区点是：被分区点分开的两个分区中，数据的数量差不多。如何优化分区点的选择？有2种常用方法，如下： 三数取中法 从区间的首、中、尾分别取一个数，然后比较大小，取中间值作为分区点。 如果要排序的数组比较大，那“三数取中”可能就不够用了，可能要“5数取中”或者“10数取中”。 随机法：每次从要排序的区间中，随机选择一个元素作为分区点。 警惕快排的递归发生堆栈溢出，有2中解决方法，如下： 限制递归深度，一旦递归超过了设置的阈值就停止递归。 在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈过程，这样就没有系统栈大小的限制。 三、通用排序函数实现技巧 数据量不大时，可以采取用时间换空间的思路 数据量大时，优化快排分区点的选择 防止堆栈溢出，可以选择在堆上手动模拟调用栈解决 在排序区间中，当元素个数小于某个常数是，可以考虑使用O(n^2)级别的插入排序 用哨兵简化代码，每次排序都减少一次判断，尽可能把性能优化到极致 四、Go语言排序函数的实现 golang标准库中的Sort用的是快排+希尔排序+插排，数据量大于12时用快排，小于等于12时用6作为gap做一次希尔排序，然后走一遍普通的插排（插排对有序度高的序列效率高）。其中快排pivot的选择做了很多工作，是基于首中尾中值的很复杂的变种 func quickSort(data Interface, a, b, maxDepth int) { for b-a 12 …… 阅读全文

摘要：一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。 对排序数据的要求很苛刻，重点掌握此3种排序算法的适用场景。 二、桶排序（Bucket sort） 算法原理： 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。 使用条件 要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。 数据在各个桶之间分布是均匀的。 代码实现 func tongSort(values []int) { t := make([]int, 10) for _, val := range values { t[val]++ } res := make([]int, 0, len(values)) for index, val := range t { //循环把排序元素添加到新的数组中 for ; val 0; val-- { res = append(res, index) } } fmt.Println(res) } 适用场景 桶排序比较适合用在外部排序中。 外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。 应用案例 需求描述： 有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序 但内存有限，仅几百MB 解决思路： 扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。 第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。 每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。 将100个小文件依次放入内存并用快排排序。 所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。 注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。 三、计数排序（Counting sort） 算法原理 计数其实就是桶排序的一种特殊情况。 当要排序的n个数据所处范围并不大时，比如最大值为k，则分成k个桶 …… 阅读全文

摘要：一、分治思想 分治思想：分治，顾明思意，就是分而治之，将一个大问题分解成小的子问题来解决，小的子问题解决了，大问题也就解决了。 分治与递归的区别：分治算法一般都用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。 二、归并排序 算法原理 先把数组从中间分成前后两部分，然后对前后两部分分别进行排序，再将排序好的两部分合并到一起，这样整个数组就有序了。这就是归并排序的核心思想。如何用递归实现归并排序呢？写递归代码的技巧就是分写得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。递推公式怎么写？如下 递推公式：merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r)) 终止条件：p = r 不用再继续分解。 代码实现 func mergeSort(arr []int, start, end int) { if start = end { return } mid:=(start + end) / 2 mergeSort(arr, start, mid) mergeSort(arr, mid+1, end) merge(arr, start, mid, end) } func merge(arr []int, start, mid, end int) { var tmparr = []int{} var s1, s2 = start, mid+1 for s1= mid s2= end{ if arr[s1] arr[s2] { tmparr = append(tmparr, arr[s2]) s2++ } else { tmparr = append(tmparr, arr[s1]) s1++ } } if s1=mid { tmparr = append(tmparr, arr[s1: mid+1]...) } if s2=end { tmparr = append(tmparr,…… 阅读全文

摘要：一、排序方法与复杂度归类 几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。 复杂度归类 冒泡排序、插入排序、选择排序 O(n^2) 快速排序、归并排序 O(nlogn) 计数排序、基数排序、桶排序 O(n) 二、算法的执行效率 算法的执行效率 最好、最坏、平均情况时间复杂度。 时间复杂度的系数、常数和低阶。 比较次数，交换（或移动）次数。 排序算法的稳定性 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 稳定性重要性：可针对对象的多种属性进行有优先级的排序。 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。 排序算法的内存损耗 原地排序算法：特指空间复杂度是O(1)的排序算法。 三、冒泡排序 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。 稳定性：冒泡排序是稳定的排序算法。 空间复杂度：冒泡排序是原地排序算法。 时间复杂度： 最好情况（满有序度）：O(n)。 最坏情况（满逆序度）：O(n^2)。 平均情况： “有序度”和“逆序度”：对于一个不完全有序的数组，如4，5，6，3，2，1，有序元素对为3个（4，5），（4，6），（5，6），有序度为3，逆序度为12；对于一个完全有序的数组，如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15，称作满有序度；逆序度=满有序度-有序度；冒泡排序、插入排序交换（或移动）次数=逆序度。 最好情况下初始有序度为n*(n-1)/2，最坏情况下初始有序度为0，则平均初始有序度为n*(n-1)/4，即交换次数为n*(n-1)/4，因交换次数比较次数最坏情况时间复杂度，所以平均时间复杂度为O(n^2)。 func BubbleSort(values []int) { for i := 0; i len(values)-1; i++ { for j := i+1; j len(values); j++ { if v…… 阅读全文

摘要：一、什么是递归？ 递归是一种非常高效、简洁的编码技巧，一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。 基本上，所有的递归问题都可以用递推公式来表示，比如 f(n) = f(n-1) + 1; f(n) = f(n-1) + f(n-2); f(n)=n*f(n-1); 二、为什么使用递归？递归的优缺点？ 优点：代码的表达力很强，写起来简洁。 缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。 三、递归需要满足的三个条件 问题的解可以分解为几个子问题的解。何为子问题？就是数据规模更小的问题。 问题与子问题，除了数据规模不同，求解思路完全一样 存在递归终止条件 四、如何实现递归？ 递归代码编写 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。 递归代码理解 对于递归代码，若试图想清楚整个递和归的过程，实际上是进入了一个思维误区。 那该如何理解递归代码呢？如果一个问题A可以分解为若干个子问题B、C、D，你可以假设子问题B、C、D已经解决。而且，你只需要思考问题A与子问题B、C、D两层之间的关系即可，不需要一层层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。 因此，理解递归代码，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。 五、递归常见问题及解决方案 警惕堆栈溢出：可以声明一个全局变量来控制递归的深度，从而避免堆栈溢出。 警惕重复计算：通过某种数据结构来保存已经求解过的值，从而避免重复计算。 六、如何将递归改写为非递归代码 递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在开发过程中，我们要根据实际情况来选择是否需要用递归的方式来实现。 比如斐波拉契数列的实现 递归实现 func f(int n) int { if n == 1 { return 1 } if n == 2 { ret…… 阅读全文

摘要：一、什么是队列？ 1.先进者先出，这就是典型的“队列”结构。 2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。 3.所以，和栈一样，队列也是一种操作受限的线性表。 二、如何实现队列 1. 数组实现 type Queue struct { items []interface{} length int //数组大小 head int //表示队头下标 tail int //表示队尾下标 } func CreateStack(cap int) *Queue { if cap == 0 { panic(不能创建容量为0的队列！) } return Queue{ items: [capacity]interface, length: capacity, head:0, tail:0 } } func (this *Queue) Enqueue(item interface{})(err error){ if this.tail == this.length { return errors.New(queue full) } this.items[this.rear] = item this.tail++ return } func (this *Queue) Dequeue() (interface{},err error){ if this.head == this.tail { return _,errors.New(queue empty) } item = this.items[this.head] this.head++ return item,err } 比起栈的数组实现，队列的数组实现稍微有点儿复杂。 对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。 如下图：当 a、b、c、d 依次入队之后，队列中的 head 指针指向下标为 0 的位置，tail 指针指向下标为 4 …… 阅读全文