• 关于

    最大分段大小工作原理

    的搜索结果

问题

HBase最佳实践-读性能优化策略

转载自:http://www.hbase.group/article/32 任何系统都会有各种各样的问题,有些是系统本身设计问题,有些却是使用姿势问题。HBase也一样,在真实生产线...
pandacats 2019-12-20 21:02:08 0 浏览量 回答数 0

回答

遍历一个 List 有哪些不同的方式?每种方法的实现原理是什么?Java 中 List 遍历的最佳实践是什么? 遍历方式有以下几种: for 循环遍历,基于计数器。在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。 迭代器遍历,Iterator。Iterator 是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。 foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现,使用时不需要显式声明 Iterator 或计数器。优点是代码简洁,不易出错;缺点是只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。 最佳实践:Java Collections 框架中提供了一个 RandomAccess 接口,用来标记 List 实现是否支持 Random Access。 如果一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1),如ArrayList。如果没有实现该接口,表示不支持 Random Access,如LinkedList。 推荐的做法就是,支持 Random Access 的列表可用 for 循环遍历,否则建议用 Iterator 或 foreach 遍历。 说一下 ArrayList 的优缺点 ArrayList的优点如下: ArrayList 底层以数组实现,是一种随机访问模式。ArrayList 实现了 RandomAccess 接口,因此查找的时候非常快。ArrayList 在顺序添加一个元素的时候非常方便。 ArrayList 的缺点如下: 删除元素的时候,需要做一次元素复制操作。如果要复制的元素很多,那么就会比较耗费性能。插入元素的时候,也需要做一次元素复制操作,缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。 如何实现数组和 List 之间的转换? 数组转 List:使用 Arrays. asList(array) 进行转换。List 转数组:使用 List 自带的 toArray() 方法。 代码示例: ArrayList 和 LinkedList 的区别是什么? 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。内存空间占用:LinkedList 比 ArrayList 更占内存,因为 LinkedList 的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。线程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全; 综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。 补充:数据结构基础之双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 ArrayList 和 Vector 的区别是什么? 这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合 线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。性能:ArrayList 在性能方面要优于 Vector。扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。 Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。 Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。 插入数据时,ArrayList、LinkedList、Vector谁速度较快?阐述 ArrayList、Vector、LinkedList 的存储性能和特性? ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢。 Vector 中的方法由于加了 synchronized 修饰,因此 Vector 是线程安全容器,但性能上较ArrayList差。 LinkedList 使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但插入数据时只需要记录当前项的前后项即可,所以 LinkedList 插入速度较快。 多线程场景下如何使用 ArrayList? ArrayList 不是线程安全的,如果遇到多线程场景,可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样: 为什么 ArrayList 的 elementData 加上 transient 修饰? ArrayList 中的数组定义如下: private transient Object[] elementData; 再看一下 ArrayList 的定义: public class ArrayList extends AbstractList implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 Serializable 接口,这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化,重写了 writeObject 实现: 每次序列化时,先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素,这样既加快了序列化的速度,又减小了序列化之后的文件大小。 List 和 Set 的区别 List , Set 都是继承自Collection 接口 List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。 Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。 另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。 Set和List对比 Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。 List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变 Set接口 说一下 HashSet 的实现原理? HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值。 HashSet如何检查重复?HashSet是如何保证数据不可重复的? 向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。 HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。 以下是HashSet 部分源码: hashCode()与equals()的相关规定: 如果两个对象相等,则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true 两个对象有相同的hashcode值,它们也不一定是相等的 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。 ** ==与equals的区别** ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同 ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值是否相同 HashSet与HashMap的区别 Queue BlockingQueue是什么? Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。 在 Queue 中 poll()和 remove()有什么区别? 相同点:都是返回第一个元素,并在队列中删除返回的对象。 不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。 代码示例: Queue queue = new LinkedList (); queue. offer("string"); // add System. out. println(queue. poll()); System. out. println(queue. remove()); System. out. println(queue. size()); Map接口 说一下 HashMap 的实现原理? HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。 HashMap 基于 Hash 算法实现的 当我们往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。 需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn) HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做拉链法的方式可以解决哈希冲突。 JDK1.8之前 JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 JDK1.8之后 相比于之前的版本,jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。 JDK1.7 VS JDK1.8 比较 JDK1.8主要解决或优化了一下问题: resize 扩容优化引入了红黑树,目的是避免单条链表过长而影响查询效率,红黑树算法请参考解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题。 HashMap的put方法的具体流程? 当我们put的时候,首先计算 key的hash值,这里调用了 hash方法,hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以 hash 函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞。按照函数注释,因为bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash,如果不做 hash 处理,相当于散列生效的只有几个低 bit 位,为了减少散列的碰撞,设计者综合考虑了速度、作用、质量之后,使用高16bit和低16bit异或来简单处理减少碰撞,而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。 putVal方法执行流程图 ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容; ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③; ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals; ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤; ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可; ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。 HashMap的扩容操作是怎么实现的? ①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容; ②.每次扩展的时候,都是扩展2倍; ③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。 在putVal()中,我们看到在这个函数里面使用到了2次resize()方法,resize()方法表示的在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上 HashMap是怎么解决哈希冲突的? 答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行; 什么是哈希? Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 所有散列函数都有如下一个基本特性**:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同**。 什么是哈希冲突? 当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。 HashMap的数据结构 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突: 这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化 hash()函数 上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下: static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或) } 这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动); JDK1.8新增红黑树 通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn); 总结 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的: 使用链地址法(使用散列表)来链接拥有相同hash值的数据;使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;引入红黑树进一步降低遍历的时间复杂度,使得遍历更快; **能否使用任何类作为 Map 的 key? **可以使用任何类作为 Map 的 key,然而在使用之前,需要考虑以下几点: 如果类重写了 equals() 方法,也应该重写 hashCode() 方法。 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。 如果一个类没有使用 equals(),不应该在 hashCode() 中使用它。 用户自定义 Key 类最佳实践是使之为不可变的,这样 hashCode() 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变,这样就会解决与可变相关的问题了。 为什么HashMap中String、Integer这样的包装类适合作为K? 答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况 内部已重写了equals()、hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况; 如果使用Object作为HashMap的Key,应该怎么办呢? 答:重写hashCode()和equals()方法 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞; 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性; HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标 答:hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置; 那怎么解决呢? HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均; 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题; HashMap 的长度为什么是2的幂次方 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢? 我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。 那为什么是两次扰动呢? 答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的; HashMap 与 HashTable 有什么区别? 线程安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!); 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它; 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛NullPointerException。 **初始容量大小和每次扩充容量大小的不同 **: ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。 推荐使用:在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap 替代。 如何决定使用 HashMap 还是 TreeMap? 对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。 HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。) HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。 ConcurrentHashMap 和 Hashtable 的区别? ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的; 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。 两者的对比图: HashTable: JDK1.7的ConcurrentHashMap: JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点): 答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 底层具体实现知道吗?实现原理是什么? JDK1.7 首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。 在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下: 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。 JDK1.8 在JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。 结构如下: 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount; 辅助工具类 Array 和 ArrayList 有何区别? Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。 如何实现 Array 和 List 之间的转换? Array 转 List: Arrays. asList(array) ;List 转 Array:List 的 toArray() 方法。 comparable 和 comparator的区别? comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序comparator接口实际上是出自 java.util 包,它有一个compare(Object obj1, Object obj2)方法用来排序 一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的Collections.sort(). 方法如何比较元素? TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。 Collections 工具类的 sort 方法有两种重载的形式, 第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较; 第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java 中对函数式编程的支持)。
剑曼红尘 2020-03-24 14:41:57 0 浏览量 回答数 0

回答

1.内存泄漏:基础 对于初学者来说,将内存泄漏视为一种疾病,将Java的OutOfMemoryError(简称OOM)视为一种症状。但与任何疾病一样,并非所有OOM都意味着内存泄漏:由于生成大量局部变量或其他此类事件,OOM可能会发生。另一方面,并非所有内存泄漏都必然表现为OOM,特别是在桌面应用程序或客户端应用程序(没有重新启动时运行很长时间)的情况下。 将内存泄漏视为疾病,将OutOfMemoryError视为症状。但并非所有OutOfMemoryErrors都意味着内存泄漏,并非所有内存泄漏都表现为OutOfMemoryErrors。 为什么这些泄漏如此糟糕?除此之外,程序执行期间泄漏的内存块通常会降低系统性能,因为分配但未使用的内存块必须在系统耗尽空闲物理内存时进行换出。最终,程序甚至可能耗尽其可用的虚拟地址空间,从而导致OOM。 2.解密OutOfMemoryError 如上所述,OOM是内存泄漏的常见指示。实质上,当没有足够的空间来分配新对象时,会抛出错误。当垃圾收集器找不到必要的空间,并且堆不能进一步扩展,会多次尝试。因此,会出现错误以及堆栈跟踪。 诊断OOM的第一步是确定错误的实际含义。这听起来很清除,但答案并不总是那么清晰。例如:OOM是否是因为Java堆已满而出现,还是因为本机堆已满?为了帮助您回答这个问题,让我们分析一些可能的错误消息: java.lang.OutOfMemoryError: Java heap space java.lang.OutOfMemoryError: PermGen space java.lang.OutOfMemoryError: Requested array size exceeds VM limit java.lang.OutOfMemoryError: request bytes for . Out of swap space? java.lang.OutOfMemoryError: (Native method) 2.1.“Java heap space” 此错误消息不一定意味着内存泄漏。实际上,问题可能与配置问题一样简单。 例如,我负责分析一直产生这种类型的OutOfMemoryError的应用程序。经过一番调查后,我发现罪魁祸首是阵列实例化,因为需要太多的内存;在这种情况下,并不是应用程序的错,而是应用程序服务器依赖于默认的堆太小了。我通过调整JVM的内存参数解决了这个问题。 在其他情况下,特别是对于长期存在的应用程序,该消息可能表明我们无意中持有对象的引用,从而阻止垃圾收集器清理它们。这时Java语言等同于内存泄漏。 (注意:应用程序调用的API也可能无意中持有对象引用。) 这些“Java堆空间”OOM的另一个潜在来源是使用finalizers。如果类具有finalize方法,则在垃圾收集时该类型的对象不会被回收。而是在垃圾收集之后,稍后对象将排队等待最终确定。在Sun实现中,finalizers由守护线程执行。如果finalizers线程无法跟上finalization队列,那么Java堆可能会填满并且可能抛出OOM。 2.2.“PermGen space” 此错误消息表明永久代已满。永久代是存储类和方法对象的堆的区域。如果应用程序加载了大量类,则可能需要使用-XX:MaxPermSize选项增加永久代的大小。 Interned java.lang.String对象也存储在永久代中。 java.lang.String类维护一个字符串池。调用实习方法时,该方法检查池以查看是否存在等效字符串。如果是这样,它由实习方法返回;如果没有,则将字符串添加到池中。更准确地说,java.lang.String.intern方法返回一个字符串的规范表示;结果是对该字符串显示为文字时将返回的同一个类实例的引用。如果应用程序实例化大量字符串,则可能需要增加永久代的大小。 注意:您可以使用jmap -permgen命令打印与永久生成相关的统计信息,包括有关内部化String实例的信息。 2.3.“Requested array size exceeds VM limit” 此错误表示应用程序(或该应用程序使用的API)尝试分配大于堆大小的数组。例如,如果应用程序尝试分配512MB的数组但最大堆大小为256MB,则将抛出此错误消息的OOM。在大多数情况下,问题是配置问题或应用程序尝试分配海量数组时导致的错误。 2.4.“Request bytes for . Out of swap space?” 此消息似乎是一个OOM。但是,当本机堆的分配失败并且本机堆可能将被耗尽时,HotSpot VM会抛出此异常。消息中包括失败请求的大小(以字节为单位)以及内存请求的原因。在大多数情况下,是报告分配失败的源模块的名称。 如果抛出此类型的OOM,则可能需要在操作系统上使用故障排除实用程序来进一步诊断问题。在某些情况下,问题甚至可能与应用程序无关。例如,您可能会在以下情况下看到此错误: 操作系统配置的交换空间不足。 系统上的另一个进程是消耗所有可用的内存资源。 由于本机泄漏,应用程序也可能失败(例如,如果某些应用程序或库代码不断分配内存但无法将其释放到操作系统)。 2.5. (Native method) 如果您看到此错误消息并且堆栈跟踪的顶部框架是本机方法,则该本机方法遇到分配失败。此消息与上一个消息之间的区别在于,在JNI或本机方法中检测到Java内存分配失败,而不是在Java VM代码中检测到。 如果抛出此类型的OOM,您可能需要在操作系统上使用实用程序来进一步诊断问题。 2.6.Application Crash Without OOM 有时,应用程序可能会在从本机堆分配失败后很快崩溃。如果您运行的本机代码不检查内存分配函数返回的错误,则会发生这种情况。 例如,如果没有可用内存,malloc系统调用将返回NULL。如果未检查malloc的返回,则应用程序在尝试访问无效的内存位置时可能会崩溃。根据具体情况,可能很难定位此类问题。 在某些情况下,致命错误日志或崩溃转储的信息就足以诊断问题。如果确定崩溃的原因是某些内存分配中缺少错误处理,那么您必须找到所述分配失败的原因。与任何其他本机堆问题一样,系统可能配置了但交换空间不足,另一个进程可能正在消耗所有可用内存资源等。 3.泄漏诊断 在大多数情况下,诊断内存泄漏需要非常详细地了解相关应用程序。警告:该过程可能很长并且是迭代的。 我们寻找内存泄漏的策略将相对简单: 识别症状 启用详细垃圾回收 启用分析 分析踪迹 3.1 识别症状 正如所讨论的,在许多情况下,Java进程最终会抛出一个OOM运行时异常,这是一个明确的指示,表明您的内存资源已经耗尽。在这种情况下,您需要区分正常的内存耗尽和泄漏。分析OOM的消息并尝试根据上面提供的讨论找到罪魁祸首。 通常,如果Java应用程序请求的存储空间超过运行时堆提供的存储空间,则可能是由于设计不佳导致的。例如,如果应用程序创建映像的多个副本或将文件加载到数组中,则当映像或文件非常大时,它将耗尽存储空间。这是正常的资源耗尽。该应用程序按设计工作(虽然这种设计显然是愚蠢的)。 但是,如果应用程序在处理相同类型的数据时稳定地增加其内存利用率,则可能会发生内存泄漏。 3.2 启用详细垃圾收集 断言确实存在内存泄漏的最快方法之一是启用详细垃圾回收。通常可以通过检查verbosegc输出中的模式来识别内存约束问题。 具体来说,-verbosegc参数允许您在每次垃圾收集(GC)过程开始时生成跟踪。也就是说,当内存被垃圾收集时,摘要报告会打印到标准错误,让您了解内存的管理方式。 这是使用-verbosegc选项生成的一些典型输出: image 此GC跟踪文件中的每个块(或节)按递增顺序编号。要理解这种跟踪,您应该查看连续的分配失败节,并查找随着时间的推移而减少的释放内存(字节和百分比),同时总内存(此处,19725304)正在增加。这些是内存耗尽的典型迹象。 3.3 启用分析 不同的JVM提供了生成跟踪文件以反映堆活动的不同方法,这些方法通常包括有关对象类型和大小的详细信息。这称为分析堆。 3.4 分析路径 本文重点介绍Java VisualVM生成的跟踪。跟踪可以有不同的格式,因为它们可以由不同的Java内存泄漏检测工具生成,但它们背后的想法总是相同的:在堆中找到不应该存在的对象块,并确定这些对象是否累积而不是释放。特别感兴趣的是每次在Java应用程序中触发某个事件时已知的临时对象。应该仅存少量,但存在许多对象实例,通常表示应用程序出现错误。 最后,解决内存泄漏需要您彻底检查代码。了解对象泄漏的类型可能对此非常有用,并且可以大大加快调试速度。 4.垃圾收集如何在JVM中运行? 在我们开始分析具有内存泄漏问题的应用程序之前,让我们首先看看垃圾收集在JVM中的工作原理。 JVM使用一种称为跟踪收集器的垃圾收集器,它基本上通过暂停它周围的世界来操作,标记所有根对象(由运行线程直接引用的对象),并遵循它们的引用,标记它沿途看到的每个对象。 Java基于分代假设-实现了一种称为分代垃圾收集器的东西,该假设表明创建的大多数对象被快速丢弃,而未快速收集的对象可能会存在一段时间。 基于此假设,[Java将对象分为多代](www.oracle.com/technetwork…. Generations|outline)。这是一个视觉解释: image Young Generation -这是对象的开始。它有两个子代 Eden Space -对象从这里开始。大多数物体都是在Eden Space中创造和销毁的。在这里,GC执行Minor GCs,这是优化的垃圾收集。执行Minor GC时,对仍然需要的对象的任何引用都将迁移到其中一个survivors空间(S0或S1)。 Survivor Space (S0 and S1)-幸存Eden Space的对象最终来到这里。其中有两个,在任何给定时间只有一个正在使用(除非我们有严重的内存泄漏)。一个被指定为空,另一个被指定为活动,与每个GC循环交替。 Tenured Generation -也被称为老年代(图2中的旧空间),这个空间容纳存活较长的对象,使用寿命更长(如果它们活得足够长,则从Survivor空间移过来)。填充此空间时,GC会执行完整GC,这会在性能方面降低成本。如果此空间无限制地增长,则JVM将抛出OutOfMemoryError - Java堆空间。 Permanent Generation -作为与终身代密切相关的第三代,永久代是特殊的,因为它保存虚拟机所需的数据,以描述在Java语言级别上没有等价的对象。例如,描述类和方法的对象存储在永久代中。 Java足够聪明,可以为每一代应用不同的垃圾收集方法。使用名为Parallel New Collector的跟踪复制收集器处理年轻代。这个收集器阻止了这个世界,但由于年轻一代通常很小,所以暂停很短暂。 有关JVM代及其工作原理的更多信息,请查阅Memory Management in the Java HotSpot™ Virtual Machine 。 5 检测内存泄漏 要查找内存泄漏并消除它们,您需要合适的内存泄漏工具。是时候使用Java VisualVM检测并删除此类泄漏。 5.1 使用Java VisualVM远程分析堆 VisualVM是一种工具,它提供了一个可视化界面,用于查看有关基于Java技术的应用程序运行时的详细信息。 使用VisualVM,您可以查看与本地应用程序和远程主机上运行的应用程序相关的数据。您还可以捕获有关JVM软件实例的数据,并将数据保存到本地系统。 为了从Java VisualVM的所有功能中受益,您应该运行Java平台标准版(Java SE)版本6或更高版本。 Related: Why You Need to Upgrade to Java 8 Already 5.2. 为JVM启用远程连接 在生产环境中,通常很难访问运行代码的实际机器。幸运的是,我们可以远程分析我们的Java应用程序。 首先,我们需要在目标机器上授予自己JVM访问权限。为此,请使用以下内容创建名为jstatd.all.policy的文件: grant codebase "file:${java.home}/../lib/tools.jar" { permission java.security.AllPermission;
游客2q7uranxketok 2021-02-22 19:58:44 0 浏览量 回答数 0

问题

该来的终于来了:“第一起”基于 IPv6 的 DDoS 攻击

作者介绍 杨彪,蚂蚁金服技术专家,《分布式服务架构:原理、设计与实战》和《可伸缩服务架构:框架与中间件》作者。近10年互联网和游戏行业工作经验,曾在酷我音乐盒、人人游戏...
驻云科技 2019-12-01 21:44:35 4186 浏览量 回答数 1

回答

浅谈Flutter框架原理及其生态圈 Flutter的锋芒 跨平台高性能的渲染引擎逐渐成为移动端、大前端领域的一个热点,作为其中的明星框架Flutter,经过近几年来的迅速发展,由极大的可能成为下一代跨端终端解决方案。自从2017 年 5 月,谷歌公司发布的了 Alpha 版本的 Flutter; 2018 年底 Flutter Live 发布的 1.0 版本;2019年7月发布1.5版本,截止今日(2020年2月)已经发布了v1.14.6 Beta版本。 在Flutter诞生之前,已经有许多跨平台UI框架的方案如Cordova、ReactNative、weex、uni-app、Hippy等,常见的需要处理兼容的终端平台也包括android、ios、web、Iot等,但是在大前端的浪潮下,对于企业和开发者来说开发效率和使用体验都十分重要,传统的做法莫过于分不同的团队开发不同的终端项目,如果还要继续向其他平台,拓展的话,我们需要付出的成本和时间将成倍增长。正因为如此,在这样的背景下,Flutter等跨端框架的兴起,从本质上讲,帮助开发者增加业务代码的复用率,减少因为要适配多个平台带来的工作量,从而降低开发成本、提高开发效率。 纵观已有的跨端方案,可以分为三类:Web 容器、泛 Web 容器、自绘引擎框架。 基于web容器即基于浏览器的跨平台也做得越来越好,自然管线也越来越短,与native的一些技术手段来实现性能上的相互补充。比如Egret、Cocos、Laya这些游戏引擎,它们在跨平台方面的做法多以Typescript编写,在iOS和安卓平台的各种浏览器中轻松的运行HTML5游戏,并在不同平台浏览器里提供近乎一致的用户体验,比如Egret还会提供高效的 JS-C Binding 编译机制,以满足游戏编译为原生格式的需求,不过大多数HTML游戏引擎也属于web容器这个范畴内。web容器框架也有一个明显的致命(在对体验&性能有较高要求的情况下)的缺点,那就是WebView的渲染效率和JavaScript执行性能太差。再加上Android各个系统版本和设备厂商的定制,很难保证所在所有设备上都能提供一致的体验。 泛 Web 容器框架比如ReactNative和Weex,即上层通过面向前端友好的UI,下层通过native的渲染形式,虽然同样使用类HTML+JS的UI构建逻辑,但是最终会生成对应的自定义原生控件,以充分利用原生控件相对于WebView的较高的绘制效率,同时H5与native相互补充来达到更好的用户体验,这也是一种很好的解决方案。缺陷也很明显,随着系统版本变化和API的变化,开发者可能也需要处理不同平台的差异,甚至有些特性只能在部分平台上实现,这样框架的跨平台特性就会大打折扣。 自绘引擎框架这里专指Flutter框架,从底层就承担跨端的任务和渲染方式,从目前来看,从技术的实现和方案的成熟度、产品的性能方面比较,Flutter有很大可能成为下一代主流跨平台框架。 Flutter与其他跨端框架的不同点之一就是自带渲染引擎,Flutter渲染引擎依靠跨平台的Skia图形库来实现,Skia引擎会将使用Dart语言构建的抽象的视图结构数据加工成GPU数据,交由 OpenGL 最终提供给 GPU 渲染,至此完成渲染闭环,因此可以在最大程度上保证一款应用在不同平台、不同设备上的体验一致性。 而开发语言选用的是同时支持 JIT和 AOT的 Dart语言,Dart本身提供了三种运行方式,应对web环境,用Dart2js编译成JavaScript代码,运行在常规浏览器中;使用DartVM直接在命令行中运行Dart代码;AOT方式编译成机器码,例如Flutter App框架。而且Dart 避免了抢占式调度和共享内存,可以在没有锁的情况下进行对象分配和垃圾回收,在性能方面表现相当不错,不仅保证了开发效率,代码性能和用户体验也更卓越。因此,Flutter在各类跨平台移动开发方案中脱颖而出。同时在去年2019的Google IO大会上,备受关注的Fuchsia系统虽然并没有发布,但是宣布了 Flutter除了支持开发 Android 和 iOS 程序之外,现在还支持开发Web程序了,在 I/O 大会上,谷歌发布了 Web 版 Flutter 的首个技术预览版,宣布 Flutter 将为包括 Google Home Hub 在内的 Google Smart Display 平台提供技术支持,并迈出利用 Chrome 操作系统支持桌面级应用的第一步。 很多JS开发者会思考Google Flutter团队至于为啥选择Dart而不是JS,其实Google 公司给出的原因很简单也很直接:Dart 语言开发组就在隔壁,对于 Flutter 需要的一些语言新特性,能够快速在语法层面落地实现;而如果选择了 JavaScript,就必须经过各种委员会(TC39等)和浏览器提供商漫长的决议。 Flutter绘制原理 在计算机系统中,图像的显示需要 CPU、GPU 和显示器一起配合完成:CPU 负责图像数据计算,GPU 负责图像数据渲染,而显示器则负责最终图像显示。 CPU 把计算好的、需要显示的内容交给 GPU,由 GPU 完成渲染后放入帧缓冲区,随后视频控制器根据垂直同步信号(VSync)以每秒 60 次的速度,从帧缓冲区读取帧数据交由显示器完成图像显示。 操作系统在呈现图像时遵循了这种机制,而 Flutter 作为跨平台开发框架也采用了这种底层方案。下面有一张更为详尽的示意图来解释 Flutter 的绘制原理。可以看到,Flutter 关注如何尽可能快地在两个硬件时钟的 VSync 信号之间计算并合成视图数据,然后通过 Skia 交给 GPU 渲染:UI 线程使用 Dart 来构建视图结构数据,这些数据会在 GPU 线程进行图层合成,随后交给 Skia 引擎加工成 GPU 数据,而这些数据会通过 OpenGL 最终提供给 GPU 渲染。 Skia原理 Skia 是一款用由C++ 开发的2D 图像绘制引擎。在2005 年被 Google 公司收购后被广泛应用在 Android和其他等核心产品上,Skia 目前是Android 官方的图像渲染引擎,因此 Flutter Android SDK 无需内嵌 Skia 引擎就可以获得天然的 Skia 支持;而对于 iOS 平台来说,由于 Skia 是跨平台的,因此它作为 Flutter iOS 渲染引擎被嵌入到 Flutter 的 iOS SDK 中,替代了 iOS 闭源的 Core Graphics/Core Animation/Core Text,这也正是 Flutter iOS SDK 打包的 App 包体积比 Android 要大一些的原因。 底层渲染能力统一了,上层开发接口和功能体验也就随即统一了,开发者再也不用操心平台相关的渲染特性了。也就是说,Skia 保证了同一套代码调用在 Android 和 iOS 平台上的渲染效果是完全一致的。 Flutter架构 Framework底层是Flutter引擎,引擎主要负责图形绘制(Skia)、文字排版(libtxt)和提供Dart运行时,引擎全部使用C++实现,Framework层使我们可以用Dart语言调用引擎的强大能力。Flutter 架构采用分层设计,从下到上分为三层,依次为:Embedder、Engine、Framework。 Embedder 是操作系统适配层,实现了渲染 Surface 设置,线程设置,以及平台插件等平台相关特性的适配。从这里我们可以看到,Flutter 平台相关特性并不多,这就使得从框架层面保持跨端一致性的成本相对较低。 Engine 层主要包含 Skia、Dart 和 Text,实现了 Flutter 的渲染引擎、文字排版、事件处理和 Dart 运行时等功能。Skia 和 Text 为上层接口提供了调用底层渲染和排版的能力,Dart 则为 Flutter 提供了运行时调用 Dart 和渲染引擎的能力。而 Engine 层的作用,则是将它们组合起来,从它们生成的数据中实现视图渲染。 Framework 层则是一个用 Dart 实现的 UI SDK,包含了动画、图形绘制和手势识别等功能。为了在绘制控件等固定样式的图形时提供更直观、更方便的接口,Flutter 还基于这些基础能力,根据 Material 和 Cupertino 两种视觉设计风格封装了一套 UI 组件库,开发者可以直接使用这些组件库。 Flutter运行流程 页面中的各界面元素(Widget)以树的形式组织,即控件树。Flutter 通过控件树中的每个控件创建不同类型的渲染对象,组成渲染对象树。在Flutter界面渲染过程分为三个阶段:布局、绘制、合成,布局和绘制在Flutter框架中完成,合成则交由引擎负责。 Flutter 采用深度优先机制遍历渲染对象树,决定渲染对象树中各渲染对象在屏幕上的位置和尺寸。在布局过程中,渲染对象树中的每个渲染对象都会接收父对象的布局约束参数,决定自己的大小,然后父对象按照控件逻辑决定各个子对象的位置,最终完成布局过程。这里只需要注意一点,无论布局还是绘制,都是父子间的遍历关系:父Widget的布局需要依赖子Widget的布局结果;而绘制则反过来(子Widget需要盖在父Widget上),布局是后续遍历,绘制是前序遍历,他们都是深度优先遍历。 Flutter生命周期 可以看到,Flutter中State 的生命周期可以分为 3 个阶段:创建(插入视图树)、更新(在视图树中存在)、销毁(从视图树中移除)。接下来,我们一起看看每一个阶段的具体流程。 第一步创建 State 初始化时会依次执行 :构造方法 -> initState -> didChangeDependencies -> build,随后完成页面渲染。构造方法是 State 生命周期的起点,Flutter 会通过调用StatefulWidget.createState() 来创建一个 State。我们可以通过构造方法,来接收父 Widget 传递的初始化 UI 配置数据。这些配置数据,决定了 Widget 最初的呈现效果。 initState,会在 State 对象被插入视图树的时候调用。这个函数在 State 的生命周期中只会被调用一次,所以我们可以在这里做一些初始化工作,比如为状态变量设定默认值。 didChangeDependencies 则用来专门处理 State 对象依赖关系变化,会在 initState() 调用结束后,被 Flutter 调用。 build,作用是构建视图。经过以上步骤,Framework 认为 State 已经准备好了,于是调用 build。我们需要在这个函数中,根据父 Widget 传递过来的初始化配置数据,以及 State 的当前状态,创建一个 Widget 然后返回。 第二步更新 Widget 的状态更新,主要由个方法触发:setState、didchangeDependencies、didUpdateWidget。 setState:我们最熟悉的方法之一。当状态数据发生变化时,我们总是通过调用这个方法告诉 Flutter:“我这儿的数据变啦,请使用更新后的数据重建 UI!” didChangeDependencies:State 对象的依赖关系发生变化后,Flutter 会回调这个方法,随后触发组件构建。哪些情况下 State 对象的依赖关系会发生变化呢?典型的场景是,系统语言 Locale 或应用主题改变时,系统会通知 State 执行 didChangeDependencies 回调方法。 didUpdateWidget:当 Widget 的配置发生变化时,比如,父 Widget 触发重建(即父 Widget 的状态发生变化时),热重载时,系统会调用这个函数。一旦这三个方法被调用,Flutter 随后就会销毁老 Widget,并调用 build 方法重建 Widget。 第三步销毁 比如组件被移除,或是页面销毁的时候,系统会调用 deactivate 和 dispose 这两个方法,来移除或销毁组件。 Flutter生态圈及其常用框架 一项技术一个框架是否流行,最直观的体现就是它的生态圈是否活跃,下面列举了一些Flutter开发中常用的库工具。 参考文献 1、[Flutter原理与实践](https://tech.meituan.com/2018/08/09/waimai-flutter-practice.html) 少杰 2、[Flutter框架技术概览](https://flutter.dev/docs/resources/technical-overview) 3、[Flutter中文官网](https://pub.dartlang.org/flutter/) 4、[Flutter插件仓库](https://pub.dev/flutter/packages)
罗思雨 2020-02-27 11:47:50 0 浏览量 回答数 0

回答

一、简单排序算法   由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境   下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么   问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。 1.冒泡法:   这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:   #include <iostream>   using namespace std;   void BubbleSort(int * pData, int Count)   {   int iTemp;   for (int i=0; i<Count; i++)   {   for (int j=Count-1; j>i; j--)   {   if (pData[j]<pData[j-1])   {   iTemp = pData[j-1];   pData[j-1] = pData[j];   pData[j] = iTemp;   }   }   }   }   void main()   {   int data[7] = {10,9,8,7,6,5,4};   BubbleSort(data,7);   for (int i=0; i<7; i++)   {   cout<<data[i]<<" ";   }   cout<<endl;   system("PAUSE");   }   倒序(最糟情况)   第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)   第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:6次   其他:   第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)   第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:3次   上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换,   显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。   写成公式就是1/2*(n-1)*n。   现在注意,我们给出O方法的定义:   若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没学好数学呀,对于编程数学是非常重要的。。。)   现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)   =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。   再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的   有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),   复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的   原因,我们通常都是通过循环次数来对比算法。 2.交换法:   交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。   #include <iostream.h>   void ExchangeSort(int* pData,int Count)   {   int iTemp;   for(int i=0;i<Count-1;i++)   { //共(count-1)轮,每轮得到一个最小值   for(int j=i+1;j<Count;j++)   { //每次从剩下的数字中寻找最小值,于当前最小值相比,如果小则交换   if(pData[j]9,10,8,7->8,10,9,7->7,10,9,8(交换3次)   第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:6次   其他:   第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)   第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次)   第一轮:7,8,10,9->7,8,9,10(交换1次)   循环次数:6次   交换次数:3次   从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样   也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以   只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。 3.选择法:   现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)   这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中   选择最小的与第二个交换,这样往复下去。   #include <iostream.h>   void SelectSort(int* pData,int Count)   {   int iTemp;   int iPos;   for(int i=0;i<Count-1;i++)   {   iTemp = pData;   iPos = i;   for(int j=i+1;j<Count;j++)   {   if(pData[j]<iTemp)   {   iTemp = pData[j];   iPos = j;   }   }   pData[iPos] = pData;   pData = iTemp;   }   }   void main()   {   int data[] = {10,9,8,7,6,5,4};   SelectSort(data,7);   for (int i=0;i<7;i++)   cout<<data<<" ";   cout<<"\n";   }   倒序(最糟情况)   第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)   第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)   第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次)   循环次数:6次   交换次数:2次   其他:   第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)   第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)   第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次)   循环次数:6次   交换次数:3次   遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。   我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n   所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。 4.插入法:   插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张   #include <iostream.h>   void InsertSort(int* pData,int Count)   {   int iTemp;   int iPos;   for(int i=1;i<Count;i++)   {   iTemp = pData[i]; //保存要插入的数   iPos = i-1; //被插入的数组数字个数   while((iPos>=0) && (iTemp9,10,8,7(交换1次)(循环1次)   第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次)   第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次)   循环次数:6次   交换次数:3次   其他:   第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次)   第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次)   第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次)   循环次数:4次   交换次数:2次   上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是,   因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<=   1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单   排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似   选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’   而这里显然多了一些,所以我们浪费了时间。   最终,我个人认为,在简单排序算法中,选择法是最好的。 二、高级排序算法   高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。   它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后   把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使   用这个过程(最容易的方法——递归)。   1.快速排序:   #include <iostream.h>   void run(int* pData,int left,int right)   {   int i,j;   int middle,iTemp;   i = left;   j = right;   middle = pData[left];   do{   while((pData[i]<middle) && (i<right))//从左扫描大于中值的数   i++;    while((pData[j]>middle) && (j>left))//从右扫描大于中值的数   j--;   if(i<=j)//找到了一对值   {   //交换   iTemp = pData[i];   pData[i] = pData[j];   pData[j] = iTemp;   i++;   j--;   }   }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)   //当左边部分有值(left<j),递归左半边   if(left<j)   run(pData,left,j);   //当右边部分有值(right>i),递归右半边   if(right>i)   run(pData,i,right);   }   void QuickSort(int* pData,int Count)   {   run(pData,0,Count-1);   }   void main()   {   int data[] = {10,9,8,7,6,5,4};   QuickSort(data,7);   for (int i=0;i<7;i++)   cout<<data<<" ";   cout<<"\n";   }   这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况   1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。   2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。   第一层递归,循环n次,第二层循环2*(n/2)......   所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n   所以算法复杂度为O(log2(n)*n)   其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变   成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大。。呵呵,你完全   不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。   如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢
知与谁同 2019-12-02 01:18:20 0 浏览量 回答数 0

问题

【精品问答】python技术1000问(1)

为了方便python开发者快速找到相关技术问题和答案,开发者社区策划了python技术1000问内容,包含最基础的如何学python、实践中遇到的技术问题、python面试等维度内容。 我们会以每天至少50条的...
问问小秘 2019-12-01 21:57:48 456417 浏览量 回答数 22

问题

不搞清这8大算法思想,刷再多题效果也不好的 7月23日 【今日算法】

算法和数据结构一直以来都是程序员的基本内功,可以说没有数据结构的基础建设和算法加持,也就没有这将近八十年的信息革命时代。数据结构可以看作是算法实现的容器,通过一系列特殊结构的数据集合,...
游客ih62co2qqq5ww 2020-07-29 11:10:09 3 浏览量 回答数 1

回答

排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将给出详细的说明。 对于排序的算法我想先做一点简单的介绍,也是给这篇文章理一个提纲。 我将按照算法的复杂度,从简单到难来分析算法。 第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念,所以这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的(甚至有最慢的),但是算法本身比较奇特,值得参考(编程的角度)。同时也可以让我们从另外的角度来认识这个问题。 第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序(抱歉,里面使用了一些论坛专家的呢称)。 现在,让我们开始吧: 一、简单排序算法 由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境 下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么 问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。 1.冒泡法: 这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡: #include <iostream.h> void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i<Count;i++) { for(int j=Count-1;j>=i;j--) { if(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[j-1] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; BubbleSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次) 第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换, 显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。 写成公式就是1/2*(n-1)*n。 现在注意,我们给出O方法的定义: 若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没 学好数学呀,对于编程数学是非常重要的。。。) 现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。 再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因,我们通常都是通过循环次数来对比算法。 2.交换法: 交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。 #include <iostream.h> void ExchangeSort(int* pData,int Count) { int iTemp; for(int i=0;i<Count-1;i++) { for(int j=i+1;j<Count;j++) { if(pData[j]<pData[i]) { iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; } } } } void main() { int data[] = {10,9,8,7,6,5,4}; ExchangeSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次) 第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:6次 其他: 第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次) 第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次) 第一轮:7,8,10,9->7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。 3.选择法: 现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中选择最小的与第二个交换,这样往复下去。 #include <iostream.h> void SelectSort(int* pData,int Count) { int iTemp; int iPos; for(int i=0;i<Count-1;i++) { iTemp = pData[i]; iPos = i; for(int j=i+1;j<Count;j++) { if(pData[j]<iTemp) { iTemp = pData[j]; iPos = j; } } pData[iPos] = pData[i]; pData[i] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; SelectSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次) 第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次) 第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次) 循环次数:6次 交换次数:2次 其他: 第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次) 第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次) 第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次) 循环次数:6次 交换次数:3次 遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。 我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n 所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。 4.插入法: 插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张 #include <iostream.h> void InsertSort(int* pData,int Count) { int iTemp; int iPos; for(int i=1;i<Count;i++) { iTemp = pData[i]; iPos = i-1; while((iPos>=0) && (iTemp<pData[iPos])) { pData[iPos+1] = pData[iPos]; iPos--; } pData[iPos+1] = iTemp; } } void main() { int data[] = {10,9,8,7,6,5,4}; InsertSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 倒序(最糟情况) 第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次) 第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次) 第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次) 循环次数:6次 交换次数:3次 其他: 第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次) 第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次) 第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次) 循环次数:4次 交换次数:2次 上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是, 因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单 排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似 选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’ 而这里显然多了一些,所以我们浪费了时间。 最终,我个人认为,在简单排序算法中,选择法是最好的。 二、高级排序算法: 高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。 它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后 把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使 用这个过程(最容易的方法——递归)。 1.快速排序: #include <iostream.h> void run(int* pData,int left,int right) { int i,j; int middle,iTemp; i = left; j = right; middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } void QuickSort(int* pData,int Count) { run(pData,0,Count-1); } void main() { int data[] = {10,9,8,7,6,5,4}; QuickSort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况 1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。 2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。 第一层递归,循环n次,第二层循环2*(n/2)...... 所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n 所以算法复杂度为O(log2(n)*n) 其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变 成交换法(由于使用了递归,情况更糟)。但是你认为这种情况发生的几率有多大。。呵呵,你完全 不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。 如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢于快速排序(因为要重组堆)。 三、其他排序 1.双向冒泡: 通常的冒泡是单向的,而这里是双向的,也就是说还要进行反向的工作。 代码看起来复杂,仔细理一下就明白了,是一个来回震荡的方式。 写这段代码的作者认为这样可以在冒泡的基础上减少一些交换(我不这么认为,也许我错了)。 反正我认为这是一段有趣的代码,值得一看。 #include <iostream.h> void Bubble2Sort(int* pData,int Count) { int iTemp; int left = 1; int right =Count -1; int t; do { //正向的部分 for(int i=right;i>=left;i--) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } left = t+1; //反向的部分 for(i=left;i<right+1;i++) { if(pData[i]<pData[i-1]) { iTemp = pData[i]; pData[i] = pData[i-1]; pData[i-1] = iTemp; t = i; } } right = t-1; }while(left<=right); } void main() { int data[] = {10,9,8,7,6,5,4}; Bubble2Sort(data,7); for (int i=0;i<7;i++) cout<<data[i]<<" "; cout<<"\n"; } 2.SHELL排序 这个排序非常复杂,看了程序就知道了。 首先需要一个递减的步长,这里我们使用的是9、5、3、1(最后的步长必须是1)。 工作原理是首先对相隔9-1个元素的所有内容排序,然后再使用同样的方法对相隔5-1个元素的排序 以次类推。 #include <iostream.h> void ShellSort(int* pData,int Count) { int step[4]; step[0] = 9; step[1] = 5; step[2] = 3; step[3] = 1; int iTemp; int k,s,w; for(int i=0;i<4;i++) { k = step[i]; s = -k; for(int j=k;j<Count;j++) { iTemp = pData[j]; w = j-k;//求上step个元素的下标 if(s ==0) { s = -k; s++; pData[s] = iTemp; } while((iTemp<pData[w]) && (w>=0) && (w<=Count)) { pData[w+k] = pData[w]; w = w-k; } pData[w+k] = iTemp; } } } void main() { int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1}; ShellSort(data,12); for (int i=0;i<12;i++) cout<<data[i]<<" "; cout<<"\n"; } 呵呵,程序看起来有些头疼。不过也不是很难,把s==0的块去掉就轻松多了,这里是避免使用0 步长造成程序异常而写的代码。这个代码我认为很值得一看。 这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法:“由于复杂的数学原因 避免使用2的幂次步长,它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并 “超出本书讨论范围”的原因(我也不知道过程),我们只有结果了。 四、基于模板的通用排序: 这个程序我想就没有分析的必要了,大家看一下就可以了。不明白可以在论坛上问。 MyData.h文件 /////////////////////////////////////////////////////// class CMyData { public: CMyData(int Index,char* strData); CMyData(); virtual ~CMyData(); int m_iIndex; int GetDataSize(){ return m_iDataSize; }; const char* GetData(){ return m_strDatamember; }; //这里重载了操作符: CMyData& operator =(CMyData &SrcData); bool operator <(CMyData& data ); bool operator >(CMyData& data ); private: char* m_strDatamember; int m_iDataSize; }; //////////////////////////////////////////////////////// MyData.cpp文件 //////////////////////////////////////////////////////// CMyData::CMyData(): m_iIndex(0), m_iDataSize(0), m_strDatamember(NULL) { } CMyData::~CMyData() { if(m_strDatamember != NULL) delete[] m_strDatamember; m_strDatamember = NULL; } CMyData::CMyData(int Index,char* strData): m_iIndex(Index), m_iDataSize(0), m_strDatamember(NULL) { m_iDataSize = strlen(strData); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,strData); } CMyData& CMyData::operator =(CMyData &SrcData) { m_iIndex = SrcData.m_iIndex; m_iDataSize = SrcData.GetDataSize(); m_strDatamember = new char[m_iDataSize+1]; strcpy(m_strDatamember,SrcData.GetData()); return *this; } bool CMyData::operator <(CMyData& data ) { return m_iIndex<data.m_iIndex; } bool CMyData::operator >(CMyData& data ) { return m_iIndex>data.m_iIndex; } /////////////////////////////////////////////////////////// ////////////////////////////////////////////////////////// //主程序部分 #include <iostream.h> #include "MyData.h" template <class T> void run(T* pData,int left,int right) { int i,j; T middle,iTemp; i = left; j = right; //下面的比较都调用我们重载的操作符函数 middle = pData[(left+right)/2]; //求中间值 do{ while((pData[i]<middle) && (i<right))//从左扫描大于中值的数 i++; while((pData[j]>middle) && (j>left))//从右扫描大于中值的数 j--; if(i<=j)//找到了一对值 { //交换 iTemp = pData[i]; pData[i] = pData[j]; pData[j] = iTemp; i++; j--; } }while(i<=j);//如果两边扫描的下标交错,就停止(完成一次) //当左边部分有值(left<j),递归左半边 if(left<j) run(pData,left,j); //当右边部分有值(right>i),递归右半边 if(right>i) run(pData,i,right); } template <class T> void QuickSort(T* pData,int Count) { run(pData,0,Count-1); } void main() { CMyData data[] = { CMyData(8,"xulion"), CMyData(7,"sanzoo"), CMyData(6,"wangjun"), CMyData(5,"VCKBASE"), CMyData(4,"jacky2000"), CMyData(3,"cwally"), CMyData(2,"VCUSER"), CMyData(1,"isdong") }; QuickSort(data,8); for (int i=0;i<8;i++) cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n"; cout<<"\n"; }
沉默术士 2019-12-02 01:19:06 0 浏览量 回答数 0

问题

【Java学习全家桶】1460道Java热门问题,阿里百位技术专家答疑解惑

阿里极客公益活动: 或许你挑灯夜战只为一道难题 或许你百思不解只求一个答案 或许你绞尽脑汁只因一种未知 那么他们来了,阿里系技术专家来云栖问答为你解答技术难题了 他们用户自己手中的技术来帮助用户成长 本次活动特邀百位阿里技术专家对Java常...
管理贝贝 2019-12-01 20:07:15 27612 浏览量 回答数 19

问题

【精品问答】Python二级考试题库

1.关于数据的存储结构,以下选项描述正确的是( D ) A: 数据所占的存储空间量 B: 存储在外存中的数据 C: 数据在计算机中的顺序存储方式 D: 数据的逻辑结构在计算机中的表示 2.关于线性...
珍宝珠 2019-12-01 22:03:38 7177 浏览量 回答数 3

云产品推荐

上海奇点人才服务相关的云产品 小程序定制 上海微企信息技术相关的云产品 国内短信套餐包 ECS云服务器安全配置相关的云产品 开发者问答 阿里云建站 自然场景识别相关的云产品 万网 小程序开发制作 视频内容分析 视频集锦 代理记账服务 阿里云AIoT