高性能队列-Disruptor

字数统计: 4.3k字   |   阅读时长: 16分

参考 https://tech.meituan.com/2016/11/18/disruptor.html

前言

作为一个有追求的程序猿，时刻保持着对优秀事物的积极学习心态，并发编程就是一个难啃的“硬骨头”，它难在难以控制，大多会使用“锁”来进行管控。但这与性能又南辕北辙。因此，无锁化设计是提升并发性能的关键。本篇文章介绍一个无锁化的高性能并发队列-Disruptor。

1. 背景

Disruptor 是英国外汇交易公司LMAX开发的一个高性能队列，研发的初衷是解决内存队列的延迟问题（在性能测试中发现竟然与I/O操作处于同样的数量级）。基于Disruptor开发的系统单线程能支撑每秒600万订单，2010年在QCon演讲后，获得了业界关注。2011年，企业应用软件专家Martin Fowler专门撰写长文介绍。同年它还获得了Oracle官方的Duke大奖。

目前，包括Apache Storm、Camel、Log4j 2在内的很多知名项目都应用了Disruptor以获取高性能。在美团技术团队它也有不少应用，有的项目架构借鉴了它的设计机制。

展开全文 >>

5-队列_队列在线程池等有限资源池中的应用

字数统计: 4.1k字   |   阅读时长: 15分

Author: haoransun
Wechat: SHR—97

学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

前言

我们知道，CPU 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 CPU 频繁切换，处理性能下降。所以，线程池的大小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。

当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又是怎么实现的呢？

实际上，这些问题并不复杂，其底层的数据结构就是我们今天要学的内容，队列（queue）。

展开全文 >>

4-栈_如何实现浏览器的前进和后退功能

字数统计: 4.5k字   |   阅读时长: 15分

Author: haoransun
Wechat: SHR—97

学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

前言

浏览器的前进、后退功能，我想你肯定很熟悉吧？当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。但是，如果你后退到页面 b 后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。

假设你是 Chrome 浏览器的开发工程师，你会如何实现这个功能呢？

这就要用到我们今天要讲的“栈”这种数据结构。

带着这个问题，我们来学习今天的内容。

展开全文 >>

3-链表下_如何轻松写出正确的链表代码

字数统计: 3.9k字   |   阅读时长: 14分

Author: haoransun
Wechat: SHR—97

学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

前言

想要写好链表代码并不是容易的事儿，尤其是那些复杂的链表操作，比如链表反转、有序链表合并等，写的时候非常容易出错。从我上百场面试的经验来看，能把“链表反转”这几行代码写对的人不足 10%。

为什么链表代码这么难写？究竟怎样才能比较轻松地写出正确的链表代码呢？

只要愿意投入时间，我觉得大多数人都是可以学会的。比如说，如果你真的能花上一个周末或者一整天的时间，就去写链表反转这一个代码，多写几遍，一直练到能毫不费力地写出 Bug free 的代码。这个坎还会很难跨吗？

总结了几个写链表代码技巧。如果你能熟练掌握这几个技巧，加上你的主动和坚持，轻松拿下链表代码完全没有问题。

展开全文 >>

2-链表上_如何实现LRU缓存淘汰算法

字数统计: 5.6k字   |   阅读时长: 19分

Author: haoransun
Wechat: SHR—97

学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

前言

今天我们来聊聊“链表（Linked list）”这个数据结构。学习链表有什么用呢？为了回答这个问题，我们先来讨论一个经典的链表应用场景，那就是 LRU 缓存淘汰算法。

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。

常见的策略有三种：

  • 先进先出策略 FIFO（First In，First Out）

  • 最少使用策略 LFU（Least Frequently Used）

  • 最近最少使用策略 LRU（Least Recently Used）

展开全文 >>

1-数组_为什么很多编程语言中数组都从0开始编号

字数统计: 4.7k字   |   阅读时长: 16分

Author: haoransun
Wechat: SHR—97

学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

前言

提到数组，我想你肯定不陌生，甚至还会自信地说，它很简单啊。

是的，在每一种编程语言中，基本都会有数组这种数据类型。不过，它不仅仅是一种编程语言中的数据类型，还是一种最基础的数据结构。尽管数组看起来非常基础、简单，但是我估计很多人都并没有理解这个基础数据结构的精髓。

在大部分编程语言中，数组都是从 0 开始编号的，但你是否下意识地想过，为什么数组要从 0 开始编号，而不是从 1 开始呢？

从 1 开始不是更符合人类的思维习惯吗？

你可以带着这个问题来学习接下来的内容。

展开全文 >>

复杂度分析-下部

字数统计: 3.6k字   |   阅读时长: 13分

Author: haoransun
Wechat: SHR—97
学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

1 浅析最好、最坏、平均、均摊时间复杂度

     最好情况时间法则度(best case time complexity)
     最坏情况时间复杂度(worst case time complexity)
     平均情况时间复杂度(average case time complexity)
     均摊时间复杂度(amortized time complexity)

展开全文 >>

复杂度分析-上部

字数统计: 5k字   |   阅读时长: 19分

Author: haoransun
Wechat: SHR—97
学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

     众所周知，数据结构与算法本身解决的是“快”和“省”的问题，即如何让代码运行得更快，如何让代码更省存储空间。所以，执行效率是算法一个非常重要的考量指标。

1 为什么需要复杂度分析？

     我将代码跑一遍，通过统计、监控，就能得到算法执行时间个占用的内存大小。为什么要使用空间、时间复杂度分析呢？难道比我实实在在跑一遍得到的数据还要准确吗？

     上述评估算法执行效率的方法是正确的。大部分人称它为事后统计法，但它有非常大的局限性。

展开全文 >>

数据结构与算法概览

字数统计: 573字   |   阅读时长: 2分

Author: haoransun
Wechat: SHR—97
学习来源：极客时间-算法之美，本人购买课程后依据图文讲解汇总成个人见解。

1 定义

   广义上：
     数据结构：一组数据的存储结构。
     算法：操作数据的一组方法。
   狭义上：
     某些著名的数据结构与算法,如队列、栈、堆、二分查找、动态规划等等。

2 二者关系

   数据结构与算法相辅相成。数据结构是为算法服务的，算法要作用在特定的数据结构之上。因此，孤立而单独的讲解两者毫无意义。
   比如，因为数组具有随机访问的特点，常用的二分查找算法需要用数组来存储数据。但是我们选择链表这种数据结构，二分查找就无法工作了，因为链表不支持随机访问。
   数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构是没有用的。

展开全文 >>

本站总访问量71567次 | 本站访客数64291人