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

Chapter4ListsandArraysRevisited 1 SkipLists2 Multilists3 MatrixRepresentations4 MemoryManagement AprobabilisticdatastructurethatcanbeusedimplementthedictionaryADT TheSkipListiscomparableincomplexitytotheBST yetoftenoutperformstheBSTsincetheSkipList sefficiencyisnottiedtothevaluesofthedatasetbeingstored Whichareliststhatmaycontainsublists Representationsforimplementingsparsematrices largematricswheremostoftheelementshavezerovalues Whichareessentiallyawayofallocatingvariable lengthsectionsfromalargearray 1 SkipLists SkipListsaredesignedtoovercomeabasiclimitationofarray basedandlinkedlists Eithersearchorupdateoperationsrequirelineartime 顺序表和链表的基本问题 每一次检索或更新需要的时间都是线性的TheprimaryproblemwiththeBSTisthatitmayeasilybecomeunbalanced BST的主要问题 容易变得不平衡The2 3treeisguaranteedtoremainbalancedregardlessoftheorderinwhichdatavaluesareinserted butitisrathercomplicatedtoimplement 2 3树保证不管数据值以什么顺序插入 都能保持平衡 但难以实现TheAVLtreeandthesplaytree whicharealsoguaranteedtoprovidegoodperformance butatthecostofaddedcomplexityascomparedtotheBST AVL树和伸展树都能保证提供好的性能 O logn 检索 插入 删除时间为O logn 但与BST树相比 也增加了额外的复杂性 1 SkipLists跳跃表 n个元素的有序表 采用折半查找所需时间复杂度为O logn 而对一个有序链表进行查找所需的时间复杂度为O n 对于有序链表时间复杂度如何由O n O logn SkipLists 1 SkipLists 在实现的难度和性能两方面进行了很好的折中 TheSkipListisnotguaranteedtoprovidegoodperformance butitwillprovidegoodperformancewithextremelyhighprobability 跳跃表不能保证提供好的性能 但提供好性能的概率极高Assuchitrepresentsagoodcompromisebetweendifficultyofimplementationandperformance 在实现难度和性能两方面进行了很好的权衡 有序链表 跳跃表 通过对有序表链表的全部或部分结点增加额外的指针 来提高搜索性能 在查询时 通过这些指针来跳过链表中若干个结点 因此没必要从左到右搜索连表中的所有结点 最坏情况下比较次数为8次 最坏情况下比较次数为4次 1 SkipLists 012 查找 key 30在二级链中找 由于3024故需在0级链中查找key 77与40比较77 40 在一级链中与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级链元素 则断开0 i级链指针 插入 级的分配 intrandomlevel void 级按指数分布for intlevel 0 Random 2 0 level returnlevel 1 SkipLists 2 Multilists广义表 InLists weassumedthatalllistellementshadthesamedatatype Weextendthedefinitionofliststoallowelementstobearbitraryinnature Ingeneral listelementsareoneoftwotypes 1 Anatom whichisadatarecordofsometypesuchasanumber symbol orstring 2 Anotherlist whichiscalledasublist 3 MatrixRepresentations Someapplicationsmustrepresentalarge two dimensionalmatrixwheremanyoftheelementshaveavalueofzero ThelowertriangularmatrixTheuppertriangularmatrixSparseMatrix a00000a10a1100a20a21a220a30a31a32a33 a00a01a02a030a11a12a1300a22a23000a33 4 MemoryManagement对OS和Compiler来说 存储管理都定一个复杂而又重要的问题 不同的编译的OS系统可采用不同的存储管理方法 用于处理变长空间请求Thebasicmodelformemorymanagementisthatwehavea large blockofcontiguousmemorylocations whichwewillcallthememorypool 存储管理的基本模型是有一大块连续的存储位置 称之为存储池 存储分配 MemoryAllocation 存储回收 MemoryDeallocation 句柄 handle DynamicStorageAllocation基本问题 系统如何应用户提出的 请求 分配分存 又如何回收那些用户不再使用而 释放 的内存 以备新的 请求 产生时重新进行分配 u7 u6 u5 u4 u3 u2 u1 初始 整个内存区是一个 空闲块 堆 heap 随用户进入系统 先后提出存储请求 系统则依次进行分配 此时 新用户进入系统请求分配内存 系统如何做 运行一段时间后 U2 U4释放存储资源 两种策略 1 系统继续从高地址的空闲块中进行分配 而不理会已分配给用户的内存区是否已空闲 直到分配无法进行 系统才去回收所有空闲块 重新组织内存 连接构成大的空闲块 2 用户一旦运行结束 便释放所占的内存区 同时新请求分配内存时系统需要巡视整个内存区所有空闲块 从中找 合适 空闲块分配 0100002500031000390005900099999 可以是 目录表 也可以是 链表 起始地址内存块大小使用情况 系统需要建立一张 可利用空间表 来管理空闲块 目录表 链表 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 首次拟合 适配 法 firstfit 从表头开始查找可利用空间表 将找到的第一个大小不小于N的空闲块的一部分分配给用户 例 用户U9申请7K的内存 8000 分配 若可利用空间表中有若干不小于N的空闲块时 如何分配 三种策略 2 最佳拟合 适配 法 bestfit 将可利用空间表中一个不小于N且最接近N的空闲块的一部分分配给用户 例 用户U9申请7K的内存 1000 分配 若可利用空间表中有若干不小于N的空闲块时 如何分配 三种策略 3 最坏拟合 适配 法 worstfit 将可利用空间表中不小于N且链表中最大的空闲块的一部分分配给用户 例 用户U9申请7K的内存 34000 首先适配有一个潜在缺陷 可能会把大块分成小块而 浪费 大块 无法满足以后的大请求 最佳适配的缺陷 1 需要检索整个链表 费时 2 剩余部分可能很少而成为外部碎片 最差适配的缺陷 需要检索整个表 ExternalfragmentationandInternalfragmentation Smallblock Externalfragmentation Unusedspaceinallocatedblock Internalfragmentation Externalfragmentationoccurswhenthememoryrequestscreatelotsofsmallfreeblocks nooneofwhichisusefulforservicingtypicalrequestInternalfragmnetationoccurswhenmorethanmwordsareallocatedtoarequestformwords wastingfreestorage 在实际使用的系统中 回收空闲块时还需考虑 结点合并 的问题 结点合并 回收空闲块时 DynamicStorageAllocation 1 BoundaryTagMethod边界标识法 OrSequential FitMethods顺序适配方法 2 BuddyMethods伙伴系统 1 BoundaryTagMethodOrSequential FitMethod在每个内存区的头部和底部两个边界上分别设有标识 以标识该区域为占用块或空闲块 使得在回收用户释放的空闲块时易于判别在物理结点上与其相邻的内存 整个结点由三个部分组成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 psizeptag 0q tllinkpllink q qrlink pq1 trlinkprlink q1 q1llink ppsize tsizefuplink p 4 F的左右邻均为空闲块 S F p s T f 总之 边界标识法由于在两个结点的头部和底部设立标识域 使的在回收用户释放的内存块时 很容易判别与它毗邻的内存区是否是空闲块 且不需要查阅整个可利用空间表便能找到毗邻的空闲块与合并 再者 释放块插入时也不需查找链表 回收空闲块的时间都常量 和可利用空间表的大小无关 唯一的缺点 增加了结点底部所占的存储量 2伙伴系统 Buddysystem 边界标识法中 尽管回收空闲块的时间是一个常量 但存储分配 1 存储分配必须检索可利用空闲表 以查找一个合适块 最差情况下 查找一个合适空闲块的时间O n 2 合并相邻空闲块较复杂 3 保留块中需要设标记位字段带来额外的开销 伙伴系统解决了上述问题在伙伴系统中 无论是占用块或空闲块 其大小均为2的K次幂 1 可利用空间表的结构 llinktag 0kvalrlink2k 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 若PMOD2K 1 0 伙伴系统的优点 算法简单 速度快 外部碎片极少 缺点 由于只归并伙伴而容易产生碎片 而且允许内部碎片 如申请N 257个字 需要分配512个字的块 Atsomepointduringprocessing amemorymanagermayencounterarequestformemorythatitcannotsatisfy Inthiscase thememorymanagerhasnooptionbuttoreturnanerror whichmayinturnleadtoafailureoftheapplicationprogram However inmanycasestherealternativestosimplyreturnanerror Thepossibleoptionsarereferredtocollectivelyasfailurepolicies 失败处理策略 除了返回错误以外还有的其他选择 FailurePoliciesandGarbageCollection Failurepolicies 1 CompactmemoryInsomecases theremaybesufficientfreememorytosatisfytherequest butitisscatteredamongsmallblocks externalfragmentationthatcollectivelycoundservicetherequest Inthiscase itmaybepossibletocompactmemorybymovingthereservedblocksaroundsothatthefreespaceiscollectedintossingleblock Problem Iftheapplicationprogramreliesontheabsolutepositionsofthedatainanyway thiswouldbedisastrous 若应用程序以某种方式依赖于数据的绝对位置 当数据移动时会引起严重后果 OneApproach handles 使用句柄 对存储位置的间接指引存储分配不返回一个指向存储块的指针 而是返回一个指向变量的指针 设变量指向存储位置 handle 2 Anotherfailurepolicythatmayworkinsomeapplicationsistodeferthememoryrequestuntilsufficientmemorybecomesavailable 延迟响应存储请求 直到有足够的可用存储空间 如 多任务OS可能采用这样一种策略 一直等到一个进程有足够的存储空间可用时才允许该进程运行 3 Anotheroptionmaybetoalloctemorememorytothememorymanager 为存储管理器分配更多的空间 从系统级new操作符中得到更多的存储空间 4 Thelastfailurepolicyisgarbagecollection C C 语言的内存管理要求申请的内存必须由用户手工释放 如果用户没有进行手工释放就会造成内存泄漏 Memoryleak 例 执行后 p malloc size 为用户分配的结点成为无用单元 无法利用 2 p malloc size q p free p 执行后 执行后 指针变量q悬空 若继续访问指针q所指结点称 悬挂访问 1 p malloc size p null 3 int p newint 5 int q newint 10 p q 使原分配给P的空间丢失 4 另一种由于结构本身的某些特性 产生无用单元 如某用户程序中有三个广义表结构 L1 L2 L3L1 L2L4L3L5 1 若L1不再使用 L2 L3尚用 若释放表L1 即自L1指针起 顺链将所有结点回收可利用空间表中 这就破坏了表L2和L3产生 悬挂访问 若不释放表L1 则当L2 L3也不被使用时 这些结点由于未曾 释放 无法被再分配而成为 无用单元 无用单元garbage 指那些用户不再使用而系统没有回收的结构和变量 如果产生内存泄漏将严重影响软件的可用性 同时手工回收内存还大大增加了程序员的工作量为了让分配的内存在不再使用时自动释放 产生了垃圾收集算法垃圾收集算法最早出现于20世纪60年代 到现在已经发展了几十年 20世纪90年代Java语言支持垃圾收集 使得垃圾收集算法被广大程序员所认识现在许多语言如Smalltalk等都拥有垃圾收集的支持 对于C C 也出现了一些支持收集的库 GarbageCollectionAlgorithm Algorithm1 ReferencecountAlgorithm使用访问计数器 Everydynamicallyallocatedmemorymemoryblockincluedesspaceforacountfield 在所有动态分配的存储块都包含一个计数字段Wheneverapointerisdirectedtoamemoryblock thereferencecountisincreased Wheneverapointerisdirectedawayfromamemoryblock thereferencecountisdecreased Ifthecounteverbecomeszero thenthememoryblockisconsideredgarbageandisimmediatelyplacedinfreestore 每当指针指向一个存储块 引用 时其引用计数加1 取消对内存的引用时就减1 当引用计数为0时 该存储块是无用单元 内存就可以被回收 Advantage itdoesnotrequreanexplicitgarbagecollectionphase sinceinformationisputinfreestoreimmediatelyplacedinfreestore 不需要一个明显的无用单元收集阶段 每当存储单元成为无用单元时 就立即把它放到可利用空间表中 Unix2文件系统 使用引用计数算法 文件系统为每个文件保持一个链接数目计数 一个文件被 删除 时 计数减1 减到0时 文件空间归还 供重新利用 Disadvantage Areferancecountmustbemaintainedforeachmemoryobject 必须为每一个存储对象维护一个引用计数 当对象很大时 如一个文件 这样有效 但当存在无用单元循环引用时 循环引用的内存块由于相互有指针指向对方 因此它的引用计数必然大于等于1 导致无法将其释放 h g Algorithm mark sweepAlgorithmEachmemoryobjectneedsonlyasinglemarkbitratherthanareferencecounterfield Whenfreestoreisexhausted aseparategarbagecollectionphasetakeplaceasfollows 1 Clearallmarkbits 2 Performdepth firstsearch DFS Followingpointersfromeachvariableonthevariablelist EachmemoryelementencounteredduringtheDFShasitsmarkbitturnedon 3 A sweep ismadethroughthememorypool visitingallelements Unmarkedelementsareconsideredgarbageandplacedinfreestore 当可利用空间表用完时 暂时中断执行程序 将所有当前不被使用的结点链接在一起 成为一个新的可利用空间表 然后程序在继续执行 问题 如何辨别哪些结点是当前未被利用的 对于一个正在运行的程序 可从当前正在工作的指针变量出发 顺链遍历 遍历到的结点为占用结点 其余结点为无用的 收集无用单元分两步 1 对所有占用结点加上标志 2 对整个可利用存储空间顺序扫描一遍 将所有标志域为 0 的结点链成一个新的可利用空间表 GarbageCollectionAlgorithm 研究标志算法 三种标志算法 1 递归算法 遍历广义表问题 需要一个较大的实现递归用的栈 而当前存储空间已经完全用尽 但因列表层次不定 递归层次不定 栈的容量不定 除非留一个相当大的区域作栈 否则会因栈溢出而瘫痪 2 非递归算法 类似遍历二叉树写出遍历表的非递归算法 所以是在算法中尽量减少栈的容量 3 利用表结点的指针标记遍历路径的算法 应用实例 使用链表管理短信息系统搜索引擎的实现抗DoS DDoS攻击的实例线程池调度管理Emalloc内存管理