您当前的位置:首页 > 电脑百科 > 程序开发 > 编程百科

当 LinkedList 不是列表时,速度快的兔子都追不上

时间:2022-10-11 14:39:44  来源:微信公众号  作者:小姐姐味道

原创:小姐姐味道(微信公众号ID:xjjdog),欢迎分享,转载请保留出处。

ArrayList和LinkedList有什么区别?

这种侮辱人的问题,默认就把这两者限定在了同一个场景之中,它甚至连八股文都算不上。

一旦你被问到这种问题,也证明面试基本上泡汤了--面试官已经实在是找不到其他问题与你交流了。

你Over了。

但当我们细看一下LinkedList的class定义,就会发现,它并不像是ArrayList的那样具有纯洁的列表精神。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, Randomaccess, Cloneable, JAVA.io.Serializable
//VS
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList除了能够当作普通的列表,它还是一个Deque。双向链表,听着就比较唬人,这就是一个既能当做队列、又能当做栈的存在。

有了这种双重Buff的叠加,LinkedList的应用场景比ArrayList丰富的多。除了能做最简单的LRU缓存,LinkedList在刷题的时候也是充满了正能量。

关于类似Deque的API,xjjdog以前有专门的文章来介绍这些爆炸性的方法。

《带你见识一下,JAVA中的方法爆炸!》

王者ConcurrentLinkedQueue,一个阻塞的双向队列,它的基本操作方法有:(3[基本]x2[异常与返回值]+4[阻塞加超时])x3[队头队尾]=5x2x3=30,足足有30个方法。看完上面的文章,这30个方法可以很快手到擒来。

不过我们今天要聊的一个重点,是使用Deque来实现更快的延迟队列。

延迟队列

如果你想要某些数据延迟一段时间再进行处理,或者要再某段时间内按照分组进行一些计算,那延迟队列无疑是非常合适的。

在Java的Concurrent包里,就静悄悄的躺着DelayQueue。只要你的数据实现了Delayed接口,那么就可以放心大胆的把它们往里面塞。

可惜的是,DelayQueue的底层存储,使用的是PriorityQueue。

PriorityQueue是堆实现的,offer和poll数据的时间复杂度是O(logN)。这就意味着,当DelayQueue中的数据比较多的时候,它的性能就会下降。

除了把数据分片,使用多个DelayQueue来完成工作,我们有没有速度更快的方法?比如把PriorityQueue使用LinkedList来替换?

这要看场景。

如果你向DelayQueue中添加数据,是与当前添加的时间相关的,那完全可以使用LinkedList来替换PriorityQueue。

关键代码

要了解DelayQueue的运行原理,我们可以需要先看一下Delayed接口。任何想要存储到DelayQueue中的数据,都需要实现这个接口。

其中,getDelay就是用来判断当前数据是否超时的方法。而compareTo,则是PriorityQueue用来排序的,如果我们是按照当前塞入数据的,则compareTo方法就不是必要的。

public long getDelay(@NotNull TimeUnit unit) {
    return MAX_CACHE_DUAL + this.enqueueTimeNs - System.nanoTime();
}
public int compareTo(@NotNull Delayed o) {
    long d = getDelay(TimeUnit.NANOSECONDS) - o.getDelay(TimeUnit.NANOSECONDS);
    return (d == 0) ? 0 : (d < 0 ? -1 : 1);
}

按照以上的思路,我们把DelayQueue的代码拷贝一份,仅保留关键代码,如下。

public class LightweightDelayedQueue<E extends Delayed> {
    private final transient ReentrantLock lock = new ReentrantLock();
    private final LinkedList<E> q = new LinkedList<>();
    private final Condition avAIlable = lock.newCondition();
    private Thread leader;
    public void put(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            q.offer(e);
            if (q.peek() == e) {
                leader = null;
                available.signal();
            }
        } finally {
            lock.unlock();
        }
    }
    public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            for (; ; ) {
                E first = q.peek();
                if (first == null)
                    available.await();
                else {
                    long delay = first.getDelay(NANOSECONDS);
                    if (delay <= 0L)
                        return q.poll();
                    first = null; // don't retain ref while waiting
                    if (leader != null)
                        available.await();
                    else {
                        Thread thisThread = Thread.currentThread();
                        leader = thisThread;
                        try {
                            available.awaitNanos(delay);
                        } finally {
                            if (leader == thisThread)
                                leader = null;
                        }
                    }
                }
            }
        } finally {
            if (leader == null && q.peek() != null)
                available.signal();
            lock.unlock();
        }
    }
    public int size() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return q.size();
        } finally {
            lock.unlock();
        }
    }
    public int drainTo(Collection<? super E> c, int maxElements) {
        Objects.requireNonNull(c);
        if (c == this)
            throw new IllegalArgumentException();
        if (maxElements <= 0)
            return 0;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int n = 0;
            for (E first;
                 n < maxElements
                         && (first = q.peek()) != null
                         && first.getDelay(NANOSECONDS) <= 0; ) {
                c.add(first);   // In this order, in case add() throws.
                q.poll();
                ++n;
            }
            return n;
        } finally {
            lock.unlock();
        }
    }
}

主要方法

轻量级的延迟队列,如果一旦采用了LinkedList,那么它的入队、出队方法,就都变成了O(1)的时间复杂度。在延迟队列中的数据增加时,时间复杂度也能维持不变,可以说是速度快的连兔子都追不上了。

一般,在java中,put和take方法,都是代表阻塞性方法。比如,take方法,我们可以将其安全的阻塞在某个线程上,而不用担心太多的资源浪费。

final Thread thread = Thread.currentThread();
while (!this.close && !thread.isInterrupted()) {
    Data data = q.take();
}

这一切都是Condition办到的,它和wait、notify的作用是一样的。

当我们通过put方法添加新的数据到队列中,会通过signal方法,来通知等待的线程获取数据。

相同的,如果take方法发现队列中的数据为空,它将进入等待状态。如果有数据,也并不是马上把这些数据取出来,因为数据还没到期。比如最老的数据还剩下5秒才到期,代码也对这种情况进行了处理,它会尝试awaitNanos对应的时间。

这样,我们就可以使用这种简单的轮询方式来实现延迟队列,而不需要单独的线程去检测队列中的数据。

增加take方法的效率

但是这样还不够。

当数据量比较大的时候,队列的数据可能有多条已经到期。如果我们通过take方法来一条一条获取的话,效率自然不如批量获取高。

drainTo方法,可以一股脑的把到期的数据转移到其他的集合中,但它并不是一个阻塞性的方法。

我们可以先使用take来阻塞线程,然后再批量取出所有数据。

下面代码,会一次性获取100条数据作为一个批量。

final Data takeItem = q.take();
final List<Data> buckets = new ArrayList<>(100);
q.drainTo(buckets, 99);
buckets.add(takeItem);

End

实际上,我们的某个业务,当采用LinkedList来替代PriorityQueue,并进行批量操作后,CPU的使用直接降低了1/3。

Deque是xjjdog最喜欢的一个接口。每当使用offerFirst、offerLast这样精准的API进行操作,都会体验到多巴胺的乐趣。LinkedList作为它的儿子,自然拥有了这些所有的功能。

当我们使用concurrent包里的基本API,对这些淳朴的工具进行封装,它们就会焕发出新的活力。

作者简介:小姐姐味道 (xjjdog),一个不允许程序员走弯路的公众号。聚焦基础架构linux。十年架构,日百亿流量,与你探讨高并发世界,给你不一样的味道。



Tags:LinkedList   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
ArrayList和LinkedList怎么选,想过吗?
我们都知道,磁盘IO以块为单位读取数据,如果你所需要的数据都存储在一个块呢,一次IO即可返回。如果跨越多个块,只要你的块是连续的,类似MYSQl,基于预读机制,一次读取多个块的数据。...【详细内容】
2023-05-16  Search: LinkedList  点击:(448)  评论:(0)  加入收藏
当 LinkedList 不是列表时,速度快的兔子都追不上
原创:小姐姐味道(微信公众号ID:xjjdog),欢迎分享,转载请保留出处。ArrayList和LinkedList有什么区别?这种侮辱人的问题,默认就把这两者限定在了同一个场景之中,它甚至连八股文都算不...【详细内容】
2022-10-11  Search: LinkedList  点击:(247)  评论:(0)  加入收藏
JAVA中ArrayList、LinkedList、Vector、Stack的比较
一、介绍先回顾一下List的框架图 由图中的继承关系,可以知道,ArrayList、LinkedList、Vector、Stack都是List的四个实现类。 AbstractList是一个抽象类,它继承于AbstractCollec...【详细内容】
2019-11-07  Search: LinkedList  点击:(615)  评论:(0)  加入收藏
▌简易百科推荐
Netflix 是如何管理 2.38 亿会员的
作者 | Surabhi Diwan译者 | 明知山策划 | TinaNetflix 高级软件工程师 Surabhi Diwan 在 2023 年旧金山 QCon 大会上发表了题为管理 Netflix 的 2.38 亿会员 的演讲。她在...【详细内容】
2024-04-08    InfoQ  Tags:Netflix   点击:(2)  评论:(0)  加入收藏
即将过时的 5 种软件开发技能!
作者 | Eran Yahav编译 | 言征出品 | 51CTO技术栈(微信号:blog51cto) 时至今日,AI编码工具已经进化到足够强大了吗?这未必好回答,但从2023 年 Stack Overflow 上的调查数据来看,44%...【详细内容】
2024-04-03    51CTO  Tags:软件开发   点击:(7)  评论:(0)  加入收藏
跳转链接代码怎么写?
在网页开发中,跳转链接是一项常见的功能。然而,对于非技术人员来说,编写跳转链接代码可能会显得有些困难。不用担心!我们可以借助外链平台来简化操作,即使没有编程经验,也能轻松实...【详细内容】
2024-03-27  蓝色天纪    Tags:跳转链接   点击:(13)  评论:(0)  加入收藏
中台亡了,问题到底出在哪里?
曾几何时,中台一度被当做“变革灵药”,嫁接在“前台作战单元”和“后台资源部门”之间,实现企业各业务线的“打通”和全域业务能力集成,提高开发和服务效率。但在中台如火如荼之...【详细内容】
2024-03-27  dbaplus社群    Tags:中台   点击:(9)  评论:(0)  加入收藏
员工写了个比删库更可怕的Bug!
想必大家都听说过删库跑路吧,我之前一直把它当一个段子来看。可万万没想到,就在昨天,我们公司的某位员工,竟然写了一个比删库更可怕的 Bug!给大家分享一下(不是公开处刑),希望朋友们...【详细内容】
2024-03-26  dbaplus社群    Tags:Bug   点击:(5)  评论:(0)  加入收藏
我们一起聊聊什么是正向代理和反向代理
从字面意思上看,代理就是代替处理的意思,一个对象有能力代替另一个对象处理某一件事。代理,这个词在我们的日常生活中也不陌生,比如在购物、旅游等场景中,我们经常会委托别人代替...【详细内容】
2024-03-26  萤火架构  微信公众号  Tags:正向代理   点击:(11)  评论:(0)  加入收藏
看一遍就理解:IO模型详解
前言大家好,我是程序员田螺。今天我们一起来学习IO模型。在本文开始前呢,先问问大家几个问题哈~什么是IO呢?什么是阻塞非阻塞IO?什么是同步异步IO?什么是IO多路复用?select/epoll...【详细内容】
2024-03-26  捡田螺的小男孩  微信公众号  Tags:IO模型   点击:(9)  评论:(0)  加入收藏
为什么都说 HashMap 是线程不安全的?
做Java开发的人,应该都用过 HashMap 这种集合。今天就和大家来聊聊,为什么 HashMap 是线程不安全的。1.HashMap 数据结构简单来说,HashMap 基于哈希表实现。它使用键的哈希码来...【详细内容】
2024-03-22  Java技术指北  微信公众号  Tags:HashMap   点击:(11)  评论:(0)  加入收藏
如何从头开始编写LoRA代码,这有一份教程
选自 lightning.ai作者:Sebastian Raschka机器之心编译编辑:陈萍作者表示:在各种有效的 LLM 微调方法中,LoRA 仍然是他的首选。LoRA(Low-Rank Adaptation)作为一种用于微调 LLM(大...【详细内容】
2024-03-21  机器之心Pro    Tags:LoRA   点击:(12)  评论:(0)  加入收藏
这样搭建日志中心,传统的ELK就扔了吧!
最近客户有个新需求,就是想查看网站的访问情况。由于网站没有做google的统计和百度的统计,所以访问情况,只能通过日志查看,通过脚本的形式给客户导出也不太实际,给客户写个简单的...【详细内容】
2024-03-20  dbaplus社群    Tags:日志   点击:(4)  评论:(0)  加入收藏
站内最新
站内热门
站内头条