32字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?.pdf
《32字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?.pdf》由会员分享,可在线阅读,更多相关《32字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?.pdf(11页珍藏版)》请在文库网上搜索。
1、 items; private int n = 0; 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 / head表示队头下标,tail表示队尾下标 private int head = 0; private int tail = 0; / 申请一个大小为capacity的数组 public CircularQueue(int capacity) items = new Stringcapacity; n = capacity; / 入队 pu
2、blic boolean enqueue(String item) / 队列满了 if (tail + 1) % n = head) return false; itemstail = item; tail = (tail + 1) % n; return true; / 出队 public String dequeue() / 如果head = tail 表示队列为空 if (head = tail) return null; String ret = itemshead; head = (head + 1) % n; return ret; 阻塞队列和并发队列 前面讲的内容理论比较多,看起
3、来很难跟实际的项目开发扯上关系。确实,队列这种数据结构很基础,平时的业务开发不大可能从零实现一个队列,甚至都不会 直接用到。而一些具有特殊特性的队列应用却比较广泛,比如阻塞队列和并发队列。 阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。因为此时还没有数据可取,直到队列中有了数据 才能返回;如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html
4、2019/1/15 15:35:21 你应该已经发现了,上述的定义就是一个“生产者-消费者模型”!是的,我们可以使用阻塞队列,轻松实现一个“生产者-消费者模型”! 这种基于阻塞队列实现的“生产者-消费者模型”,可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快,“消费者”来不及消费时,存储数据的队列 很快就会满了。这个时候,生产者就阻塞等待,直到“消费者”消费了数据,“生产者”才会被唤醒继续“生产”。 而且不仅如此,基于阻塞队列,我们还可以通过协调“生产者”和“消费者”的个数,来提高数据的处理效率。比如前面的例子,我们可以多配置几个“消费者”,来应 对一个“生产者”。 09|队列:
5、队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 前面我们讲了阻塞队列,在多线程情况下,会有多个线程同时操作队列,这个时候就会存在线程安全问题,那如何实现一个线程安全的队列呢? 线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在enqueue()、dequeue()方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或 者取操作。实际上,基于数组的循环队列,利用CAS原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛
6、的原因。在实战篇 讲Disruptor的时候,我会再详细讲并发队列的应用。 解答开篇 队列的知识就讲完了,我们现在回过来看下开篇的问题。线程池没有空闲线程时,新的任务请求线程资源时,线程池该如何处理?各种处理策略又是如何实现的 呢? 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 我们一般有两种处理策略。第一种是非阻塞的处理方式,直接拒绝任务请求;另一种是阻塞的处理方式,将请求排队,等到有空闲线程时,取出排队的请求继续 处理。那如何存储排队的请
7、求呢? 我们希望公平地处理每个排队的请求,先进者先服务,所以队列这种数据结构很适合来存储排队请求。我们前面说过,队列有基于链表和基于数组这两种实现方 式。这两种实现方式对于排队请求又有什么区别呢? 基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的响应时间过长。所以,针 对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。 而基于数组实现的有界队列(bounded queue),队列的大小有限,所以线程池中排队的请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏 感的系统来说,就相
8、对更加合理。不过,设置一个合理的队列大小,也是非常有讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资 源、发挥最大性能。 除了前面讲到队列应用在线程池请求排队的场景之外,队列可以应用在任何有限资源池中,用于排队请求,比如数据库连接池等。实际上,对于大部分资源有限 的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。 内容小结 今天我们讲了一种跟栈很相似的数据结构,队列。关于队列,你能掌握下面的内容,这节就没问题了。 队列最大的特点就是先进先出,主要的两个操作是入队和出队。跟栈一样,它既可以用数组来实现,也可以用链表来实现。用数组实现的叫顺序队列,用
9、链表实 现的叫链式队列。特别是长得像一个环的循环队列。在数组实现队列的时候,会有数据搬移操作,要想解决数据搬移的问题,我们就需要像环一样的循环队列。 循环队列是我们这节的重点。要想写出没有bug的循环队列实现代码,关键要确定好队空和队满的判定条件,具体的代码你要能写出来。 除此之外,我们还讲了几种高级的队列结构,阻塞队列、并发队列,底层都还是队列这种数据结构,只不过在之上附加了很多其他功能。阻塞队列就是入队、出 队操作可以阻塞,并发队列就是队列的操作多线程安全。 课后思考 1. 除了线程池这种池结构会用到队列排队请求,你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢? 2. 今天讲到
10、并发队列,关于如何实现无锁并发队列,网上有非常多的讨论。对这个问题,你怎么看呢? 欢迎留言和我分享,我会第一时间给你反馈。 我已将本节内容相关的详细代码更新到GitHub,戳此即可查看。 09|队列:队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列:队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 精选留言: 城 2018-10-10 00:46:32 1.分布式应用中的消息队列,也是一种队列结构 2.考虑使用CAS实现无锁队列,则在入队前,获取tail位置,入队时比较tail是否发生变化,如果否,则允许入
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 32 字符串 匹配 基础 如何 借助 算法 实现 高效