随机包存储操作及其在数据结构中的应用

MOQAMOQAMOQA MOQAMOQAMOQAMOQAMOQAMOQA理论计算机科学电子笔记225（2009）341-360www.elsevier.com/locate/entcs一类随机保袋积运算Michel Schellekens米歇尔·舍勒肯斯1，2爱尔兰国立大学计算机科学系/CEOL，科克3摘要作者目前的研究计划是发展平均费用的模演算数据结构。这种模演算为算法的分析提供了一个新的基础。它对算法分析的适用性已经在面向电子科学的语言中心（CEOL）通过设计新颖的编程语言和相关的平均案例分析工具Ibra-TRACK [8，4，5，2，3]。通过随机袋保存的基本概念，数据结构化的平均成本的模块化计算是可能的。随机包存储操作使得能够在存储期间对数据和数据状态的分布进行建设性跟踪。一个计算。这又使得能够（半）自动地导出操作的平均成本。数据结构的创建和销毁有两个基本操作：乘积操作（本文的主题）和删除操作（[3]的主题整个语言的介绍远远超出了本文的范围并将在一本书中报道[2]。该语言已在CEOL实施，数据结构化平均成本的自动推导正在进行中。在这里，我们报告一个（简化）版本的随机袋保存的基本概念，并证明了中央产品操作具有这一重要性质。关键词：算法，随机包，组合性，模块化，语言。1引言是一种特定领域的高级语言。该语言具有广泛的编程能力，在这个意义上，它包括for循环，（终止）递归和条件。这种方法可以编程各种各样的数据重构算法，包括大多数排序和搜索算法。的关键属性是它保持了一定的“规律性”。在其运营过程中。这种规律性被随机结构和随机袋的概念所捕获。所有MOQA操作都保证 保存1爱尔兰科学基金会首席研究员，07/IN.1/I9772电子邮件：m. cs.ucc.ie3.面向电子科学的语言1571-0661/© 2008 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi：10.1016/j.entcs.2008.12.085342M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341MOQA±±±±随机的袋子。这使得在计算过程中的数据结构的跟踪，这反过来又有利于模块化的推导程序的平均情况下的时间。我们在本文中关注乘积运算，因为该运算有两个目的：第一，它使人们能够将元素（“基数为1的数据结构”）插入到数据结构中;第二，一般来说，它使两个数据结构合并为一个更大的数据结构。这样的操作例如在插入排序或合并排序中出现。该操作在这里以这样一种方式被公式化，它适用于由任意有限偏序确定的数据结构，包含非常广泛的数据结构。2状态和随机结构我们继续进行正式的定义。 第一个是定义国家的概念。 请注意，L形成了一组标签，我们认为这是一个子集的自然数配备了他们的标准秩序，（N，≤）。定义2.1从可数标签集N中对有限偏序（X，±）的标签是从X到N的递增注入，与偏序（X，±）配对。从一组标号L得到的有限偏序（X，±）的状态，其中|X|为|L|，是递增注入F：X→ L，与偏序（X，±）配对。注意，我们认为两个标号，比如（F1，（X，1））和（F2，（X2，2）），当它们的基础偏序不同时，它们是不同的。这包括X1= X2的情况，以及1和2不同，但函数F1和F2重合的情况。在实践中，当基本偏序是明确的，我们将引用标记F而不是状态（F，（X，±））。当然，从上面的定义可以得出，状态是来自X的双射。去洛在下面的符号中省略顺序是对符号的轻微滥用，这不会在作品中引起歧义。设（X，±）是有限偏序。设m（Y）表示（Y，±）的极小元集，M（Y）表示（Y，±）的极大元素的集合。设F是这个偏序的一个状态。设m（F）表示（X，±）的极小元F的标号，即F（m（X）），设M（F）表示F的极大元的标号，即F（M（X））。对于标签集合L的任何子集A，我们让m（A）表示A中（F−1（A），±）的极小元素的标签，即F（m（F−1（A），我们让M（A）表示F中（F−1（A），±）的极大元素的标签，即F（M（F−1（A）。最后，我们使用以下符号：A表示集合A的最大标号，而A表示A的最小标号。注2.2很明显，状态的最大（最小）标号必须出现在最大（最小）元素上。定义2.3有限偏序（X，±）上关于标签集L的随机结构，其中|X|为|L|，是来自部分的L的所有状态的集合，M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341343{}LL----R±AA你好！秩序 我们将这种随机结构表示为：RL（X，±）。记法：我们经常用R表示随机结构RL（X，±），在这种情况下，将底层集合X和标签集合L称为XR和LR。我们注意到，随机结构的定义并不要求底层的偏序是连通的。注2.4对于两个不同的标号集L1和L2，可以很容易地看到给定的部分序（X，±）的随机结构RL1（X，±）和RL2（X，±）是标号同构的，即存在从线性序（L1，≤）到线性序（L2，≤）的保序双射<$（L1，L2），其中≤是自然数上的通常序，使得RL2（X，±）={<$（L1，L2）<$F|F∈RL1（X，±）}.因此，如果L1={a1， . ，an}和L2={b1， . ，bn}，其中r∈{1， . ， n−1}。aiai+1，bi[a|swap（a，n）[a|、F）和以前一样，我们将在伪代码中自由使用Push-Down和Push-Up，不指定我们使用哪个版本，因为这是一个实现选择的问题。我们提供了伪代码的标签产品算法的输入算法是不相交的标签F1和F2。我们将标签乘积算法返回的函数F表示为F1F2。[4]参见 [9]这两个版本的讨论。350M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341标号积算法F：=F1→F2;当ΔM（FTX1）>ΔM（FTX2）时，a：=M（FTX1）;b：=m（FTX2）;sort（a，b）;下推（b，F）;俯卧撑（a，F）返回F引理5.3如果F1和F2是不相交标号，则F1F2是一个标签。证据这是通过随机乘积算法的伪代码进行的简单但技术上冗长的我们省略细节。 Q例5.4在下面给出的例子中，我们考虑下面显示的部分订单的两个标号F1和F2，并说明执行标号积算法的步骤。M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341351我们用完整的圆圈表示极值元素标签的选择，这些元素在下图中交换。对于每个while循环执行，由两个极值元素的标签的原始交换启动，要交换的其他元素对通过双箭头（虚线显示）在图片中链接这些元素在图片中交换出现最后一幅图说明了计算的最终结果，即F1F2。定义5.5设L1和L2是不相交的标签集。 标签产品功能：RL1（X1，±1）×RL2（X2，±2）→RL1<$L2（X1<$X2，±1<$±2）定义如下：（F1，F2）=F1F2。下面的结果对于获得随机乘积是RS保持运算是重要的。定理5.6标积函数是双射。证据 考虑两个不相交的偏序（X1，±1）和（X2，±2）.我们提出了一个证明威廉姆斯证明弗洛伊德的版本是类似的我们将标记乘积算法的执行视为沿着X1X2的链的一系列交换。对于给定的一对不相交的标签，F1和F2，每个这样的链由随机乘积的代码中的两个推操作的单次运行确定。我们回想一下，在while循环的开始，标签a和b涉及交换，其中就伪码而言，a=m（FTX1）和b=m（FTX2）。我们将这些标签称为极值标签。标签b沿着偏序（X1，±1）中的唯一链向下交换，标记为F1和a沿着偏序（X2，±2）352M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）3411± ±±±±1LL212K标记为F2。将这两条路径相加的结果在产品中形成了一条链 部分 秩序 （X1）我们将证明沿着这样的唯一链的每个这样的交换序列是单射的。因此，标号乘积函数是单射的。为了说明这个结果，我们假设我们有两个标号F1，FJ，偏序（X1，±1）和偏序（X2，±2）的两个标号F2，F2J，F1和F2不相交，F1J表明F1= F1J和F2= F2J。F2J是不相交的，F1F2= F1J F2J。我们我们将通过以下方式显示链上的标签，这些标签由调用F1F2产生的交换序列确定：[a1，a2，.，a m]，[b1，b2，...， b k]，其中（a，b）是算法交换的第一对，a m= a，b1= b，序列[a1，a2，...， a m]由标记偏序（X1，1）中的标记组成，F1），它们分别与b和序列[b1，b2，...，b k]由分别与a交换的标记偏序（X2，2，F2）中的标记组成。在上文中，我们允许m=0和k=0的情况，即不发生交换。类似地，我们通过以下方式显示链上的标签，这些标签由调用F1JF2J产生的交换序列确定：[aJ1，aJ2， . ，aJn]，[bJ，bJ， . ，bJl]，其中（aJ，bJ）是算法交换的第一对，aJn=aJ，bJ1=bJ，序列[aJ1，aJ2， . ，aJm]由标记偏序（X1，±1，F1，J）中分别与b j交换的标记和序列[bJ，bJ，.， bJ]由标记偏序（X2，2，F2J）中的标记组成与J交换。在上文中，我们再次允许n=0和l=0的情况，即不发生交换。我们注意到Ra（F1）= Ra（F1j）=1和Ra（F2）= Ra（F2j）=2.这意味着a=aJ，b= bJ。我们证明了a=aJ。b=bJ的情况类似。该算法选择标记偏序（X1，±1，F1）中深度为0的最大标记a和标记偏序（X1，±1，F1J）中的最大标记aJ由于Ra（F1）=Ra（F1J）=L1，并且标号在增加，我们知道L1的最大标号必须作为最大元素的标号出现，因此a=AJ=maximum（L1）。我们注意到这一事实不会改变，即使在算法中的前两个推通过归纳，我们可以证明Ra（F1）=Ra（F1J）仍然成立。事实上，在a b的情况下，不会发生互换，结果也不成立。否则，在前两个while循环发生了第一系列交换之后，我们得到在Ra（F1）中，标签a只是已经被标签b所取代，并且在F1J中也发生了同样的情况因此我们保留相应标签的范围一致的事实，M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341353F1诱导的非平凡交换序列的个数F2与12--以产生所需的性质。它遵循的事实是，在每个交换序列的开始处a=aJ和b=bJ由F1JF2J诱导的非平凡交换序列的数目。因此，我们可以关注由F1F2和F1JF2J引起的最后一个交换序列并假设两个交换序列，由上述，必须开始与交换同一对元素a和b。由于在前面的交换序列中标签当然已经改变了，所以我们在开始时表示标签分别用G1，G2和Gj1，Gj2对最终交换序列进行优化考虑这些标签交换的最终链，即链条[G−11（a1），G−11（a2）， . ，G−11（am）]，[G−21（b1），G−21（b2）， . ，G−21（bk）]和链条[（GJ1）−1（aJ1），（GJ1）−1（aJ2）， . ，（GJ1）−1（aJn）]，[（GJ2）−1（bJ），（GJ2）−1（bJ）， . ，（GJ2）−1（bJl）]。为了证明最终交换序列的内射性，它假设这些链必须是相同的。实际上，假设这些路径是相同的，比如用P表示的路径。以来F1F2=F1JF2J和P上的交换序列当然不包含标签一x1P，标号G1和Gj1必须在集合X1P. 此外，委员会认为，由于Push-Down操作的最终结果是将P的最大元素的标号移到F2中最初用b标记的元素，并将P的元素的每隔一个标号移到P上紧接在它上面的元素，我们得到G1必须与GJ1相同。我们主张，总是这样，即对应于b的交换序列对于G1和GJ1必须相同，因此，通过以上所述，最终交换运算形成单射运算。我们回想一下，由于F1F2=F1JF2J，我们必须在两个下推操作结束时，标签b是偏序中相同元素的标签我们通过矛盾的方式假设，这些路径不是相同的，因此在一点上分叉。因为b必须在最终交换序列的末尾相同的位置结束，所以我们知道在序列发散之后，标签b第一次作为X的相同元素z的标签结束。在此之前，s交换我们有：H1−1（x）=b和H1J−1（y）=b其中x/=y，其中H1和H1J是通过对G1和GJ1向上进行交换而从G1和GJ1到路径的第一次收敛之前的点我们在下图中澄清了标记H1和H1J的情况在H1中，标签b将与标签a互换，而在H1J中，与标签β交换。标签B将是由于在这些交换之后，x和y的标签将不会再次改变，因此下图中显示的标签是唯一可能的标签，以保证下推调用的最终结果是相同的。354M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341|R X，±| ×|RX，±| |11 2 2 1 2 1 2 L L 1 2 L L 1 2 L|11221212LL12L∪L12|L2 |L2X X X X，±12121LL124----{}。 Σ××其中LJ由第一个|X1|元素的排序版本，而LJ12x ya−β α a−zα β我们现在得到了一个矛盾，因为从标记H1可以清楚地看出，α β而从拉贝灵H1J我们得到β α。因此，我们不能有发散的路径和结果如下。由于同样的论点对a也成立，我们得到两个交换路径必须相同。证明现在可以通过归纳论证得出结论，该论证指出，当以其出现的相反顺序运行时，对于每对交换序列都必须成立。由于在交换路径之外的元素上，交换后，我们得到F1= F1J和F2= F2J。最 后 ， 我 们 需 要 验 证 标 签 产 品 功 能 是 满 射 。它 可 以 验 证（）（）=（）。我们注意到，|RL1L2（X1X2，±1±2）|为|RLJ1（X1，±1）|× |RLJ2（X2，±2）|、由排序版本中的最后一个元素组成。 这是因为（2）在局部序中，集合和完全连通（±2）。 由于我们可以识别直到序同构的标号，很明显，|为|R j（X 1，± 1）|并且|R L 2（X 2，± 2）|为|R j（X 2，± 2）|.|. 因此结果如下。Q我们得到下列直接推论。推论5.7设L1和L2构成标签集L的一个划分然后又道：|为|RL 1（X 1，± 1）|×| RL2（X2，± 2）.|RL2(X2,±2). |例5.8在第14页和第15页的例子中，我们说明了标号的随机乘积的产生是一个内射过程。我们并不展示所有的情况，而是将我们的注意力限制在可以用于第一偏序（1，2，3，4）的固定标号集和可以用于第二偏序（5，6，7）的固定标号集的情况。很容易验证，对于来自标签集合1，2，3，4，5，6，7的给定偏序，标签的可能组合的数量是75 2=350，这妨碍了对所有情况的完整说明。第一个五对标签的组合在下一页的顶部以粗体显示，然后是计算步骤，而接下来的五个组合在下一页以粗体显示，然后是计算步骤。我们定义了下面的二进制随机乘积，这可能是第一种类型的G1GJ1M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341355RX，±RX，±1 122LL12R X，±RX，±1 122LL12LLLLL1L LLMOQAR ±R±LL12R ±R±产品，其次是一元随机产品，这是一个将在应用中使用的5.3二进制随机乘积定义5.9Let（）和（）是两个不相交的随机结构。我们定义二进制随机乘积（）（） 为RL1<$L2（X1X2，±1±2）。引理5.10二进制随机乘积是RS保持的。证据 这直接由定理5.6得出。Q注5.11二元随机乘积导致了关于平均时间的确定的复杂性。实际上，二进制随机乘积具有作为标签集1和2的函数的平均时间。 考虑集合1恰好由小于集合1的最小标签的标签组成的情况。二、在这种情况下，二进制随机乘积将不需要下推或上推。在另一个极端，考虑标签集J1和J2，其中j 2的标签大于j的最大标签。 在这种情况下，显然二进制随机乘积J（X1，1）J（X2，2） 将 需要许多下推和俯卧撑运营因此，它的平均时间一般严格大于L1（X1，1）L2（X2，2）的平均时间。二进制乘积运算对所涉及的标签集的依赖性导致了关于其平均时间的确定的复杂性因此，语言在这个阶段不包含二进制随机相反，我们包括如下所述的一元随机乘积，这避免了上述问题，并且已经导出了表示平均情况时间的公式。始终存在包括二进制随机乘积运算的选项，并让分析工具为该特定运算返回黑盒类型的消息，其中用户需要为该特定运算提供他们自己的时间分析。操作这种方法55接第16356M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341357358M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341N.Σ|我|+|我|12次重复。MOQALIII12I，INXX，±12II12±R±NLL L| R±±121 212L12|I1|分区。Q对于简单的数据结构或对于其中工具被扩展为通过二进制随机乘积的动态分析来直接计算有界数据结构大小的平均情况时间的方法的情况可能是可行的5.4一元随机乘积我们描述了一元随机产品，已实现在Java在CEOL。这种类型的产品在涉及数据结构的连接的实现中是有用的，例如用于Mergesort算法中的合并操作和Insertion sort算法中的插入操作定义5.12考虑一个随机结构 （X，）和不同的组件 X的I1和I2。我们定义偏序（X，）关于以下分量的一元随机乘积：是偏序（） ， 其中±I1I2是包含± <$（（±TI1）（±TI2））的最小偏序.我们将一元随机乘积定义为函数：μI1NI2（X）：R（X，±）→R（X，±I1NI2）其中<$F ∈ R（X，±）. μI1I2（X，I）（F）T（I1I2）=（F T I1）（FTI2），μ（F）T（X−（I1<$I2））=FT（X−（I1<$I2））。定理5.13考虑随机结构R（X，±）和不同分量I1和X的I2。一元随机积μI1NI2（X）是多元保RS的|I1|证据 我们勾勒出证据。让是一组标签。从Corol-lary5.7我们得到，对于任何分区（，）的：（I I，）|为|RL（I1，±1）| ×|RL（I2，±2）|. 结果如下，因为有。|+|I 2|苏春|Σsu ch我们注意到，我们可以扩展一元随机乘积，以操作给定随机结构的随机子结构，如[2]所述。细节是技术性的，在此省略。 假设一元随机乘积 当将其应用于偏序的所谓孤立子集时，该运算仍然保证是RS-保持的。下面的例子说明了这一点。同样，由于空间限制，我们没有提供孤立子集的正式定义。操作应用的增加的通用性极大地增加了其在以下方面的使用：MOQA语言读者可参考[2]进行全面讨论。我们提供一个一元随机乘积的例子例5.14考虑以下树的哈斯图M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341359联系我们--|I1|1X5X4我我们显示了树的八个标签，其中我们选择了最深层的两个叶子，即x1和x2，以形成原子隔离子集I，并且该集合的标签如下所示我们将一元随机乘积应用于孤立子集I = x1，x2，并使用分量I = x和I = x。 结果如下所示。的涉及的多样性。|=.|Σ =. 2= 2。事实上，我们得到两个随机的副本，结构，由（I）标记的标签组成的第一份，即具有奇数索引的标签，以及由（II）标记的标签组成的第二副本，即具有偶数索引的标签。X3X1X2360M. Schellekens/Electronic Notes in Theoretical Computer Science 225（2009）341引用[1] B. A. 戴维，H.A. Priestley，Introduction to Lattices and Order，Cambridge University Press，1990.[2] M. Schellekens，A Modular Calculus for the Average Cost of Data Structuring，Springer出版，250页，2008年5月。[3] M. Schellekens，Compositional Average-Case Analysis，预印本，正在审查，2006年。[4] M. Boubekeur，D. Hickey，J. Mc Enery和M. Schellekens，A new Approach for Modular Average-CaseTiming of Real-Time Java Programs，2007年在WSEAS Transactions on Computers上发表。[5] M. Boubekeur，D.Hickey，J.Mc Enery和M.Schellekens，Towards Modular Average-Case Timing inReal-Time Languages：An Application to Real-Time Java，第六届WSEAS应用计算机科学国际会议（ACS'06），特内里费岛，2006年12月[6] S. Edel Kamp. 我们走了，一个人把他的衣服整理好。1996年，获博士学位。[7] D. Knuth，计算机编程的艺术卷。3，Addison-Wesley，1973.[8] M.Schellekens，D. Hickey和G. Bollella，ACETT，一种用于（半）自动平均案例分析的线性组合编程语言，IEEE实时系统研讨会-工作进展会议，2004年。[9] M. Li和P. Vitanyi。Kolmogorov复杂性及其应用介绍，计算机科学中的Springer Verlag，1993年。