详解九章算法的作者是谁_arrayset

详解九章算法的作者是谁_arraysetArrayDeque方法很多,而他们按过程划分分为三种,初始化,扩容,CRUD操作。下面依次来说初始化过程中依赖一个核心的函数calculateSize,它的源码如下privatestaticintcalculateSize(intnumElements){intinitialCapacity=MIN_INITIAL_CAPACITY;//Findthebestpoweroftwotoholdelements.

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

ArrayDeque方法很多,而他们按过程划分分为三种,初始化,扩容,CRUD操作。

下面依次来说

初始化过程中依赖一个核心的函数calculateSize,

它的源码如下

private static int calculateSize(int numElements) {
        int initialCapacity = MIN_INITIAL_CAPACITY;
        // Find the best power of two to hold elements.
        // Tests "<=" because arrays aren't kept full.
        if (numElements >= initialCapacity) {
            initialCapacity = numElements;
            initialCapacity |= (initialCapacity >>>  1);
            initialCapacity |= (initialCapacity >>>  2);
            initialCapacity |= (initialCapacity >>>  4);
            initialCapacity |= (initialCapacity >>>  8);
            initialCapacity |= (initialCapacity >>> 16);
            initialCapacity++;

            if (initialCapacity < 0)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        return initialCapacity;
    }

首先它的作用是处理输入的容量,使之为2的倍数,如果处理后发生溢出,则向右算术右移一位。

具体实现过程是在if代码块中,整体的目标是使得输入数字的二进制最高位及以后全为一,之后加1。结果必然只有最高位为1,其余全为0.

那么为什么恰好5次移位即可完成的,我用递归来辅助大家理解。

public static int get(int n) {
        if(n == 0) {
            return 1;
        }

        return 2 * get(n - 1);
    }

首先,每次移位之后,新生成的1和之前所有的1必然不碰撞,即他们之间相互独立。因此,可以用递归来表达整个的移位过程,默认不考虑0,输入n为移动次数,结果是不考虑位宽限制下的最高位移动n次后的1的总数量。

当输入n为0时,不移动,最高位1不动,总共1个1。

当输入n大于1时,最高位移动移位,生成的1和本身的1开始新的移动过程即get(n – 1) + get(n – 1) = 2 * get(n- 1)。通过式子可以发现,当n = 5时,可以使得从最高位1开始的32位全为1.而int只有32位,也就是说可以使得从最高位开始所有的位都为1.

最后做一个边界情况的处理,如果进来的数字小于MIN_INITIAL_CAPACITY(8),直接返回

initialCapacity。

下面开始讲CRUD。

这里面有许多方法,他们底层调用了四个方法addFirst,addLast,pollFirst,pollLast。

一个个来说

addFirst
public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[head = (head - 1) & (elements.length - 1)] = e;
        if (head == tail)
            doubleCapacity();
    }

它的主体逻辑是,取模获取index,之后赋值。而取模的过程它利用数组的长度是2的倍数这一特性用位运算取代了模运算,提高了效率。这同样也意味着,扩容之后长度也必须是2的倍数,这决定了长度最大为2^30。

另外的点是为什么使用head,而不是tail,用head-1这个操作。

这需要讲到ArrayDeque的架构。它有两个描述数组的变量,head和tail。head表示队列的头,tail表示尾可插入的位置,一个elements描述存储变量的数组结构。均不可序列化。

插入遵循着一个约定,先插入,再处理扩容问题。

addLast

public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

在index上是有区别的,head是先移位,再赋值(插入)。而tail是先赋值再移位。

当输入为null时都抛异常。

二者讲完要讲doubleCapacity这个重要的扩容函数了。

doubleCapacity

private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

首先扩容,容量为原来的两倍,如果溢出,抛出异常(这是运行时异常)。之后,分两段复制,一段为[head, elements.length),一段为[0, head)。之所以要这样复制,也是因为System.arraycopy的缘故。因为如果写

        for (int i = 0; i < n; i++) {
            a[i] = elements[head & (elements.length - 1)];
            head = (head + 1) & elements.length;
        }

从实现上来讲是没有问题的,但是其没有调用系统提供的调用,从效率上来讲会差一点(经过试验,使用系统调用会是下面的实现性能的2倍),而且不够优雅,扩展性不足。

下面开始讲

pollFirst

public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }

首先会用

@SuppressWarnings忽略unchecked警告。

之后如果没有,返回null。否则将此位置设为null,并将head向前移动移位。设为null,这个操作是必须的,因为这表示数据被弹出。而ArrayDeque又不允许输入为null,这样数组内为null的槽为空槽,不为null的槽即为在使用的槽

pollLast

public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

整体流程和pollFirst无区别,只是要注意tail – 1.为什么减一参照之前的说明。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/191637.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • docker启动mysql容器失败_docker容器

    docker启动mysql容器失败_docker容器什么是Docker?Docker是一种工具,它让容器创建,部署和运行应用程序变得更加容易。容器使开发人员可以将应用程序与所需的所有部分(如库和其他依赖项)打包在一起,并将其作为一个包进行部署。这样,借助容器,开发人员可以放心,该应用程序可以在任何其他Linux机器上运行,而不用管该机器的环境配置。安装DockerDesktop前往官方网站:www.docker.com/get-started根据操作系统,下载并安装对应的DockerDesktop。验…

  • pycharm 安装第三方库指南

    pycharm 安装第三方库指南当pycharm中没有你想要的安装包时,需要自己在pypi中下载或是其他方式下载,清华镜像网站等;只用alt+f12打开pycharm控制台,然后将下载的文件放在显示的目录里下载即可。

  • consolewriteline用法_promise sb to do

    consolewriteline用法_promise sb to do1.Promise的含义Promise是异步编程的一种解决方案,比传统的解决方案——回调函数和事件——更合理和更强大。它由社区最早提出和实现,ES6将其写进了语言标准,统一了用法,原生提供了P

  • pycharm 中文输入_pycharm中文输入法

    pycharm 中文输入_pycharm中文输入法1.Pycharm编译器中英文切换1.左上角打开file(文件)—>setting(设置)—plugins(插件)2.搜索chinese,点击安装3.安装完根据提示重启就行2.pycharm输入法不能输入中文1.找到pycharm的bin文件(我的是在/opt/pycharm/bin)2.打开pycharm.sh,在当前区域添加以下代码(我的是第144行)。如果是fcitx输入框架,则ibus换成fcitxexportLC_ALL=zh_CN.UTF-8expor

  • phy芯片与rj45接法_232接口详细接线图

    phy芯片与rj45接法_232接口详细接线图千兆PHY通过网络变压器连接到RJ45接口,一共有4对差分线MDI[0..3]+/-。一般的接法是: MDI[0]+:RJ45[1] MDI[0]-:RJ45[2] MDI[1]+:RJ45[3] MDI[1]-:RJ45[6] MDI[2]+:RJ45[4] MDI[2]-:RJ45[5] MDI[3]+:RJ45[7]

  • 粒子群算法详解

    粒子群算法详解一.产生背景  ❃粒子群算法(particleswarmoptimization,PSO)由Kennedy和Eberhart在1995年提出,该算法对于Hepper的模拟鸟群(鱼群)的模型进行修正,以使粒子能够飞向解空间,并在最好解处降落,从而得到了粒子群优化算法。❃同遗传算法类似,也是一种基于群体叠代的,但并没有遗传算法用的交叉以及变异,而是粒子在解空间追随最优的粒子进行搜索。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号