（一）数组：为什么很多编程语言中数组都从0开始编号？ 作者: lovingyu_er 时间: 2019-05-11 19:35:00 分类: 数据结构和算法之美,JAVA 评论 ##为什么数组要从0开始编号（索引），而不是从1开始(⊙o⊙)? 从1开始不是更符合人类的思维习惯？ #####如何实现随机访问？ 关于数组的定义： 数组（Array)是一种**线性表**数据结构。它用一组**连续的内存空间**，来存储一组具有相同类型的数据。 对于数组定义的几个关键字，来了解一下数组的概念 第一：线性表（Linear List)。就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前后两个方向。其实，除了数组，链表、队列、栈等也是线性表结构。  而与它相对立的概念是**非线性表**，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。  第二：是连续的内存空间和相同类型的数据。 这个连续的内存空间可以理解，但是对于相同类型的数据，有的语言没有这些要求，比如PHP的数组，其数据类型都是可以是随意的。 数组的这两个连续的内存空间和相同类型的数据的限制，保证了数组有了这两个特性：”随机访问“。但是这两个限制也让数组的很多的操作变得非常的低效，比如，想要在数组中删除、插入一个数据，为了保证内存连续性，就需要做大量的数据迁移工作。 说道了数据的访问，那么数组是如何实现根据下标随机访问数组元素的(⊙o⊙)? 我们重点一JAVA语言为案例： 一个长度为10的int类型的数组 ，```int[] a = new int[10];```,计算机为数组a[10]分配了一块连续内存空间1000~1039,七中内存的首地址为base_address =1000; 如下图：  计算机会给每个内存单元分配一个地址，计算机通过地址来访问内存中的数据。当 计算机需要随机访问数组中的某个元素的时候，它会首先通过下面的寻址公式，计算出该元素存储的内存地址： ```a[i]_address = base_address + i * data_type_size``` Tips: data_type_size 表示数组中每个元素的大小，案例中的int类型的数组，int类型的占4个字节，那么data_type_size =4 字节 数组比较适合查找操作，但是查找的时间复杂度并不为O(1).即便是排序号的数组，你用二分查找，时间的复杂度也是O(logn)。数组支持随机访问，根据下标随机访问的时间复杂度是O（1）。 ####低效的”插入“和”删除“ 由于数组在内存的地址要保持内存数据的连续性，会导致插入、删除这两个操作比较低效。那么原因是什么(⊙o⊙)?？ **插入操作** 案例：一个数组的长度为n，我们需要将一个数据插入到数组中第K 个位置。为了把第k个位置腾出来，给新来的数据，我们需要将第k~n这部分的元素都顺序的往后挪动，那插入的时间的复杂度会是多少呢？如果是末尾插入，时间复杂度为O（1），但是如果是在数组的开头插入，那么所有的数据都要往后挪动，那么 这种最坏的时间复杂度是O（n).因为我们在每个位置插入元素的概率都是一样的，所以平均情况时间复杂度为（1+2+3+...n)/n = O（n); 如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。 **删除操作** 为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就会不连续了。 其复杂度，经过分析，和数组的插入的的时间复杂度咿呀个。 实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？ 我们继续来看例子。数组 a[10] 中存储了 8 个元素：a，b，c，d，e，f，g，h。现在，我们要依次删除 a，b，c 三个元素。  为了**避免 d，e，f，g，h 这几个数据会被搬移三次，我们可以先记录下已经删除的数据**。每次的删除操作并不是真正地搬移数据，只是**记录数据已经被删除**。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。这就是JVM标记清除垃圾回收算法的核心思想。 ###容器能否完全取代数组？ 很多语言都提供了容器类，比如Java中的ArrayList、C++ STL中的vector。 对于容器来说，可以将很多数组操作的细节封装起来，支持动态扩容（Redis的SDS结构):数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。但是当我们使用ArrayList的时候，我们不需要去关心底层是如何实现的扩展逻辑，容器已经帮我们实现好了，每一次空间不够的时候，它都会讲空间自动扩容为1.5倍大小。扩容操作涉及内存申请和数据迁移，如果开发的时候能够确定存储数据的大小，最好在创建的ArrayList的时候，事先指定好数据大小，这样会省去很多**内存申请**和**数据迁移**操作。在做业务开发的时候，如果资源充足，直接使用容器就可以满足了，省时省力。毕竟耗损一丢丢性能，完全不会影响到系统整体的性能。但是如果你要做一些非常底层的开发，比如：开发网络框架，性能的优化需要做到极致，那么这个时候使用数组比较明智。 ##数组从0开始的问题。 从数组存储的内存模型上来看，”下标“最确切的定义应该是"偏移(offset)".如果用a来表示数组的首地址，那么a[0]就是偏移为0的地址，也就是首地址，a[k]就是偏移k个type_size的位置，所以计算a[k]的内存地址只需要用这个公式: ```a[k]_address = base_address + k * type_size``` 假如我们数组从1开始的化，我们的内存地址的计算数组a[k]的内存地址就会变成： ```a[k]_address = base_address + (k-1)*type_size``` 下面的公式比上面的公司多了一次减法 的运算，对于CPU来说，就多了一个减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。C 语言设计者用 0 开始计数数组下标，之后的 Java、JavaScript 等高级语言都效仿了 C 语言，或者说，为了在一定程度上减少 C 语言程序员学习 Java 的学习成本，因此继续沿用了从 0 开始计数的习惯。实际上，很多语言中数组也并不是从 0 开始计数的，比如 Matlab。甚至还有一些语言支持负数下标，比如 Python。 大多数主流虚拟机采用可达性分析算法来判断对象是否存活，在标记阶段，会遍历所有 GC ROOTS，将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后，清理工作才会开始。 不足： 1.效率问题。标记和清理效率都不高，但是当知道只有少量垃圾产生时会很高效。 2.空间问题。会产生不连续的内存空间碎片。 二维数组内存寻址： 对于 m * n 的数组，a [ i ][ j ] (i < m,j < n)的地址为： address = base_address + ( i * n + j) * type_size 另外，对于数组访问越界造成无限循环，我理解是编译器的问题，对于不同的编译器，在内存分配时，会按照内存地址递增或递减的方式进行分配。老师的程序，如果是内存地址递减的方式，就会造成无限循环。
Ubuntu 19.04 安装java8 作者: lovingyu_er 时间: 2019-05-10 12:21:00 分类: NGINX,JAVA 评论 安装环境： ubuntu 19.04 ####apt源安装 安装步骤： 1.```sudo apt-get update``` 2.```sudo apt-get install openjdk-8-jdk``` 3.确认是否安装成功: ```bash darrykinger@darrykinger-F117-B:~/tvupd$ java --version openjdk 11.0.3 2019-04-16 OpenJDK Runtime Environment (build 11.0.3+7-Ubuntu-1ubuntu1) OpenJDK 64-Bit Server VM (build 11.0.3+7-Ubuntu-1ubuntu1, mixed mode) ``` 这样，就可以安装java 的IDE工具了。 Eclipse 在Ubuntu的软件管理中心搜索即可，直接点击```install``` 即可，如果没有java环境，你在```launch```的时候，会提示你没有Java Virtual Machine的环境，这个时候就是提示你要安装Java的环境。