在项目中,使用缓存是常见的提升性能的一个方法。为防止内存被无限制的消耗,使用内存缓存必须注意到一个淘汰策略,本文就介绍其中的一种算法:LRU。
什么时LRU?
LRU (Least recently used:最近最少使用)算法在缓存写满的时候,会根据所有数据的访问记录,淘汰掉未来被访问几率最低的数据。也就是说该算法认为,最近被访问过的数据,在将来被访问的几率最大。
简单的理解,就是当缓存需要淘汰时,先淘汰最早写入且最近没有被查询过的缓存元素。
more >>Golang,PHP工程师
在项目中,使用缓存是常见的提升性能的一个方法。为防止内存被无限制的消耗,使用内存缓存必须注意到一个淘汰策略,本文就介绍其中的一种算法:LRU。
LRU (Least recently used:最近最少使用)算法在缓存写满的时候,会根据所有数据的访问记录,淘汰掉未来被访问几率最低的数据。也就是说该算法认为,最近被访问过的数据,在将来被访问的几率最大。
简单的理解,就是当缓存需要淘汰时,先淘汰最早写入且最近没有被查询过的缓存元素。
more >>前面介绍了BTree算法的实现,实际在数据库索引里用的是B+Tree。
B+树是B树的一个变种算法,两者都是平衡多路查找树。
与BTree的区别
1 | 1.非叶子节点只存储键值信息,数据记录都存放在叶子节点中。 |
优点
1 | 1.IO效率更高:内部结点只有关键字,没有数据,一个结点可以容纳更多的关键字。查询时一次性读入内存中的关键字也就越多 |
插入数据
1 | 1.插入数据时首先定位到数据所在的叶子节点,然后将数据插入到该节点,插入数据后的数组依然成正序排列。 |
查找数据
1 | 1.根据关键字,找到对应的叶子节点。 |
删除数据
1 | 1.当删除某节点中最大或者最小的关键字,就会涉及到更改其双亲节点一直到根节点中所有索引值的更改。 |
本文将介绍btree的原理与golang的实现。
B树是一种平衡的多路查找树。树,可广泛用于磁盘访问。 M阶树顺序的B树最多可以有m-1个键和M个子树。 使用B树的主要原因之一是它能够在单个节点中存储大量键,并且通过保持树的高度相对较小来存储大键值。
概念
1 | 根节点:最顶层节点 |
特点
1 | 1.每个叶结点具有相同的深度,也就是树的高度。 |
Btree主要用于提高访问数据的效率,比如数据库的索引文件。
插入
1 | package btree |
删除
查找
本文将介绍Bitmap的使用场景与算法实现。
所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。比如将第4位字节设为1,就代表某个集合已存在ID为4的记录。
由于存储数据的是非常小的字节,所以bitmap能节省超大空间,可以用来处理大量数据的排序、查询以及去重。
1 | package bit |
本文介绍在golang项目中,基于tcp协议的面向网络编程。
一般来说,基于C/S架构实现的项目,都是基于长链接来实现的。协议有http、tcp、udp,重点介绍tcp。
服务端
1 | 1.监听端口 |
客户端
1 | 1.建立与服务端的链接 |
时序图
在C/S模型下,需要服务端主动推送大量数据时,通过定时或按数量到达一定条件时,将数据批量取出,实现合并推送,减少推送次数。
设计一个队列,将元素不停的往队列里添加,直到满足某个条件后,可以将多个元素一并取出。
接口说明
1 | // Batcher 批处理接口 |
结构图
算法思想主要有分治算法、回溯法、贪心算法、动态规划法等,本文介绍分治算法。
将一个复杂的问题分成两个或更多个相同或相似的子问题,求得子问题的解,再合并就得到原问题的解。其核心思想是“分而治之”。
算法描述
1 | 1.选择数组的第一个数作为基数,将后面的数与之比较,较小的放右边,较大的放左边,分成2个数组。 |
快速排序的时间复杂度是 O(nlogn)
。
实现
1 | // QuickSort 快速排序,left为数组的第一个下标,right为数组的最后一个下标 |
使用
1 | func main() { |
算法描述
1 | 1.分:将n个元素的序列分成n/2个子序列,每个子序列含两个元素。 |
实现
1 | // 自顶向下归并排序,排序范围在[left,right)的数组 |
该如何在实际环境中使用到这种分治思想呢?
本文介绍在微服务架构中,常用于服务与服务之间的异步通信组件kafka。
Kafka是由Apache软件基金会开发的一个开源流处理平台,是一种高吞吐量的分布式发布订阅消息系统。
首先需要安装zookeeper
1 | docker run -d --name zookeeper -p 2181:2181 -v /etc/localtime:/etc/localtime wurstmeister/zookeeper |
然后启动kafka容器
1 | docker run -d --name kafka -p 9092:9092 \ |
安装
1 | go get github.com/segmentio/kafka-go |
封装客户端
1 |
|
本文将介绍字典树的相关知识与Golang的实现方式。
在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。
Trie的典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计、敏感词检测、文本提示等。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
如果插入数据为sex
,son
,sleep
, some
,则树结构如下所示:
1 | s |
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia-plus根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true