C高等数据结构与算法分析.ppt

Chapter 4 Lists and Arrays Revisited,1.Skip Lists 2.Multilists 3.Matrix Representations 4.Memory Management,A probabilistic data structure that can be used implement the dictionary ADT. The Skip List is comparable in complexity to the BST,yet often outperforms the BST since the Skip List s efficiency is not tied to the values of the dataset being stored.,Which are lists that may contain sublists.,Representations for implementing sparse matrices,large matrics where most of the elements have zero values.,Which are essentially a way of allocating variable-length sections from a large array.,1.Skip Lists,Skip Lists are designed to overcome a basic limitation of array-based and linked lists:Either search or update operations require linear time .顺序表和链表的基本问题：每一次检索或更新需要的时间都是线性的 The primary problem with the BST is that it may easily become unbalanced. BST的主要问题：容易变得不平衡 The 2-3 tree is guaranteed to remain balanced regardless of the order in which data values are inserted,but it is rather complicated to implement.2-3树保证不管数据值以什么顺序插入，都能保持平衡，但难以实现 The AVL tree and the splay tree,which are also guaranteed to provide good performance ,but at the cost of added complexity as compared to the BST. AVL树和伸展树都能保证提供好的性能（O（logn）（检索、插入、删除时间为O（logn）),但与BST树相比，也增加了额外的复杂性,1.Skip Lists 跳跃表,n个元素的有序表，采用折半查找所需时间复杂度为O（logn） 而对一个有序链表进行查找所需的时间复杂度为O（n） 对于有序链表时间复杂度如何由 O（n） O（logn）,？,Skip Lists,1.Skip Lists,在实现的难度和性能两方面进行了很好的折中,The Skip List is not guaranteed to provide good performance，but it will provide good performance with extremely high probability. 跳跃表不能保证提供好的性能，但提供好性能的概率极高 As such it represents a good compromise between difficulty of implementation and performance. 在实现难度和性能两方面进行了很好的权衡。,有序链表,跳跃表:,通过对有序表链表的全部或部分结点增加额外的指针， 来提高搜索性能,在查询时，通过这些指针来跳过链表中若干个结点，因此没必要从左到右搜索连表中的所有结点,最坏情况下比较次数为8次,最坏情况下比较次数为4次,1.Skip Lists,0 1 2,查找: key=30 在二级链中找，由于3024 故需在0级链中查找 key=77 与40比较7740，在一级链中与75比较,通常0级链包括n个元素，1级链包括n/2个元素，2级链包括n/4个元素。,当且仅当一个元素在0-i级链上，但不在i+1级链上时，我们称该元素定为i级链元素。如：40，95是2级链上唯一的元素，24，75是1级链元素，20，30，60，80是0 级元素。,插入，删除： 插入key=77 找到插入的位置 为新元素分配一个级，分配过程由随机数产生器完成 若新元素为i级链元素，则断开0i级链指针，插入。,级的分配： int randomlevel (void) /级按指数分布 for (int level=0;Random(2)=0;level+); return level; ,1.Skip Lists,2.Multilists 广义表,In Lists ,we assumed that all list ellements had the same data type. We extend the definition of lists to allow elements to be arbitrary in nature. In general,list elements are one of two types: 1.An atom,which is a data record of some type such as a number,symbol,or string. 2.Another list,which is called a sublist.,3.Matrix Representations,Some applications must represent a large,two-dimensional matrix where many of the elements have a value of zero. The lower triangular matrix The upper triangular matrix Sparse Matrix,a00 0 0 0 a10 a11 0 0 a20 a21 a22 0 a30 a31 a32 a33,a00 a01 a02 a03 0 a11 a12 a13 0 0 a22 a23 0 0 0 a33,4.Memory Management 对OS和Compiler来说，存储管理都定一个复杂而又重要的问题。不同的编译的OS系统可采用不同的存储管理方法。 用于处理变长空间请求 The basic model for memory management is that we have a (large)block of contiguous memory locations,which we will call the memory pool（存储管理的基本模型是有一大块连续的存储位置，称之为存储池). 存储分配（Memory Allocation） 存储回收（Memory Deallocation） 句柄（handle),Dynamic Storage Allocation 基本问题： 系统如何应用户提出的“请求”分配分存？又如何回收那些用户不再使用而“释放”的内存，以备新的“请求”产生时重新进行分配？,u7,u6,u5,u4,u3,u2,u1,初始：整个内存区是一个“空闲块”堆（heap）,随用户进入系统，先后提出存储请求，系统则依次进行分配,此时，新用户进入系统请求分配内存，系统如何做？,运行一段时间后：U2、U4释放存储资源,两种策略： 1、系统继续从高地址的空闲块中进行分配，而不理会已分配给用户的内存区是否已空闲，直到分配无法进行，系统才去回收所有空闲块，重新组织内存，连接构成大的空闲块。 2、用户一旦运行结束，便释放所占的内存区，同时新请求分配内存时系统需要巡视整个内存区所有空闲块，从中找“合适”空闲块分配。,0 10000 25000 31000 39000 59000 99999,可以是“目录表”，也可以是“链表”。,起始地址 内存块大小 使用情况,系统需要建立一张 “可利用空间表”来管理空闲块,目录表,链表,2.可利用空间表及分配方法 讨论链表的情况：可利用空间表中的所有可分配空间块是链表中的结点。 根据系统运行的不同情况，可利用空间表可有三种不同的结构形式： （1）系统运行期间所有用户请求分配的存储量大小相同。 将内存区分成基本大小相同的块，链成可利用空间表。 分配：每个结点大小相同，则分配时无需查找,第一个结点即可. 回收： 释放时，将空闲块插入表头即可。,（2）系统运行期间所有用户请求分配的存储量有若干大小规格。如：请求分配2个字，4个字或8个字的内存块，分别建链表。,tag= 0 空闲块， 1 占用块 0 结点大小为2位, type= 1 结点大小为4位, 2 结点大小为8位,分配与回收：与第一种类似。根据请求分配的大小选择相应的链表。当结点大小和请求分配的量相同的链表为空时，查询结点较大的链表，并从中取出一个结点，将其中的部分分配给用户，剩余部分插入相应大小的链表中。,特殊问题：当结点与请求相符和更大的链表均为空时，分配不能进行。 但实际上内存空间并不一定不存在所需大小的连续空间，只是多次小块的分配回收，空间块被分割成小块插入链表中。 -重新组织内存：执行“存储紧缩”。,可利用空间表,（3）系统运行期间分配给用户的内存块的大小不固定，可随请求而变。 链表中结点大小不同，则结点的结构为,必须设置size（结点大小域）,分配：用户需要大小为N的内存， 若可利用空间表中仅有一块大小为M=N的空闲块，则将其中大小为N的一部分分配给申请表，剩余的M-N作为结点留在链表中。 若可利用空间表中有若干不小于N的空闲块时，该分配哪一块？,分配： 若可利用空间表中有若干不小于N的空闲块时，如何分配？ 三种策略： （1）首次拟合（适配）法(first fit): 从表头开始查找可利用空间表，将找到的第一个大小不小于N的空闲块的一部分分配给用户。 例：用户U9申请7K的内存。,8000,分配： 若可利用空间表中有若干不小于N的空闲块时，如何分配？ 三种策略： （2）最佳拟合（适配）法(best fit): 将可利用空间表中一个不小于N且最接近N的空闲块的一部分分配给用户。,例：用户U9申请7K的内存。,1000,分配： 若可利用空间表中有若干不小于N的空闲块时，如何分配？ 三种策略： （3）最坏拟合（适配）法(worst fit): 将可利用空间表中不小于N且链表中最大的空闲块的一部分分配给用户。 例：用户U9申请7K的内存。,34000,首先适配有一个潜在缺陷：可能会把大块分成小块而“浪费”大块” 无法满足以后的大请求。 最佳适配的缺陷： （1）需要检索整个链表，费时。 （2）剩余部分可能很少而成为外部碎片。 最差适配的缺陷：需要检索整个表。,External fragmentation and Internal fragmentation,Small block：External fragmentation,Unused space in allocated block： Internal fragmentation,External fragmentation occurs when the memory requests create lots of small free blocks,no one of which is useful for servicing typical request Internal fragmnetation occurs when more than m words are allocated to a request for m words,wasting free storage.,在实际使用的系统中，回收空闲块时还需考虑“结点合并”的问题。 “结点合并”回收空闲块时,Dynamic Storage Allocation： 1. Boundary Tag Method边界标识法 （ Or Sequential-Fit Methods顺序适配方法) 2. Buddy Methods 伙伴系统,1. Boundary Tag Method Or Sequential-Fit Method 在每个内存区的头部和底部两个边界上分别设有标识，以标识 该区域为占用块或空闲块，使得在回收用户释放的空闲块时易 于判别在物理结点上与其相邻的内存。,整个结点由三个部分组成 space: 头部head 底部foot,（1）可利用空间表的结构,一组地址连续的存储单元,头部head: size:块大小， Llink:指向前驱， Rlink:指向后继 tag：0 空闲块 1 占用块,底部foot： tag,uplink指向本 结点头部,可利用空间表为双重循环链表 例：一个占有100K内存空间的系统在运行开始时可利用空间表,(2)分配算法 采用首次拟合法进行分配，从表头指针 pav开始查找，找到第一个容量不小于请求分配的存储量n 的空闲块时，即可进行分配，剩余m-n继续留在链表中。,为使系统更有效， 约定一：选定一个适当的常量e，待分配空闲块的容量为m个字。 当m-n=e时，将容量为M的空闲块整块分配给用户 反之，只分配其中n个字的内存块，约定将高地址部分分配给用户。 （因若每次分配只是从中分配n个字给用户，剩余m-n个字大小的结点留在链表中，则若干次分配后，链表中会出现一些容量极小总也分配不出去的空闲块，大大减慢分配速度）,约定二：在每次分配后，令指针pav指向刚进行过分配的结点的后继结点。以使每次分配从不同的结点开始进行查找，使分配后剩余的小块均匀分布在链表中，若每次分配都从同一结 点开始查找，势必造成存储量小的结点密集在pav所指结点附近。,分配7k的内存后：,分配7K的内存后 (3)回收算法 用户释放占用块,系统立即回收以备再分配。 为使物理地址相邻的空闲块结合成一个尽可能大的结点。 则首先需要检查刚释放的占用块左、右紧邻是否为空闲块。,（1）释放块F的左、右邻区为占用块，将F做新的空闲块插入可利用空闲表。 因为边界标识法按首次拟合进行分配时对可利用空间表的结构无要求；所以新的空闲块插入在表中任何位置均可。 简单做法：插入pav所指结点之前或之后。 （2）释放块F：左邻为空闲块，右邻为占用块 F的头部与左邻的底部相邻，则左邻空闲块结点SIZE增加且底部重新设置。,f,(3)F的右邻为空闲块，左邻为占用块。,F,T,t,P,t=p+p size p tag=0 q=t llink p llink=q; q rlink=p q1=t rlink p rlink=q1;q1 llink=p p size+=t size f uplink=p,(4)F的左右邻均为空闲块,S,F,p,s,T,f,总之，边界标识法由于在两个结点的头部和底部设立标识域，使的在回收用户释放的内存块时，很容易判别与它毗邻的内存区是否是空闲块，且不需要查阅整个可利用空间表便能找到毗邻的空闲块与合并。 再者，释放块插入时也不需查找链表。 回收空闲块的时间都常量，和可利用空间表的大小无关。 唯一的缺点：增加了结点底部所占的存储量。,2 伙伴系统（Buddy system）,边界标识法中，尽管回收空闲块的时间是一个常量，但存储分配： （1）存储分配必须检索可利用空闲表，以查找一个合适块。 最差情况下，查找一个合适空闲块的时间O（n）。 （2）合并相邻空闲块较复杂。 （3）保留块中需要设标记位字段带来额外的开销。 伙伴系统解决了上述问题 在伙伴系统中，无论是占用块或空闲块，其大小均为2的K次幂。,（1）可利用空间表的结构,llink tag=0 kval rlink 2k -1,占一个字空间,head,2的幂次K,(2)分配算法 用户推出大小为N的内存请求,在可利用空闲表中查找 （1）若N=2k ，相匹配，则将2k子表中任意一个结点分配之即可。 若2k 子表为空，则需从结点更大的非空子表中查找，直到 找到将其中一部分分配给用户，而将剩余部分插入相应的 子表中。 分配前,若2k-1 N= 2k-1,则删除2k 表中第一个结点分配给用户即可。 若2k-2 N= 2k-1-1， 2k-1的子表为空，则需从2k的子表中取出一结 点，将其一半分配给用户，剩余一半作些新结 点插入2k-1子表中。 若2k-i-1 N= 2k-i-1，且小于2k 的子表均为空，则需从2k子表中取 出一结点，将其中2k-i的一小部分分配给用户， 剩余部分分割或若干结点分别插入结点大小为 2k-i ， 2k-i+1 , 2k-1子表中。,(3)回收算法 同样的问题，回收时考虑地址相邻的空闲块归并成大块。 伙伴系统中，仅考虑互为“伙伴”的两个空闲块的归并。 何谓“伙伴”？ 在分配时经常需要将一个大的空闲块分裂成两个大小相等的存储区，这两个由同一大块分裂出来的小块称之“互为伙伴” 空闲块A、B是大小相同且地址相邻，但不是由同一大 块分裂出来A、B不是“伙伴”不能归并。 在回收空闲块时，首先判别其伙伴是否为空闲块。 若否，则将释放空闲块简单插入相应子表即可。 若是，则需在相应子表中找到其伙伴并删除之，然后再差别合并 后的空闲块的伙伴是否是空闲块，依此重复，直到归并所 有的空闲块的伙伴不是空闲块时，再插入一相应子表中 去。,B,A,2M-1,起始地址为P，大小为2k 的内存块，其伙伴块的起始地址为 buddy(P,K)= P+ 2k (若P MOD 2K+1 =0) 伙伴系统的优点：算法简单，速度快，外部碎片极少。 缺点：由于只归并伙伴而容易产生碎片， 而且允许内部碎片，如申请N=257个字。 需要分配512个字的块。,At some point during processing,a memory manager may encounter a request for memory that it cannot satisfy. In this case,the memory manager has no option but to return an error,which may in turn lead to a failure of the application program. However,in many cases there alternatives to simply return an error. The possible options are referred to collectively as failure policies. 失败处理策略：除了返回错误以外还有的其他选择,Failure Policies and Garbage Collection,Failure policies： 1.Compact memory In some cases,there may be sufficient free memory to satisfy the request,but it is scattered among small blocks .-external fragmentation that collectively cound service the request. In this case,it may be possible to compact memory by moving the reserved blocks around so that the free space is collected into s single block. Problem: If the application program relies on the absolute positions of the data in any way,this would be disastrous.若应用程序以某种方式依赖于数据的绝对位置，当数据移动时会引起严重后果。 One Approach: handles(使用句柄）：对存储位置的间接指引存储分配不返回一个指向存储块的指针，而是返回一个指向变量的指针，设变量指向存储位置,handle,2、Another failure policy that may work in some applications is to defer the memory request until sufficient memory becomes available. 延迟响应存储请求，直到有足够的可用存储空间. 如:多任务OS可能采用这样一种策略，一直等到一个进程有足够的存储空间可用时才允许该进程运行。 3、Another option may be to allocte more memory to the memory manager. 为存储管理器分配更多的空间：从系统级new操作符中得到更多的存储空间。 4、The last failure policy is garbage collection.,C/C+语言的内存管理要求申请的内存必须由用户手工释放，如果用户没有进行手工释放就会造成内存泄漏(Memory leak)。 例：,执行后， p=malloc(size)为用户分配的结点成为 无用单元，无法利用,（2） p=malloc(size)； q=p； free(p);,执行后，执行后，指针变量q悬空，若继续访问指针q所指结点 称“悬挂访问”,（1）p=malloc(size) p=null,（3）int *p=new int5; int *q=new int10 ; p=q;,使原分配给P的空间丢失,（4）另一种由于结构本身的某些特性，产生无用单元。如某用户程序中有三个广义表结构：L1，L2，L3 L1 L2 L4 L3 L5,1,若L1不再使用，L2，L3尚用，若释放表L1，即自L1指针起，顺链将所有结点回收可利用空间表中，这就破坏了表L2和L3产生“悬挂访问”。 若不释放表L1，则当L2，L3也不被使用时，这些结点由于未曾“释放”无法被再分配而成为“无用单元”。,“无用单元garbage”：指那些用户不再使用而系统没有回收的结构和变量。,如果产生内存泄漏将严重影响软件的可用性，同时手工回收内存还大大增加了程序员的工作量 为了让分配的内存在不再使用时自动释放，产生了垃圾收集算法 垃圾收集算法最早出现于20世纪60年代，到现在已经发展了几十年。 20世纪90年代Java语言支持垃圾收集，使得垃圾收集算法被广大程序员所认识 现在许多语言如Smalltalk等都拥有垃圾收集的支持，对于C/C+,也出现了一些支持收集的库,Garbage Collection Algorithm,Algorithm 1：Reference count Algorithm 使用访问计数器：Every dynamically allocated memory memory block incluedes space for a count field.在所有动态分配的存储块都包含一个计数字段 Whenever a pointer is directed to a memory block,the reference count is increased. Whenever a pointer is directed away from a memory block,the reference count is decreased.If the count ever becomes zero,then the memory block is considered garbage and is immediately placed in free store 。每当指针指向一个存储块（引用）时其引用计数加1，取消对内存的引用时就减1，当引用计数为0时，该存储块是无用单元，内存就可以被回收,Advantage：it does not requre an explicit garbage collection phase,since information is put in free store immediately placed in free store.不需要一个明显的无用单元收集阶段，每当存储单元成 为无用单元时，就立即把它放到可利用空间表中。 (Unix2文件系统：使用引用计数算法. 文件系统为每个文件保持一个链接数目计数, 一个文件被“删除”时，计数减1，减到0时，文件空间归还，供重新利用。) Disadvantage： A