Redian新闻
>
当 LinkedList 不是列表时,速度快的兔子都追不上!

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

公众号新闻

点击上方“芋道源码”,选择“设为星标

管她前浪,还是后浪?

能浪的浪,才是好浪!

每天 10:33 更新文章,每天掉亿点点头发...

源码精品专栏

 
来源:小姐姐味道

ArrayList和LinkedList有什么区别?

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

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

你Over了。

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

public class ArrayList<Eextends AbstractList<E>
        implements List<E>, RandomAccessCloneablejava.io.Serializable

//VS

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneablejava.io.Serializable

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

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

王者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。

基于 Spring Boot + MyBatis Plus + Vue & Element 实现的后台管理系统 + 用户小程序,支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能

  • 项目地址:https://github.com/YunaiV/ruoyi-vue-pro
  • 视频教程:https://doc.iocoder.cn/video/

关键代码

要了解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();
        }
    }
}

基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 实现的后台管理系统 + 用户小程序,支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能

  • 项目地址:https://github.com/YunaiV/yudao-cloud
  • 视频教程:https://doc.iocoder.cn/video/

主要方法

轻量级的延迟队列,如果一旦采用了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,对这些淳朴的工具进行封装,它们就会焕发出新的活力。



欢迎加入我的知识星球,一起探讨架构,交流源码。加入方式,长按下方二维码噢

已在知识星球更新源码解析如下:

最近更新《芋道 SpringBoot 2.X 入门》系列,已经 101 余篇,覆盖了 MyBatis、Redis、MongoDB、ES、分库分表、读写分离、SpringMVC、Webflux、权限、WebSocket、Dubbo、RabbitMQ、RocketMQ、Kafka、性能测试等等内容。

提供近 3W 行代码的 SpringBoot 示例,以及超 4W 行代码的电商微服务项目。

获取方式:点“在看”,关注公众号并回复 666 领取,更多内容陆续奉上。

文章有帮助的话,在看,转发吧。

谢谢支持哟 (*^__^*)

微信扫码关注该文公众号作者

戳这里提交新闻线索和高质量文章给我们。
相关阅读
小牛电动车,为何追不上雅迪和爱玛?刚刚,人口突破80亿!哪里人口增长速度快?Logitech Pro Y-U0031 Tenkeyless Wired Gaming Keyboard30岁以后冻脸的秘密,每天一包,让细纹追不上你!顾月华:情人墙隔不开的兔子,一屋子等待中的老小 | 二湘空间兔年到了,吃十多种口味的兔子不过分吧?如何提高记忆力和思维力墨尔本将超过悉尼,成澳洲第一大城市!人口增长速度快,将在几年内实现反超!波的折射现象你都知道哪些?当波进入慢速介质时,速度和波长都会产生变化...往事如烟,和女王的绵绵不了情健身学会吃“脂肪”,增肌减脂速度快一倍?为催修车工速度快些,男子谎自己是杀人犯,结果险些被警察击毙黄永玉的兔子好在哪里?兔年小手工| 兔子剪纸和兔子红包今年冬天很难过!新冠善变 疫苗补强剂追不上一只充满“妖气”的兔子,再一次撕裂了网络火了120年的兔子,超全纪念版+原版玩偶,兔年送孩子太喜欢!Rosalía 登意大利版《VOGUE》封面!穷山恶水出刁民,绿水青山养文人(3)惨烈|加拿大18城房价技术性崩盘!温哥华独立屋均价年跌35万!价格最坚挺的竟是列治文?硬核观察 #822 电子书的“磨损”速度快于实体书at标号与“圈a”该买新年战衣啦!这款软fufu的兔子毛衣,吸睛又百搭~最航运 | ONE的担忧 需求下降的速度快于集运市场调整供给侧产能的速度小牛电动车,为何追不上雅迪和爱玛?两轮“特斯拉”不好当10月10日:用秒表看员工速度快不快,用指南针看员工方向对不对这只最受争议的兔子!竟出自99岁黄永玉之手,或成“绝唱”!“退款速度赶不上发货速度”,上海消保委有提醒物理改变图像生成:扩散模型启发于热力学,比它速度快10倍的挑战者来自电动力学中国成功拿下6G专利,比5G速度快50倍,老美彻底傻眼!畅游法国(19)-葡萄酒之都世界儿童文学经典广播剧系列 |《爱丽丝梦游仙境》第一集之神奇的兔子洞人口突破80亿,哪里人口增长速度快?[惨烈]加国18城房价崩盘!温哥华独立屋均价年跌35万!价格最坚挺的竟是列治文?戴尔拟2024年前停用中国产芯片,外迁速度快于行业预计
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。