1、54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 Disruptor你是否听说过呢？它是一种内存消息队列。从功能上讲，它其实有点儿类似Kafka。不过，和Kafka不同的是，Disruptor是线程之间用于消息传递的队列。 它在Apache Storm、Camel、Log4j 2
2、等很多知名项目中都有广泛应用。 之所以如此受青睐，主要还是因为它的性能表现非常优秀。它比Java中另外一个非常常用的内存消息队列ArrayBlockingQueue（ABS）的性能，要高一个数量级， 可以算得上是最快的内存消息队列了。它还因此获得过Oracle官方的Duke大奖。 如此高性能的内存消息队列，在设计和实现上，必然有它独到的地方。今天，我们就来一块儿看下，Disruptor是如何做到如此高性能的？其底层依赖了哪些数据 结构和算法？ 基于循环队列的“生产者-消费者模型” 什么是内存消息队列？对很多业务工程师或者前端工程师来说，可能会比较陌生。不过，如果我说“生产者-消费者模型”，估计
3、大部分人都知道。在这个模型 中，“生产者”生产数据，并且将数据放到一个中心存储容器中。之后，“消费者”从中心存储容器中，取出数据消费。 这个模型非常简单、好理解，那你有没有思考过，这里面存储数据的中心存储容器，是用什么样的数据结构来实现的呢？ 实际上，实现中心存储容器最常用的一种数据结构，就是我们在第9节讲的队列。队列支持数据的先进先出。正是这个特性，使得数据被消费的顺序性可以得到保 证，也就是说，早被生产的数据就会早被消费。 我们在第9节讲过，队列有两种实现思路。一种是基于链表实现的链式队列，另一种是基于数组实现的顺序队列。不同的需求背景下，我们会选择不同的实现方 式。 如果我们要实现一个无
4、界队列，也就是说，队列的大小事先不确定，理论上可以支持无限大。这种情况下，我们适合选用链表来实现队列。因为链表支持快速地 动态扩容。如果我们要实现一个有界队列，也就是说，队列的大小事先确定，当队列中数据满了之后，生产者就需要等待。直到消费者消费了数据，队列有空闲 位置的时候，生产者才能将数据放入。 实际上，相较于无界队列，有界队列的应用场景更加广泛。毕竟，我们的机器内存是有限的。而无界队列占用的内存数量是不可控的。对于实际的软件开发来 说，这种不可控的因素，就会有潜在的风险。在某些极端情况下，无界队列就有可能因为内存持续增长，而导致OOM（Out of Memory）错误。 在第9节中，我们还
5、讲过一种特殊的顺序队列，循环队列。我们讲过，非循环的顺序队列在添加、删除数据的工程中，会涉及数据的搬移操作，导致性能变差。而 循环队列正好可以解决这个数据搬移的问题，所以，性能更加好。所以，大部分用到顺序队列的场景中，我们都选择用顺序队列中的循环队列。 实际上，循环队列这种数据结构，就是我们今天要讲的内存消息队列的雏形。我借助循环队列，实现了一个最简单的“生产者-消费者模型”。对应的代码我贴到这 里，你可以看看。 为了方便你理解，对于生产者和消费者之间操作的同步，我并没有用到线程相关的操作。而是采用了“当队列满了之后，生产者就轮训等待；当队列空了之后，消 费者就轮训等待”这样的措施。 publ
6、ic class Queue private Long data; private int size = 0, head = 0, tail = 0; public Queue(int size) this.data = new Longsize; 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 this.size = size; public boo
7、lean add(Long element) if (tail + 1) % size = head) return false; datatail = element; tail = (tail + 1) % size; return true; public Long poll() if (head = tail) return null; long ret = datahead; head = (head + 1) % size; return ret; public class Producer private Queue queue; public Producer(Queue qu
8、eue) this.queue = queue; public void produce(Long data) throws InterruptedException while (!queue.add(data) Thread.sleep(100); public class Consumer private Queue queue; public Consumer(Queue queue) this.queue = queue; public void comsume() throws InterruptedException while (true) Long data = queue.
9、poll(); if (data = null) Thread.sleep(100); else / TODO:.消费数据的业务逻辑. 基于加锁的并发“生产者-消费者模型” 实际上，刚刚的“生产者-消费者模型”实现代码，是不完善的。为什么这么说呢？ 如果我们只有一个生产者往队列中写数据，一个消费者从队列中读取数据，那上面的代码是没有问题的。但是，如果有多个生产者在并发地往队列中写入数据， 或者多个消费者并发地从队列中消费数据，那上面的代码就不能正确工作了。我来给你讲讲为什么。 在多个生产者或者多个消费者并发操作队列的情况下，刚刚的代码主要会有下面两个问题： 多个生产者写入的数据可能会互相覆盖；
10、 多个消费者可能会读取重复的数据。 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 因为第一个问题和第二个问题产生的原理是类似的。所以，我着重讲解第一个问题是如何产生的以及该如何解决。对于第二个问题，你可以类比我对第一个问题 的解决思路自己来想一想。 两个线程同时往队列中添加数据，也就相当于两个线程同时执行类Queue中的add()函数。我们假设队列的
11、大小size是10，当前的tail指向下标7，head指向下标3，也 就是说，队列中还有空闲空间。这个时候，线程1调用add()函数，往队列中添加一个值为12的数据；线程2调用add()函数，往队列中添加一个值为15的数据。在极 端情况下，本来是往队列中添加了两个数据（12和15），最终可能只有一个数据添加成功，另一个数据会被覆盖。这是为什么呢？ 为了方便你查看队列Queue中的add()函数，我把它从上面的代码中摘录出来，贴在这里。 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据
12、结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 public boolean add(Long element) if (tail + 1) % size = head) return false; datatail = element; tail = (tail + 1) % size; return true; 从这段代码中，我们可以看到，第3行给datatail赋值，然后第4行才给tail的值加一。赋值和tail加一两个操作，并非原子操作。这就会导致这样的情况发生：当线 程1和线程2同时执行add()函
13、数的时候，线程1先执行完了第3行语句，将data7（tail等于7）的值设置为12。在线程1还未执行到第4行语句之前，也就是还未 将tail加一之前，线程2执行了第3行语句，又将data7的值设置为15，也就是说，那线程2插入的数据覆盖了线程1插入的数据。原本应该插入两个数据（12和15） 的，现在只插入了一个数据（15）。 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/
14、31 9:33:46 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 那如何解决这种线程并发往队列中添加数据时，导致的数据覆盖、运行不正确问题呢？ 最简单的处理方法就是给这段代码加锁，同一时间只允许一个线程执行add()函数。这就相当于将这段代码的执行，由并行改成了串行，也就不存在我们刚刚说的 问题了。 不过，天下没有免费的午餐，加锁将并行改成串行，必
15、然导致多个生产者同时生产数据的时候，执行效率的下降。当然，我们可以继续优化代码， 用CAS（compare and swap，比较并交换）操作等减少加锁的粒度，但是，这不是我们这节的重点。我们直接看Disruptor的处理方法。 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 基于无锁的并发“生产者-消费者模型” 尽管Disruptor的源码读起来很复
16、杂，但是基本思想其实非常简单。实际上，它是换了一种队列和“生产者-消费者模型”的实现思路。 之前的实现思路中，队列只支持两个操作，添加数据和读取并移除数据，分别对应代码中的add()函数和poll()函数，而Disruptor采用了另一种实现思路。 对于生产者来说，它往队列中添加数据之前，先申请可用空闲存储单元，并且是批量地申请连续的n个（n1）存储单元。当申请到这组连续的存储单元之后，后 续往队列中添加元素，就可以不用加锁了，因为这组存储单元是这个线程独享的。不过，从刚刚的描述中，我们可以看出，申请存储单元的过程是需要加锁的。 对于消费者来说，处理的过程跟生产者是类似的。它先去申请一批连续可
17、读的存储单元（这个申请的过程也是需要加锁的），当申请到这批存储单元之后，后续 的读取操作就可以不用加锁了。 不过，还有一个需要特别注意的地方，那就是，如果生产者A申请到了一组连续的存储单元，假设是下标为3到6的存储单元，生产者B紧跟着申请到了下标 是7到9的存储单元，那在3到6没有完全写入数据之前，7到9的数据是无法读取的。这个也是Disruptor实现思路的一个弊端。 文字描述不好理解，我画了一个图，给你展示一下这个操作过程。 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与
18、算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 实际上，Disruptor采用的是RingBuffer和AvailableBuffer这两个结构，来实现我刚刚讲的功能。不过，因为我们主要聚焦在数据结构和算法上，所以我对这两种结 构做了简化，但是基本思想是一致的。如果你对Disruptor感兴趣，可以去阅读一下它的源码。 总结引申 今天，我讲了如何实现一个高性能的并发队列。这里的“并发”两个字，实际上就是多线程安全的意思。 常见的内存队列往往采用循环队列来实现。这种实现方法，对于只有一个生产者和一个消费者的场景，已经
19、足够了。但是，当存在多个生产者或者多个消费者的 时候，单纯的循环队列的实现方式，就无法正确工作了。 这主要是因为，多个生产者在同时往队列中写入数据的时候，在某些情况下，会存在数据覆盖的问题。而多个消费者同时消费数据，在某些情况下，会存在消费 重复数据的问题。 针对这个问题，最简单、暴力的解决方法就是，对写入和读取过程加锁。这种处理方法，相当于将原来可以并行执行的操作，强制串行执行，相应地就会导致操 作性能的下降。 为了在保证逻辑正确的前提下，尽可能地提高队列在并发情况下的性能，Disruptor采用了“两阶段写入”的方法。在写入数据之前，先加锁申请批量的空闲存储单 元，之后往队列中写入数据的操
20、作就不需要加锁了，写入的性能因此就提高了。Disruptor对消费过程的改造，跟对生产过程的改造是类似的。它先加锁申请批量的 可读取的存储单元，之后从队列中读取数据的操作也就不需要加锁了，读取的性能因此也就提高了。 你可能会觉得这个优化思路非常简单。实际上，不管架构设计还是产品设计，往往越简单的设计思路，越能更好地解决问题。正所谓“大道至简”，就是这个意 思。 课后思考 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disrupto
21、r背后的数据结构和算法.html2019/1/31 9:33:46 为了提高存储性能，我们往往通过分库分表的方式设计数据库表。假设我们有8张表用来存储用户信息。这个时候，每张用户表中的ID字段就不能通过自增的方式 来产生了。因为这样的话，就会导致不同表之间的用户ID值重复。 为了解决这个问题，我们需要实现一个ID生成器，可以为所有的用户表生成唯一的ID号。那现在问题是，如何设计一个高性能、支持并发的、能够生成全局唯 一ID的ID生成器呢？ 欢迎留言和我分享，也欢迎点击“请朋友读”，把今天的内容分享给你的好友，和他一起讨论、学习。 54|算法实战（三）：剖析高性能队列Disruptor背后的数据
22、结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 精选留言： Smallfly 2019-01-30 10:29:31 没有读过 Disruptor 的源码，从老师的文章理解，一个线程申请了一组存储空间，如果这组空间还没有被完全填满之前，另一个线程又进来，在这组空间之后 申请空间并添加数据，之后第一组空间又继续填充数据，那在消费时如何保证队列是按照添加顺序读取的呢？ 即使控制读取时前面不能有空闲空间，是为了保证能按内
23、存空间顺序消费，但是如果生产的时候没有保证顺序存储，似乎就不满足队列的条件了。 1赞 想当上帝的司机 2019-01-30 08:44:47 为什么3到6没有完全写入前，7到9无法读取，不是两个写入操作吗 1赞 Victor 2019-01-30 15:10:46 课后问题：设计高性能、支持并发的全局唯一ID生成器 使用Redis生成全局唯一ID 1、 redis Incr为原子操作，支持并发 2、redis基于内存，性能较高 Yakmoz 2019-01-30 14:11:37 像TDDL采用的也是类似的思想，由一个sequeue维护当前已用的最大ID，然后也是取一个ID区间自己缓存起来，用
24、的是乐观锁控制并发。另外比起zookeeper 来说etcd更适合生成全局唯一的ID，因为ZK只能保证最终一致性，etcd是强一致性，在性能上也要比ZK更好 belongcai蔡炳榕 2019-01-30 10:35:19 看完还是有很多困惑（可能跟我不了解线程安全有关） 一是申请一段连续存储空间，怎么成为线程独享的呢？生产者ab分别申请后，消费者为啥无法跨区域读取呢 二是这种方法应该是有实验证明效率高的，私下去了解下。 M.Y 2019-01-30 10:07:55 课后思考。 如果不是分布式应用： 1.用JDK自带的AtomicLong 2.用Oracle数据库中的Sequence 如果是
25、分布式应用： 1.用zookeeper生成全局ID 2.用Redis中的Redlock 生产全局ID Keep-Moving 2019-01-30 10:06:44 54|算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战（三）：剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 思考题：加锁批量生成ID，使用时就不用加锁了 神盾局闹别扭 2019-01-30 09:56:45 有个问题，按照老师所说，a线程只写1-3
26、区块，b线程只写4-6块，假设a线程先写了块1，切换到线程b，b写块4，然后再切回线程a，a写块2。虽然没有数据 覆盖问题，但是最终块1-6的顺序不是按写入先后顺序排布的，读取不是乱套了吗，怎么解决这个问题？求老师能说的详细点。 Keep-Moving 2019-01-30 09:52:01 “当申请到这组连续的存储单元之后，后续往队列中添加元素，就可以不用加锁了”，这句话不太理解，老师能不能再说得详细些？ Jamin 2019-01-30 09:46:31 那在 3 到 6 没有完全写入数据之前，是想说3到6的数据无法被读取吧？ yann 扬 :曹同学 2019-01-30 09:43:38
27、 应该是读不需要锁，生成id时加锁，各个表的id去生成器上查一下有没有用过，不行，需要整理一下了 朝夕心 2019-01-30 08:49:04 即使3-6完全写入了，7-9也不一定可以消费吧，如果此时7-9没01|为什么要学习数据结构和算法？ file:/F/temp/geektime/数据结构与算法之美/01为什么要学习数据结构和算法？.html2019/1/15 15:35:03 01|为什么要学习数据结构和算法？ 你是不是觉得数据结构和算法，跟操作系统、计算机网络一样，是脱离实际工作的知识？可能除了面试，这辈子也用不着？ 尽管计算机相关专业的同学在大学都学过这门课程，甚至很多培训机构也
28、会培训这方面的知识，但是据我了解，很多程序员对数据结构和算法依旧一窍不 通。还有一些人也只听说过数组、链表、快排这些最最基本的数据结构和算法，稍微复杂一点的就完全没概念。 当然，也有很多人说，自己实际工作中根本用不到数据结构和算法。所以，就算不懂这块知识，只要Java API、开发框架用得熟练，照样可以把代码写 得“飞”起来。事实真的是这样吗？ 今天我们就来详细聊一聊，为什么要学习数据结构和算法。 想要通关大厂面试，千万别让数据结构和算法拖了后腿 很多大公司，比如BAT、Google、Facebook，面试的时候都喜欢考算法、让人现场写代码。有些人虽然技术不错，但每次去面试都会“跪”在算法上，
29、很是可 惜。那你有没有想过，为什么这些大公司都喜欢考算法呢？ 校招的时候，参加面试的学生通常没有实际项目经验，公司只能考察他们的基础知识是否牢固。社招就更不用说了，越是厉害的公司，越是注重考察数据结 构与算法这类基础知识。相比短期能力，他们更看中你的长期潜力。 你可能要说了，我不懂数据结构与算法，照样找到了好工作啊。那我是不是就不用学数据结构和算法呢？当然不是，你别忘了，我们学任何知识都是为 了“用”的，是为了解决实际工作问题的，学习数据结构和算法自然也不例外。 业务开发工程师，你真的愿意做一辈子CRUD boy吗？ 如果你是一名业务开发工程师，你可能要说，我整天就是做数据库CRUD（增删改查
30、），哪里用得到数据结构和算法啊？ 是的，对于大部分业务开发来说，我们平时可能更多的是利用已经封装好的现成的接口、类库来堆砌、翻译业务逻辑，很少需要自己实现数据结构和算法。 但是，不需要自己实现，并不代表什么都不需要了解。 如果不知道这些类库背后的原理，不懂得时间、空间复杂度分析，你如何能用好、用对它们？存储某个业务数据的时候，你如何知道应该用ArrayList，还 是Linked List呢？调用了某个函数之后，你又该如何评估代码的性能和资源的消耗呢？ 作为业务开发，我们会用到各种框架、中间件和底层系统，比如Spring、RPC框架、消息中间件、Redis等等。在这些基础框架中，一般都揉和了很
31、多基础数据 结构和算法的设计思想。 比如，我们常用的Key-Value数据库Redis中，里面的有序集合是用什么数据结构来实现的呢？为什么要用跳表来实现呢？为什么不用二叉树呢？ 如果你能弄明白这些底层原理，你就能更好地使用它们。即便出现问题，也很容易就能定位。因此，掌握数据结构和算法，不管对于阅读框架源码，还是理 解其背后的设计思想，都是非常有用的。 99% 01|为什么要学习数据结构和算法？ file:/F/temp/geektime/数据结构与算法之美/01为什么要学习数据结构和算法？.html2019/1/15 15:35:03 在平时的工作中，数据结构和算法的应用到处可见。我来举一个你
32、非常熟悉的例子：如何实时地统计业务接口的响应时间？ 你可能最先想到，每次查询时，从小到大排序所有的响应时间，如果总共有1200个数据，那第1188个数据就是99%的响应时间。很显然，每次用这个方法查询 的话都要排序，效率是非常低的。但是，如果你知道“堆”这个数据结构，用两个堆可以非常高效地解决这个问题。 基础架构研发工程师，写出达到开源水平的框架才是你的目标！ 现在互联网上的技术文章、架构分享、开源项目满天飞，照猫画虎做一套基础框架并不难。我就拿RPC框架举例。 不同的公司、不同的人做出的RPC框架，架构设计思路都差不多，最后实现的功能也都差不多。但是有的人做出来的框架，Bug很多、性能一般、
33、扩展性也不 好，只能在自己公司仅有的几个项目里面用一下。而有的人做的框架可以开源到GitHub上给很多人用，甚至被Apache收录。为什么会有这么大的差距呢？ 我觉得，高手之间的竞争其实就在细节。这些细节包括：你用的算法是不是够优化，数据存取的效率是不是够高，内存是不是够节省等等。这些累积起来， 决定了一个框架是不是优秀。所以，如果你还不懂数据结构和算法，没听说过大O复杂度分析，不知道怎么分析代码的时间复杂度和空间复杂度，那肯定说不 过去了，赶紧来补一补吧！ 对编程还有追求？不想被行业淘汰？那就不要只会写凑合能用的代码！ 何为编程能力强？是代码的可读性好、健壮？还是扩展性好？我觉得没法列，也列
34、不全。但是，在我看来，性能好坏起码是其中一个非常重要的评判标准。 但是，如果你连代码的时间复杂度、空间复杂度都不知道怎么分析，怎么写出高性能的代码呢？ 你可能会说，我在小公司工作，用户量很少，需要处理的数据量也很少，开发中不需要考虑那么多性能的问题，完成功能就可以，用什么数据结构和算法， 差别根本不大。但是你真的想“十年如一日”地做一样的工作吗？ 经常有人说，程序员35岁之后很容易陷入瓶颈，被行业淘汰，我觉得原因其实就在此。有的人写代码的时候，从来都不考虑非功能性的需求，只是完成功 能，凑合能用就好；做事情的时候，也从来没有长远规划，只把眼前事情做好就满足了。 我曾经面试过很多大龄候选人，简历
35、能写十几页，经历的项目有几十个，但是细看下来，每个项目都是重复地堆砌业务逻辑而已，完全没有难度递进，看不 出有能力提升。久而久之，十年的积累可能跟一年的积累没有任何区别。这样的人，怎么不会被行业淘汰呢？ 如果你在一家成熟的公司，或者BAT这样的大公司，面对的是千万级甚至亿级的用户，开发的是TB、PB级别数据的处理系统。性能几乎是开发过程中时刻都 要考虑的问题。一个简单的ArrayList、Linked List的选择问题，就可能会产生成千上万倍的性能差别。这个时候，数据结构和算法的意义就完全凸显出来了。 其实，我觉得，数据结构和算法这个东西，如果你不去学，可能真的这辈子都用不到，也感受不到它的
36、好。但是一旦掌握，你就会常常被它的强大威力所折 服。之前你可能需要费很大劲儿来优化的代码，需要花很多心思来设计的架构，用了数据结构和算法之后，很容易就可以解决了。 内容小结 我们学习数据结构和算法，并不是为了死记硬背几个知识点。我们的目的是建立时间复杂度、空间复杂度意识，写出高质量的代码，能够设计基础架构，提 升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善你的人生。 所以，不管你是业务开发工程师，还是基础架构工程师；不管你是初入职场的初级工程师，还是工作多年的资深架构师，又或者是想转人工智能、区块链这 些热门领域的程序员，数据结构与算法作为计算机的基础知识、核心知
37、识，都是必须要掌握的。 01|为什么要学习数据结构和算法？ file:/F/temp/geektime/数据结构与算法之美/01为什么要学习数据结构和算法？.html2019/1/15 15:35:03 掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。因为这样的你，就像是站在巨人的肩膀上，拿着生存利器行走世界。数据结 构与算法，会为你的编程之路，甚至人生之路打开一扇通往新世界的大门。 课后思考 你为什么要学习数据结构和算法呢？在过去的软件开发中，数据结构和算法在哪些地方帮到了你？ 欢迎留言和我分享，我会第一时间给你反馈。 01|为什么要学习数据结构和算法？ file:/F
38、/temp/geektime/数据结构与算法之美/01为什么要学习数据结构和算法？.html2019/1/15 15:35:03 精选留言： 姜威 2018-09-20 22:49:15 为什么学习数据结构和算法？我认为有3点比较重要 1.直接好处是能够有写出性能更优的代码。 01|为什么要学习数据结构和算法？ file:/F/temp/geektime/数据结构与算法之美/01为什么要学习数据结构和算法？.html2019/1/15 15:35:03 2.算法，是一种解决问题的思路和方法，有机会应用到生活和事业的其他方面。 3.长期来看，大脑思考能力是个人最重要的核心竞争力，而算法是为数不多
39、的能够有效训练大脑思考能力的途径之一。 1528赞 作者回复2018-09-21 02:07:30 写的很好 同学们把这条回复顶上去 HouShangLing 2018-09-20 22:41:00 一定要动手写 684赞 作者回复2018-09-21 02:08:56 你掌握了学这门课的最有效的方法。看十遍也没自己实现一遍学的牢。同学们这条也帮忙顶上去 wistbean 2018-09-20 19:38:17 其实问题的所在就是现在有很多现成的框架，器又大活又好，拿来就用，还不用太担心性能的问题。就好像那些建楼的工程师不需要懂砖瓦的构成，也 能盖楼。司机不需要懂汽车引擎的原理，也能当顺风车司
40、机载美女兜风。 遇到不会的上 Google，懒了就上 GitHub 找框架。所以写了这么多年代码，一直是个菜鸟。 或许是时候修炼自己的内功了。一直 CURD 有意思么？把设计模式，网络原理，数据结构和算法捡起来，或许就没那么容易菜鸟了。怼人也更加自信了 。跳槽也不用畏畏缩缩的了。 为了不当菜鸟，我和我的小伙伴们就加入了哇！ 149赞 作者回复2018-09-21 02:12:42 写的太好了 两颗小虎牙 2018-09-20 16:14:11 可不可以每次多发布几篇？ 118赞 tdytaylor 2018-09-20 16:26:29 老师，就像你说的，工作中其实好多都和业务挂钩，基本上都是
41、针对业务做增删改查，很难把所学的算法应用起来，我平时也时不时学习算法，但总感 觉学了就忘，忘了又学，如此反复，老师，这种到底是没了解算法的原理导致不会灵活应用，还是写的少导致的，感觉学习算法很少能应用起来 91赞 作者回复2018-09-21 03:33:48 1. 客观的讲，有些项目确实涉及的数据结构和算法少一些，你可以再看下我文章里写的。 2. 你提到学了又忘，我觉得一方面你是没有掌握学习的方法，学习的重点，走马观花的看肯定比较容易忘；我们02节会具体讲； 01|为什么要学习数据结构和算法？ file:/F/temp/geektime/数据结构与算法之美/01为什么要学习数据结构和算法？.
42、html2019/1/15 15:35:03 3. 不会灵活应用？那估计还是没有好的教材教你如何应用，还有可能就是确实还没掌握太牢，只是懂点皮毛，很浅，灵活应用是一个比较的境界，需要 一段时间的沉淀学习。 4. 学习算法并不是为了记住几个排序、二分查找、二叉树遍历，他还能锻炼你的逻辑思维、性能意识，而且，如果你写代码能力还有欠缺，你还可以通 过把学到的数据结构和算法都实现一遍，这是一种很好很好的锻炼编程能力的方法。所以不要过度追求一定要在项目里手写快排、手写二叉树才能算是 用上。 裴海港 2018-09-20 17:29:41 年近40的大叔也有一颗积极向上的心 82赞 作者回复2018-09
43、-21 02:17:30 终身学习 多大年纪也不晚 五岳寻仙 2018-09-20 22:55:48 老师好！看到专栏第一眼就果断订阅了。我是一个菜鸟程序员，半年的工作经验让我感受到数据结构和算法太重要了！讲一个自己亲身经历的例子。 入职不久，就遇到一个需求，需要建立一个3G(30亿)条键值对映射，已供后续检索。听上去很简单的问题，用python的字典就可以解决。但在实现的过 程中，很快就遇到了问题：字典是基于hash的，对于每条键值对要多消耗50个字节的内存维持这种结构(即便使用redis也需要这个内存花销)，再加上键 值存储消耗的内存，我大约需要3G70=210G内存，超过服务器内存了。
44、后来，想到了可以根据键排序后线性存储，使用二分查找，解决了这个问题，大约消耗的内存也就3G10=30G左右。 看似简单的问题，当规模大到一定程度，不借助算法和数据结构，就无法解决了。 74赞 作者回复2018-09-21 04:29:23 哈哈 你要是看到我讲的散列那一篇你就知道了 像java里的hashmap是比较耗内存的 你用到的解决方案是一种用时间复杂度换空间复杂度的思路 我们专栏 也会讲的 不过你现在的解决办法还可以更高效 利用hash函数 我们专栏也会讲到 还有二分是logn的时间复杂度 是非常高效的一种时间复杂度 2的64次方 个有序数据二分查找也顶多循环64次 有没有觉得logn
45、这个复杂度很奇妙 Haoz 2018-09-25 14:37:56 一、数据结构和算法是什么 1、数据结构是指一组数据的存储结构 2、算法就是操作数据的方法 3、数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构之上 二、学习的重点在什么地方 01|为什么要学习数据结构和算法？ file:/F/temp/geektime/数据结构与算法之美/01为什么要学习数据结构和算法？.html2019/1/15 15:35:03 数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。在学 习数据结构和
46、算法的过程中，要学习它的来历、自身的特点、适合解决的问题以及实际的应用场景。 1、数据结构和算法学习的精髓-复杂度分析 2、最常用的、最基础的数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树 3、最常用的算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法 感谢老师的分析，一直以来数据结构和算法都是我的硬伤，学了很多次，也放弃了很多次，可能是方法不对，但更多的是因为自己之前的毅力不够。 在此立下 flag：从本篇文章开始，将老师的文章根据自己的理解进行输出相应的总结和思考，发表成留言，并将每周三篇文章中涉及的数据结构和算法 用 Java 实现一次。 41赞 作者回复2018-09-25 14:44:37 写的很好 钳子钳子千 2018-09-20 16:12:10 大二上，刚刚学完第二章顺序表和链表（一切为了性能xd （半夜等更居然真的刷出来了（x 24赞 小麦2018 2018-09-21 01:00:58 我还是觉得王争老师自己读的音频好，亲切，有听作者亲自讲解的感觉。 21赞
个人主页
