网站搭建图片,邢台中高风险地区,上海市建筑业官网,wordpress固定链接怎么设置亲爱的小屋客人#xff0c;昨天小夕将小屋的讨论室重新装修啦#xff01;希望您会喜欢哦~除了口令[d]#xff0c;现在也可以通过主页下方的“喵了个咪”进入讨论室啦。ps#xff1a;昨天小夕装修讨论室的时候发生了N次差点吐血的事件#xff0c;明天小夕与大家含泪分享T_T… 亲爱的小屋客人昨天小夕将小屋的讨论室重新装修啦希望您会喜欢哦~除了口令[d]现在也可以通过主页下方的“喵了个咪”进入讨论室啦。ps昨天小夕装修讨论室的时候发生了N次差点吐血的事件明天小夕与大家含泪分享T_T。在上一篇文章中小夕为大家讲解了链表与递增式扩容的姿势而这一篇将会是本系列文章的高潮哦不要污 源于数组上篇文章中小夕为了避免大家理解起来抽象让大家注意了几个数据结构如果您是C程序喵那么请注意一下Vector数据结构如果是Java程序喵请注意一下ArrayList、LinkedList、哈希系列(HashSet/ HashTable/ HashMap)如果是不用Java也不用C的程序喵或者是已经脱离XX编程语言层次的程序喵那么请注意一下可变数组可增长顺序表、链表、哈希散列。上篇文章中小夕讲解了基于链表实现的数据结构都是递增式扩容最优。那么对于C中的VectorJava中的ArrayList、HashSet/ HashTable/ HashMap也就是数据结构中的可变数组、哈希来说空间增长方式是怎样呢可能有可爱的读者宝宝此时在想“天呐这些数据结构又特喵的不一样怎么放到一起讨论了呢”好啦让小夕碾压这些读者宝宝吧小夕再次跑路其实这些表面看似不同的东西底层的实现方式确是一样的它们在底层都是通过操纵静态数组来实现他们的动态空间增长功能下文会详细介绍哦。讲到这里可能爱思考的读者宝宝会记得小夕在上一篇中也提到过哈希说哈希的横向增长是基于链表的因此递增式扩容是最优动态空间增长方案。那这一篇中又说哈希是基于静态数组的这是怎么回事呢下面给没有接触过哈希的读者宝宝先科普一下哈希哈希的横向增长是基于链表实现的即当新元素的哈希值与已有元素哈希值相同时新元素会插入到某个链表中因此是递增式增长。但是更多的情况下哈希是纵向增长的。学过数据结构的宝宝知道哈希在纵向上就是一个指针数组数组的每个索引值即代表一个哈希值数组的每个元素是一个指向某链表的指针。画个图来看就是这样的。所以在本篇文章中我们不看哈希的横向增长啦就看竖着的也就是纵向增长此时显然是基于静态数组实现的哦。下面小夕直接以“数据结构”代称所有这些基于静态数组实现的动态空间分配的数据结构包括但不限于C中的Vector即数据结构中的动态数组Java中的ArrayList即动态数组、Hash系列即哈希/散列等~具体来说如何用静态数组实现上述的动态空间增长的数据结构呢其实很简单每次数据结构要扩容时只需要依次进行下述操作就完成啦开辟一段新的内存空间空间大小就是扩容后的数据结构大小。把旧数据结构也就是旧的内存空间的元素一个个的复制到新的内存空间释放旧的内存空间代码上就是删除旧空间的指针当然像Java这种自动管理内存的语言就不用程序喵操心这一步了通过上述扩容的三步操作可以看到每次哈希表的扩容操作的代价还是挺大的。第1步和第3步的代价不算大但是第2步的代价会随着要搬移元素数量的增加而直线上升。所以这就相当于一个完整搬家的过程先买个新房子再把旧房子里的全部家当搬到新房子里去再把旧房子注销你说麻不麻烦喵ω加倍式扩容既然代价如此之大那么显然我们要尽量减小扩容次数呀~每次扩容都是大出血...怎么扩呢一个很creative的想法就是每次使数据结构变为自身的两倍再机智一点每次使数据结构变为自身的N倍其中N只要大于1就可以这种每次使自身的大小变为之前N倍的数据结构动态空间增长方式称为【加倍式扩容】。实际上在基于静态数组的数据结构的动态空间增长问题上加倍式扩容远远优于递增式扩容。口说无凭待小夕用萌味算法分析来证明假如数据结构A使用【递增式扩容】。每次数据结构满了的时候就固定的增加10个单位的空间增加单位的数量不会影响最终分析出来的复杂度哦。好那小夕现在手里有n个元素想添加进数据结构假如n的数值很大远远的大于10那么要执行多少次扩容操作呢当然是n/10次啦~这n/10次扩容的累计开销大约为cost102*103*10…(n/10)*10计算一下这个级数就是cost[(n/10)/2]*[(n/10)1]*10,所以复杂度是O(n2)的数量级所以平均每个元素被添加进哈希表时的开销为cost/n也就是O(n)的复杂度。 假如数据结构B使用【加倍式扩容】。每次数据结构满了的时候数据结构的大小就变成原来的2倍与之前同样的这个倍数取不同的值并不会影响最终分析出来的复杂度哦~当然倍数必须大于1。同样小夕将n个元素添加进数据结构假如n的数值很大远远的大于2那么要执行的扩容操作的次数是…小夕去算一会...嗯…应该是log2n令clog2n则这c次扩容操作的累计开销为cost2122…2c。这个级数的和为cost[2/(1-2)]*(1-2c)代入clog2n得cost2(n-1)。也就是说复杂度为O(n)所以平均每个元素被添加进哈希表时的开销为cost/n也就是O(1)的复杂度注意前面我们计算过这里数据结构A递增式扩容的复杂度为O(n)!怎么样~小夕说的没错吧读者宝宝有没有拨开云彩见到日呢(∇)。所以说呀正是因为这类数据结构采用了加倍式扩容导致这类数据结构申请内存的时候翻倍翻倍的要。结果当时在那个机器学习任务中小夕算的是一个超大哈希表只需要占用5个G作右的内存空间而实际上在往这个哈希表加数据时从4个G直接爆到了接近8个G导致小夕内存8G的小电脑直接崩盘了~等等看似此文可以结了实际上敏锐的读者宝宝可能想到了“递增式扩容你都告诉我了每次扩容增加一个单位的空间就最优了那加倍式扩容每次增大几倍最优呢”如果读者宝宝能发现这一点的话真的非常棒啦答案是2倍吗当然不那是几呢下篇萌货萌味干货的简称见分晓(∇)。啊啊高潮果然是最累的我说文章的高潮啊喂~小夕好累喵(´Д )。所以亲爱的读者宝宝是不是有一种抑制不住要鼓励小夕的冲动吖(⁎⁍̴̛ᴗ⁍̴̛⁎)小夕已委托维权骑士对小夕发布文章的版权行为进行追究与维权。如需转载请联系微信xiyaomengmengda。
