text:
|Publication number
|Publication type
|Application number
|PCT number
|Publication date
|Nov 27, 2008
|Filing date
|Feb 16, 2006
|Priority date
|Feb 16, 2005
|Also published as
|Publication number
|Michel Schellekens
|Original Assignee
|Michel Schellekens
|Export Citation
|BiBTeX, EndNote, RefMan
|Patent Citations (1), Referenced by (5), Classifications (9), Legal Events (1)
|External Links: USPTO, USPTO Assignment, Espacenet
1. Field of the Invention
The invention relates to control of data processor activity and utilization of memory.
2. Prior Art Discussion
There are many software code applications which involve a large number of comparison operations and for which it would be very advantageous to be able to predict the processor time to execute the code. This is particularly true for real time applications such as are flight control systems in aircraft or vehicle cruise control applications.
An example of the source code language which is used for development of comparison-based programs is Java Libraries™. It would be very advantageous to be able to accurately predict the processor execution time for a program developed in this language as execution of the programs involves many cycles of retrieving libraries and processing their data. If accurate prediction were possible, it would in turn be possible to correctly deploy the correct hardware resources for optimum trade-off between performance and cost, to plan the timing of interactions between tasks, and to allocate tasks to processing units.
At present, estimation of execution time is typically on the basis of Worst-Case Execution Time ("WCET"). The problems with this approach are that (a) they output a worst-case scenario so that there is typically over-specification of hardware resources, and (b) the processes for generating the WCET are not completely automated.
As software code is concerned with manipulating data, the state of the data is constantly changing during that program cycle. At any point in the program, depending on previous decisions made by the program, the data will be in a particular state. Current software technology does not provide for determining all possible states data can be in at any point of a program's execution.
The invention is directed towards providing a software development method for more accurate prediction of execution time and/or for more automated prediction of execution time. It is also directed towards the development of an associated static analysis timing tool to perform steps of the method. It is also directed towards providing a data processing system incorporating software developed in this method.
The invention provides a method of developing software code for executing on a target digital processor using a memory in which it maintains data structures having elements, each of the elements storing data which is represented by a label, and at least some links between the elements being created by the target processor as data is being processed, the method comprising the steps of:
Other features of the invention are set out in the appended claims, the contents of which are incorporated herein by reference.
The invention will be more clearly understood from the following description of some embodiments thereof, given by way of example only with reference to the accompanying drawings in which:
The invention provides a method of developing software code, called MOQA (MOdular Quantitative Analysis), the method involving use of a static analysis timing tool called "Distri Track" after software development to automatically estimate the actual times for execution of the code. The MOQA method allows knowledge about the data to be derived by the Distri Track tool, i.e. all possible states of data are known at any given point of the code execution, and to keep track of all states during the execution.
This method of developing software code is based on a specific body of rules. Any programmer or automatic development tool which adheres to these rules of how data is created and manipulated can apply the Distri Track tool to statically analyze the code and determine the average-case time of the computation.
The Distri Track tool extracts the data distribution information at any given point of the computation. By using this information in a way described further below, the average number of basic steps a computation performs (for example, comparisons, swaps, and assignments) in order to manipulate the data can be calculated by Distri Track. This information in turn enables Distri Track to statically predict the average-case time of the computation, simply by multiplying the number of computation steps by the time it takes to compute such a step (or an upper bound of this time) on the particular processor used and summing up the resulting times.
Referring to
Any program operates on data structures. MOQA however states unambiguously how to create and manipulate a data structure in order to make average timing of this manipulation possible.
A memory data structure consists of data and how this data is related. How this relationship between data is represented varies from program to program. MOQA states a particular way to represent the relationship as defined below.
In more detail, a memory data structure is a finite collection of elements and the relations, or "links", between elements. The elements store the data. The MOQA methodology is used to form the relation or links between the elements. The elements are not individually uniquely addressed or labelled. Instead, the processor identifies the data stored in them and uses the data to relatively address the elements. A data value comprises a pair of an identifier or "label" and a piece of data. To take the example of a temperature measurement in a chemical process plant, there are many millions of such measurements and each one may comprise a pair of a temperature value (the label) and a piece of data comprising the location where the measurement was taken. Data will always have a label. The labels are always comparable with respect to a specific order, for example "less than or equal to". Therefore for any two labels one can always decide whether the first is less than the second or the second is less than the first, in that example. Sometimes it is not necessary to have a label if the data itself is directly comparable, e.g. sorting numbers. In these cases the label is also the data.
When a new link is created between two elements, the link has a direction. For example, for two elements x and y, it is indicated whether the link proceeds from x to y or from y to x. So the processor creates a relation from x to y or from y to x. In other words the data of x must be below the data of y or visa versa. However we now have to take into account that both pieces of data have labels. For instance if the data in x has the label which is the number 13445 and if the data in y has the label which is the number 12333 and if a link is created from x to y (indicating "x is below y") then the numbers need to be moved (in fact swapped in this case) along with their data, or solely the numbers in case of pointers linking labels and data, depending on the choice of implementation. This needs to happen for the end result to respect the less than or equal to ordering that is indicated by the link.
These labels may or may not be the same. However, for data storage in MOQA, the labels are required to be distinct from one another. If data is supplied that has a label already attached to another piece of data, it is a rule to ensure that this is dealt with appropriately to prevent duplicate labels being attached to stored data.
In this document the word "label" is synonymous with identifier. We now have described what a data structure is and how MOQA represents such a data structure.
The MOQA methodology is concerned with how the data structure is changed, how the links in the data structure are created and destroyed in an acceptable fashion, which leads to data being reorganized accordingly. The acceptable methods of changing a MOQA data structure include the four main MOQA operations below. A "delete" operation removes an element and its data with its associated label from (part of) a data structure. A "product" operation allows one to "merge" two (parts of) data structures into a larger data structure, made up of the original two data structures and reorganize their labels accordingly. A "split" operation allows one to link elements in (part of) a data structure in such a way that the elements are above or below a specified element, depending upon the identifiers/labels of the elements. A "projection" operation allows one to produce a copy of (part of) a given data structure.
The invention is not restricted to these operations, but these are core operations in this embodiment, for which the first three in particular are key to all data manipulation.
We also characterize precisely a condition which any operation (not only the above four, but any other operation complying with the rules) needs to posses in order for the data manipulation to achieve the desired effect. This is the condition of "random structure preservation". This enables one to test in practice whether the average-case time of the operation can be determined by the static analysis tool Distri Track. We also characterize the exact parts of data structures on which it is allowed to execute the MOQA operations, in particular the isolated subsets of a data structure and the strictly isolated subsets of a data structure. Depending on the operation in question (as described below), the operation can be applied to such a part (isolated or strictly isolated), whereupon the Distri Track tool can track the random sequences produced. Distri Track obtains the average-case time by having the guarantee that every MOQA operation satisfies the condition of random structure preservation (and thus "random sequence preservation"). To explain these terms we first introduce the concept of a labeling and the related concept of a random structure.
We know that each piece of data has a label. Gathering together all the labels of all the elements in a data structure is defined to be the particular labeling of that data structure. The labels respect the ordering of the data structure and a data structure can have more than one possible labeling that respects the ordering of that data structure.
For instance, we consider a data structure consisting of the V-shaped triple of elements, say an element x (at the apex of the V-shape) is linked to an element y and an element z. Say, for example, we use natural numbers as labels. Say we want to store the information consisting of the numbers 3, 6 and 9 in elements of the V-shape. Since the element x is linked to the elements y and z (in the direction from y to z) our rule on the ordering indicated by links specifies that labels stored in x must have a value less than the labels stored in y and in z. Hence the label stored in x must be the number 3. In the storage of the labels 6 and 9, we have freedom: we can store the label 6 in the cell y and 9 in the cell z, or 9 in the cell y and 6 in the cell z. This results in two possible labelings. The first which assigns the value 3 to x, the value 6 to y and the value 9 to z, and the second which assigns the value 3 to x, the value 9 to y and the value 6 to z.
The two labelings in the previous example form a "random structure" over the data structure consisting of the V-shape. In general, if a data structure has n elements and if we collect all possible labelings of these elements from a given fixed set of labels a(1), . . . a(n), then this collection of labelings is called a random structure over the data structure.
During a computation only one of these particular labelings will be in use at any given stage, so a MOQA operation will take a particular labeling over the elements of a data structure and return another data structure with a particular labeling for that structure.
If a MOQA operation does this individually for every labeling of a data structure, i.e. the entire random structure, we can guarantee that if we gather together the results, they can be grouped into one or more random structures, with no leftover individual resulting labelings that do not form a random structure. So if some data structure with a particular labeling is selected from the resulting output of a MOQA operation on a random structure, the random sequence preservation guarantee is that all the other possible labelings for that the data structure will also be among the output, when the operation has been applied to all possible input labelings from the random structure. The random structure is over a particular set of labels.
Random structure preservation means a random structure can be transformed into one or more new random structures, each of which could be copied a certain number of times. This final result is referred to as a random sequence. Each random structure preserving operation can be extended to operate on random sequences as follows (we refer to this as "random sequence preservation"). Random sequence preservation then means that a random sequence is transformed into a new random sequence, by carrying out a random structure preserving operation on each of the random structures in the random sequence. Each random structure in the random sequence is replaced by the new random sequence produced from this random structure. Random structures are regarded as random sequences of size one.
The output of a MOQA operation on a random structure can be grouped into one or more random structures. These one or more random structures are referred to as a random sequence of random structures. If some of the random structures in the random sequence are identical, they can be grouped together and represented by one copy of the random structure together with a number indicating how many times it appears in the random sequence. This number is called the multiplicity of the random structure (in the random sequence).
Therefore any random structure has a multiplicity of either one, it appears once in the random sequence, or more than one, it appears more than once in the random sequence.
The Distri Track static analysis timing tool operates on program code developed via MOQA methodology. It initially takes a random structure, consisting of the initial input states for this program, and the first MOQA operation of the program on that random structure, and calculates the random sequence outputted by the operation. Subsequently, it takes that random sequence and the subsequent MOQA operation will now be performed on a random sequence. Distri Track takes each random structure in that random sequence and applies the principles of how a MOQA operation changes a structure to determine its associated random sequence. It then replaces the random structures in the original random sequence, with the new random sequences reflecting the consequences of the MOQA operation on the random structures in the original random sequence.
This cycle continues with this random sequence now being taken by Distri Track which applies the next MOQA operation and so on until program completion and the final random sequence is produced.
This process is illustrated in
Distri Track does not calculate the random sequence by calculating the result of the operation over all labelings of the original random structure. Rather it takes the original random structure and produces from its data structure a new sequence of data structures based on the rules for the MOQA operation. Moreover, Distri Track immediately computes the multiplicities involved in the output random sequence. The fact that this efficient approach works is guaranteed by the fact that the MOQA operations are random sequence preserving.
We describe the process of random sequence preservation in the context of Distri Track. A random sequence (R1,K1), . . . , (Rn,Kn) is here represented as a distribution. The horizontal axis represents the random structures, while the vertical axis represents how many copies of the random structures are produced in the computation.
By calculating the random sequence produced by one operation, Distri Track can, along with complex mathematical formulas, determine the average-case time of this operation.
The compositionality of MOQA operations (guaranteed by their random sequence preservation) enables Distri Track to determine the average-time of any program written with the MOQA methodology.
Distri Track parses the code to follow the program flow in calculating the average-case time, whether sequential or branching. It is fully modular in that it determines the average-case time of each program (produced via MOQA methodology) in terms of linear combinations of the average-case times of the MOQA operations within that program.
If software has been timed and one alters a piece of the software, only this particular piece needs to be re-timed by Distri Track and recombined with the priorly obtained times (excluding the time of the replaced piece); since the tool is modular. None of the current timing tools is (functionally) modular in this sense.
For the example of a program composed of sequential MOQA operations, Distri Track will produce the average time of the program as the SUM of the average times of each individual operation. The fact that the average time of a program or collection of programs can be obtained in this way is only guaranteed for MOQA-produced software. This is a major improvement over the prior art, in which programmers had to carefully select a tiny but appropriate collection of inputs among millions, perhaps infinitely many possible inputs, itself a laborious (or impossible) task, with no guarantee of accuracy. In fact it was not possible to produce in this way the exact average-case time. As well as the selection process, they then had to carry out the actual testing procedure, which in many cases, due to the amount of memory required, resulted in only very small sample cases to be testable. Often these approximations could be close to the mark, but this is insufficient in the context of real-time analysis and critical applications, where precision needs to be guaranteed. In these cases trust had to be placed in the approximated average-case time as this was the only answer available.
The MOQA methodology radically transforms average case analysis. No longer are such laborious tests required. Distri Track produces the precise answer with one run of its program. There is no need to execute the software to be timed on any of its inputs, not even once. Distri Track hence saves hours in testing, increasing productivity of programmers, letting the focus be on accurate code as opposed to timing the code. Because the average-case time is known, code can be written which better optimizes the use of resources. So the exact average-case time allows time itself to be saved in code development and therefore this additional time can be allocated to the production of more efficient code.
Before describing the four key MOQA operations in more detail, the following are some useful definitions that will assist in characterizing these operations.
Data structures (finite collections of elements and their links) are formally characterized as finite partial orders. We do not insist that all links of a partial order are actually represented in an implementation of the data structure/stored in memory. In fact we allow the traditional approach for partial orders of minimizing the number of links through the so-called transitive reduction and the well-known partial order concept of Hasse Diagram.
We also characterize the exact parts of data structures on which it is allowed to execute the MOQA operations, in particular the isolated subsets of a data structure and the strictly isolated subsets of a data structure. Depending on the operation in question (as described below), the operation can be applied to such a part (isolated or strictly isolated), whereupon the Distri Track tool can track the random sequences produced.
The definitions are as follows:
Partial Order
Maximal and Minimal Elements
Component (Connected Component)
Directly Related
Isolated Set
Strictly Isolated Set
Every random structure over a data structure has a data structure which is determined by a partial order and also has a set of labels. There are two sets involved: a set of elements of the partial order and a second set which is the partial order's set of labels. Both these sets are the same size. The partial order attaches these label values to its elements in an order-consistent way, consistent with the relationship between the elements. An order consistent way of attaching the labels is called a labeling. Often there is more than one order-consistent way that the labels can be arranged over the elements in the partial order. Gathering together all the possible ways a set of labels can be arranged over a partial order, i.e. gathering all labelings, is defined as a random structure. Formally, a random structure consists of all possible labelings of a partial order from a given set of labelings and where labels are used which are all distinct from one another and stem from a collection of labels which has same size as the number of elements in the random structure. A random-sequence-preserving operation transforms a random structure to a sequence of random structures. This random-sequence-preserving property of all MOQA operations is what enables average-case time to be automatically derived, from running MOQA code through a static analysis tool. To gain a clearer understanding of what it means for a MOQA operation to be random-sequence-preserving, we examine the general behaviour of any MOQA operation on a single labeling of a partial order.
Every MOQA operation takes a particular labeling over the elements of a finite partial order and the majority of MOQA operations then change the relationship between the elements of this partial order. As well as adjusting the relationships between the elements, the MOQA operation may also need to adjust the particular labeling of the original partial order, as the particular labeling may not be order-consistent over the new partial order, consistent with the updated relationships between the elements. The two definitions, Push-Down and Push-Up are MOQA-package operations used by MOQA operations to harmonize a particular labeling with its newly adjusted partial order.
A MOQA operation receives a partial order and a particular labeling over that partial order's elements. It then returns another partial order with a particular labeling over that partial order's elements. If a MOQA operation does this individually for every labeling of a partial order, i.e. the random structure, we can guarantee that if we gather together the results, they can be grouped into one or more random structures, with no leftover individual results that do not form a random structure. So if some partial order with a particular labeling is selected from the resulting output of a MOQA operation on a random structure, the random-sequence-preservation guarantee is that all the other possible labelings for that partial order will also be among the output. Consider a partial order with all six distinct possible labelings, i.e. a random structure. The same MOQA operation is executed on each labeling of this partial order and the six end results are distinct labelings over some new partial order. Due to the operation being random-sequence-preserving, these six labelings will also be all the possible labelings of the resulting partial order. While this situation can occur it is generally too simplistic to be realistic. The overall result can easily contain a number of different partial orders for which all possible labelings are generated. In the example of the initial partial order of six possible labelings, which are all passed to the same MOQA operation, the outcome could be two different partial orders, one with two labelings, the other with four labelings. However, again due to the random-sequence-preservation of MOQA operations, the two labelings will be all possible labelings of that partial order and the four labelings will be all possible labelings of the other partial order. So a number of different partial orders may be generated from changing one partial order across all its possible labelings. The guarantee of any MOQA operation is that all the possible labelings of these new partial orders will be generated too, with no leftovers/incomplete random structures.
When two or more random structures are generated, there can be more than one random structure for the same partial order, where each identical random structure has its own complete set of all possible labelings. In other words all the possible labelings for a partial order can appear twice, three times, four times, etc. The number of identical random structures, where each random structure has its own distinct and complete set of all possible labelings, is formally called the multiplicity of that random structure. So if there was a partial order with two possible labelings and six labelings for this partial order were found in the result of some MOQA operation going over all possible labelings of an original partial order, then there must be three identical random structures of that partial order in the result, that the multiplicity of the random structure is three.
In summary, a MOQA operation executes over one possible labeling of a finite partial order at a time. The operation generally alters the relation between the elements in that partial order and the labeling may also be altered to be in line with the new partial order. So either before or after the elements have their ordering changed, it may be necessary to change what labels are attached to what elements, by means of Push-Down and Push-Up, until the labeling is consistent with the new ordering of the elements. Due to the fact that MOQA operations are random-sequence-preserving, that is applying them to a random structure always gives a sequence of random structures, means we can rely on the fact that the probability of a possible labeling occurring within its random structure and the probability of a possible labeling occurring over all random structures can be determined. The probability of a possible labeling occurring within its random structure is equal to the probability of any other possible labeling within that random structure occurring. The probability of a possible labeling occurring over all random structures, if each random structure is distinct, is one over the number of all possible labelings that can occur. The number of all possible labelings that can occur is the sum of the size of every random structure in the sequence. The size of a random structure being the number of all possible labelings of its partial order. The probability of a possible labeling occurring over all random structures, if each random structure is not necessarily distinct, is the size of the labeling's random structure multiplied by its multiplicity over the total number of labelings that are in the random sequence. The total number of labelings in the random sequence is the sum of the size of each random structure multiplied by its multiplicity for every random structure in the random sequence. This information is used by the static analysis tool to determine average-time case time automatically, an advantage MOQA has over other standard programming languages. Random-sequence-preservation is the key to this new technology.
The product operation is used to construct any partial order other than the partial order that has the identity relation =, i.e. the discrete order. The discrete order is the initial input from an external source that is supplied in an implementation-dependent manner. Every MOQA data structure is built from the base case MOQA data structure, which is the discrete order. The discrete order is the starting point prior to any sequence of random-sequence-preserving MOQA operations. Once a discrete order has been supplied, the product operation can be used to specify a relation between elements in a partial order, to impose an ordering between elements which is more than the identity relation =. The product operation is defined as follows:
However, if
So as to ensure random-sequence-preservation, the sets to be producted together must have certain properties in common, otherwise the product operation will fail in an appropriate manner, without any change to the partial order. The properties are as follows:
A more formal way of describing the properties of the two sets is to say that A and B are two distinct components of an isolated subset I of a finite partial order (X,
Once the parameters for the product operation meet the conditions outlined above, the product operation, in combination with other MOQA operations, can build partial orders at any level of complexity desired by the computation. So far, product has been described as taking place within a partial order but what about a product operation across two distinct partial orders (X1,
Examples of the product operatin are set out in
The split operation, like the Product operation, changes the ordering of a partial order by adding additional relations between the elements in the partial order. The split operation is defined as follows:
So as to ensure random-sequence-preservation, the set that is being split around one of its specified elements must have certain properties, otherwise the split operation will fail in an appropriate manner, without any change to the partial order. The properties are as follows:
A more formal way of describing the properties of the set that the specified element
While split has much in common with Product by its constructive nature, the underlying approach differs in more than just definition details. It has already been shown that a random structure can be seen as the combination of two separate sets, the set of elements and the set of labels for these elements. The set of elements have an ordering between them and the set of labels can be laid over the set of elements in one or more ways that satisfy the ordering. Product forms a relation between two sets of elements, subsets of a larger set of elements, once these sets meet the required properties of Product. The particular labeling involved, which is laid over the larger set of elements, is then shifted around this new ordering if necessary. However, split forms a relation between an element and the other elements in the set, once the set meets the required properties of split, based on the particular labeling of that set. Product changes the ordering in a partial order independent of the particular labeling. The labeling is only considered afterwards as part of the cleaning-up process. However, split changes the ordering in a partial order based on the particular labeling. The labeling is an intrinsic part of the operation, used to influence the new ordering.
Examples of the split operation are illustrated in
The projection operation is simply a copy operation. The projection operation is defined as follows:
If a MOQA operation, other than projection, is executed on I after projection, I will no longer be order-isomorphic with J and vice versa. This clearly holds if the MOQA operation is executed on J instead. Now J will no longer be order-isomorphic with I and vice versa. To restore order-isomorphism in the first case, the same MOQA operation must be executed on J after being executed on I. Not only the same MOQA operation but the same MOQA operation involving the same size subset(s) as in I. Plus the subset(s) of J involved in the MOQA operation must have the same ordering, in terms of the overall set, that the subset(s) of I involved in the MOQA operation had. As I and J's element and label sets are distinct, the order-isomorphism does not hold otherwise.
So as to ensure random-sequence-preservation, the set I that is being projected must have a certain property, otherwise the projection operation will fail in an appropriate manner, without the creation of the set J. The property is as follows:
1. The set I is an isolated subset of a finite partial order (X,
Examples of the projection operatin are illustrated in
The delete operation is not always as simple or as intuitive as its name suggests. Delete is defined in terms of the entire finite partial order (X,
The delete operation over an entire partial order is defined as follows:
So as to ensure random-sequence-preservation, the property of the partial order that an element is deleted from must simply be that it is a finite partial order (X,
Reference is made to
The delete operation over a strict subset of a partial order is defined as follows:
So as to ensure random-sequence-preservation, the strict subset of the partial order that is having an element deleted from it must have a certain property, otherwise the delete operation will fail in an appropriate manner, without the deletion of an element. The property is as follows:
Please refer to
Push-Down and Push-Up are used by other MOQA operations for the purpose of ensuring that the particular labeling in question is to be consistent with the new ordering on the partial order. The MOQA operations will specify which label value in the labeling that they want Push-Down or Push-Up called upon. Depending on the definition of the MOQA operation and how out of sync the labeling is with the new ordering, Push-Down and/or Push-Up may be repeatedly executed on a series of label values. The definition of Push-Down and/or Push-Up are as follows.
Push-Down takes the specified label value,
Where └
Note how this formal definition of Push-Down is called W-Push-Down. This is because the manner of pushing the label value down to its appropriate position, described here both recursively and iteratively, was initially defined by Williams in his implementation of Push-Down [Wil64, which we refer to as W-Push-Down. The other approach is Floyds [Flo64]. Floyd's differs to Williams in that he does not continuously swap
Whether Push-Down is in the style of Floyd or Williams is an implementation detail as both versions produce the same solution. The idea is that a label, which is not in its correct position because it is smaller than one or more label values below it in the ordering, is pushed down to a suitable position that now satisfies the ordering.
Push-Up is the inverse of Push-Down as this definition shows. Push-Up takes the specified label value,
Where └
Note how this formal definition of Push-Up is called W-Push-Up. This is because the manner of pushing the label value up to its appropriate position, described here both recursively and iteratively, was initially defined by Williams in his implementation of Push-Up [Wil64], which we refer to as W-Push-Up. The other approach is Floyds [Flo64]. Floyd's differs to Williams in that he does not continuously swap
Whether Push-Up is in the style of Floyd or Williams is an implementation detail as both versions produce the same solution. The idea is that a label, which is not in its correct position because it is larger than one or more label values above it in the ordering, is pushed upwards to a suitable position that now satisfies the ordering.
It will be appreciated that the current state of the art of modular time derivation is extremely limited. We have shown that it can NOT be achieved in general for worst-case time analysis. Some partial modularity has been obtained in prior art and only in extremely limited contexts such as forced complete execution of both conditional branches of any conditional statement. Also partial modularity for worst-case time can be achieved under conditions where all processes are assumed to be entirely independent from one another, i.e. there is no functional dependency and no process every waits for the outcome of another process. Again, this is an extremely restrictive context.
The MOQA methodology on the other hand, works for the average-case time, where it is shown that modularity is guaranteed (as opposed to partial modularity) and where functional dependency is allowed, i.e. it is perfectly allowed for one process to have to wait for the output of another in order to continue the computations.
The following section, called "More Detailed Technical Specification" describes the operations and the static analysis timing tool more comprehensively. There is a degree of repetition or overlap between the following passages and the preceding ones. This is considered necessary as it allows the following passages to be read as a unit without need to frequently refer back to the preceding passages, which are written at a slightly higher level description for ease of understanding the invention.
Each random sequence consists of "random structures" paired with a multiplicity. The multiplicity reflects the number of copies of the random structure which are produced after an application of a data structuring operation.
These multiplicities play a crucial role in average-case time analysis.
In particular, if we compose basic data structuring operations in order to obtain a transformation of one data structure into another, we can obtain an expression (recurrence equation) of the average-case time of this composed operation provided all the basic operations are Random Structure Preserving (in the sense specified below). Indeed, in the case of Random Structure Preservation, we are guaranteed that a Random Sequence is once again transformed into a new Random Sequence. The multiplicities of the resulting sequence can then be used to determine the average-case time.
Our results are specified for labels which can come from any linear order. For the sake of simplicification of presentation we focus on data structures for which a labeling has no repeated labels. However, our results apply to the general case of repeated labels as well. Essentially our method guarantees modular timing, i.e. the average-time of a composition of data structuring operations is guaranteed to be obtainable from the average-times of the basic operations involved in the composition. This induces a considerable simplification in average-case time determination, which is obtained thanks to this novel approach.
The verifications that the method works are made in the following.
We denote the real numbers by
For any set X, we let |X| denote its cardinality. For any function ƒ: X→Y we let Ra(ƒ) denote the set of values {ƒ(
The result of concatenating two sequences, say A=(a1, . . . , aη) and B=(b1, . . . , bη) is the sequence Conc(A, B)=(a1, . . . , aη, b1, . . . , bη). Concatenation of more than two sequences, Conc(A1, . . . , Aη), is defined in a similar way.
An affine combination of a sequence of real-valued functions ƒ1, . . . ,ƒη is an expression of the form α1ƒ1+ . . . +αηƒη where α1, . . . ,αη are scalars and
A partial order is a pair (X,
We use the following notation for partial orders (X,
If (X1,
We assume that the reader is familiar with Hasse Diagrams (e.g. [DP90]) which we will use to represent partial orders in the examples. The transitive reduction of a partial order (X,
A linear order (X,
For any set X we denote the discrete partial order on X, i.e. the partial order consisting only of the reflexive pairs {(
For any subset Y of a partial order (X,
An element
For any two points
The length of a path of a finite partial order is the number of elements on the path.
A chain in a partial order (X,
We consider data structures in the following and operations on data structures. In this context we have the physical data structuring object in mind and we consider operations over these data structures. Hence we will refer to "inputs" of such operations, which will be particular instances of the data structure under consideration. We remark that every input I has a size ηε
We briefly discuss identification up to order-isomorphism of input sets which plays a main role in Average-Case Time analysis. Typically there are infinitely many inputs corresponding to a given data structure for a given size. For instance, the infinite collection of all finite lists of size η over the natural numbers, i.e. the set
For data structures, such as lists and heaps, we use the following notation, where we work modulo identification up to order-isomorphic copies:
A multi-set is a finite set-like object in which order is ignored but multiplicity is explicitly significant. Thus, contrary to sets, multi-sets allow for the repetition of elements. Therefore, multi-sets {1,2,3} and {3,1,2} are considered to be equivalent, but {1,2,2,3} and {1,2,3} differ. We refer to the number of times an element occurs in a multi-set as the multiplicity of the element. The cardinality of a multi-set is the sum of the multiplicities of its elements. Each multi-set A of η elements has an associated set B={b1, . . . , bk} such that ∪A=∪B and where each element bi of B is repeated Ki times where 1≦Ki≦η and
It is clear that a multi-set A can be represented in this way as a set of pairs {(b1,K1), . . . , (bk,Kk)}.
In fact it will be convenient to adopt a slight generalization of this type of representation as our formal definition of a multi-set in the following. I.e. a multi-set is formally defined in this context as a finite set of pairs {(b1,K1), . . . , (bk,Kk)}, where each Ki is a natural number, referred to as the multiplicity of the element bi and where we do not require that the elements bi are pairwise disjoint. In case (*) ∀i,j. bi≠bj, we refer to the finite set of pairs {(b1,K1), . . . , (bk,Kk)} as a strict multi-set. We allow a more flexible approach in which we do not require (*) to hold since in practice some repetitions of an element b may occur in different contexts, e.g. as K repetitions in one context and L in another, in which case we chose to keep track of these repetitions separately as pairs (b,K) and (b,L) in the same multi-set rather than as a single pair (b,K+L) in the multi-set.
To keep track of the number of times that a particular output is produced, we will represent the range of the input-output function of a data structure operation as a multi-set.
For any data structure operation P we indicate the multi-set of its inputs by
It is clear that in case
Multi-sets are useful to represent sets of data that are uniformly distributed. A multi-set A={(b1,K1), . . . , (bk,Kk)} is called uniformly distributed iff ∀i, jε{1, . . . ,η}. Ki=Kj. It is clear that if A={(b1,K1), . . . , (bk,Kk)} is a uniform multi-set then we can simply use the simplified notation A={(B,K)}, which indicates that the multi-set A consists of K copies of the set B. In particular: |A|=K|B|. Each element of a uniform multi-set A with associated set B arises with equal probability of
We define a multi-sequence to be a multi-set for which the order of the elements is fixed. A uniformly distributed multi-sequence is a multi-sequence obtained by fixing the ordering of a uniformly distributed multi-set. It will be convenient to work with multi-sequences later on since, for implementation purposes, the order of the elements will be required in order to specify the application of data structure operations to these elements.
In order to formalize the notion of a "uniformly distributed data structure" obtained via "identification up to label-isomorphism", we will introduce the concept of a Random Structure in Section 4.
We recall the standard definitions of comparison based algorithms and of Worst-Case Time and Average-Case Time for comparison based algorithms. A comparison based algorithm is an algorithm for which every action during the code execution is determined by a comparison between two elements of the input data structure (e.g. [AHU87]). In particular, every assignment and every swap during the execution of the code is a direct consequence of a comparison between two elements. Most sorting and search algorithms fall into this class and traditional lower bound estimates apply in this context.
Convention 2 We will focus in what follows on measuring the number of comparisons made during the execution of a comparison based algorithm. This simplifies the presentation and is consistent with standard approaches such as [AHU87]. Of course one could fine-tune matters and take into account assignments and swaps, which falls outside the scope of the present paper.
For a comparison based algorithm P we define the enact time TP(I) on an input I to be the number of comparisons made by the data structure operation P during the computation of the output P(I). The notation TP(n) indicates the restriction of the function TP to the set
The Total Time of P for inputs from
The Worst-Case Time of P for inputs from
The Best-Case Time of P for inputs from
The Average-Case Time of P for inputs from
In order to denote an arbitrary measure, which can include any of the above, we use the notation
We observe that:
If the exact time of P is a constant C on the inputs from I then:
Of course, in case
The capacity to generate recurrences is particularly important for the Average-Case Time measure since, in general, the direct determination of the Average-Case Time via the formula
is no feasible. For instance, for the case of sorting algorithms where |
would require an excessive time in order to add the η! comparison times TP(I) for the inputs I of size n. This is clear by Stirling's approximation
The computation time would be too great, even for the relatively small input size of η=20. If on the other hand one has a recurrence expressing the Average-Case Time, this time can be determined for very large values of n. We will introduce a method, IO-compositionality, which will enable one to derive recurrence equations for the average-case time of compositions of our data structure operations.
The compositional treatment for time measures that are defined with respect to sets of inputs of a given size, needs a more refined type of bookkeeping via output multi-sets. This is captured by the notion of "IO-Compositionality".
Definition 3 Given a time measure
Lemma 4 The Total Time TP t is O-Compositional. The Worst-Case Time TP W and the Best-Case Time TP B are respectively lower and upper IO-Compositional.
Proof: Given P1, P2 arbitrary data structure operations and
For the Best-Case Time and the Worst-Case Time, we observe that for any input IεI clearly we must have that
from which the lower and upper IO-Compositionality for Worst-Case and Best-Case time follows.
Remark 5 The right hand-side of the lower IO-Compositionality inequality for the Worst-Case Time, TP
We will show that the Worst-Case Time TP W and the Best-Case Time TP B are in general not IO-Compositional, i.e. the semi IO-Compositionality inequalities can be strict in general. Secondly, we will verify that the Average-Case Time
We show that IO-Compositionality for Worst-Case Time and Best-Case Time can not be achieved in general, i.e. their semi IO-Compositionality inequalities are strict in general. Hence, as is well-known, the worst-case bounds in a Real-Time context are not exact in general. This is illustrated by the counter-example given below. A similar example can be constructed for the Best-Case Time.
The example displayed on the next page is clearly an artificial one. Yet it illustrates nicely the lack of control one has in guaranteeing IO-compositionality for the Worst-Case Time and (via a similar example) for the Best-Case Time. It is easy to see that this problem arises in many cases, where no apparent pattern seems available to obtain some compositional subclass of sufficient generality.
Proposition 7 The average-time measure is IO-Compositional, i.e. the following equality holds for any two data structure operations P1, P2, where P1 operates on an input multi-set I and produces the output multi-set
where the last equality follows from the fact that |
We introduce a formalization of the notion of a Random Structure. This formalization is new and will serve as a basis for the data structures. As mentioned in the previous section, a Random Structure can also be viewed as a formalization of a "uniformly distributed data structure" obtained through identification up to order-isomorphism.
We will define a Random Structure (Definition 10) as a set of labelings on a finite partial order. One could develop the theory in the more general context of directed acyclic graphs, but the lack of transitivity in this context would introduce an additional layer of technicality. Labelings are functions which assign to each element of the partial order a "label". For our purposes, it is convenient to consider labels that are natural numbers equipped with the usual order. One can of course work in general with a countable linear order as the set of labels. In particular, the data structures can incorporate labels that are words, real numbers etc. In the present paper, such a generalization involving labels from an arbitrary linear order can be achieved via minor technical modifications.
We use in the following the notation
A Random Structure will be defined as the set of all possible order-consistent labelings of a finite partial order (X,
We discuss one example at this stage: the data structure of lists. For lists of size η the identification up to order-isomorphism yields as usual the η! permutations over n elements. These can be incorporated as a Random Structure Aη over the discrete partial order which, when labeled in all possible ways from a finite set of labels, say from the set {1, . . . ,η}, results in the η! permutations.
Other examples of data structures can be incorporated such as Heap-Ordered-Trees and Heaps [AHU87]. A trivial and degenerate example of a Random Structure is the Random Structure over the linear order which allows for a single order-consistent labeling. This is interpreted as a data structure consisting of the sorted list.
We recall that Random Structures will serve as the fundamental notion of Data Structures. They will be used to represent the set of lists of a given size, the singleton consisting of the sorted list of a given size, the empty data structure, the set of heaps of a given size, etc.
We proceed with formal definitions. The first one defines our concept of a labeling, which is always order-consistent. We recall that
Definition 8 A labeling of a finite partial order (X,
Of course, it follows from the above definition that labelings are bijections.
Omitting the order in the following notations consists of a slight abuse of notation, which will not cause ambiguities in the paper. Let (X,
Finally we use the following notation:
Remark 9 It is quite evident that the greatest (least) label must occur at a maximal (minimal) element.
Definition 10 The Random Structure on a finite partial order (X,
Notation: We frequently denote a random structure
We remark that the definition of a random structure does not require the underlying partial order to be connected.
Remark 11 Random structures,
Moreover, for the purpose of time analysis, we will focus on data structures, referred to as Random Structures, for which the labels are pairwise distinct. This is however not an essential requirement. Any operation on data structures which extends the ones we give below to the context where labels are no longer pairwise distinct, allows for an average-time analysis estimation in a similar way.
It is easy to see that random structures allow one to incorporate traditional labeled data structures, including heaps, unordered lists, sorted lists, . . . , as long as the labelings respect the underlying order. We illustrate this in the next example.
In each part of the example, we display the Hasse Diagram of the given partial order on the left and the labelings on the right. In each case the underlying set consists of elements {
The random structure
The random structure
c) Consider the partial order (X,
d) Consider the partial order (X,
e) We denote the following four-element random structure by
The random structure
f) Finally, we remark that heaps can be represented as random structures over a partial order which has a tree as Hasse Diagram. Heaps of size η are denoted by
Similarly, Heap Ordered Trees in general can be represented in this way.
It is obvious that the cardinality of Random Structures over partial orders with n elements lies between 1 and η! included.
We introduce "floor" and "ceiling" functions for elements of partial orders. For a partial order (X,
Similarly, we define:
For a discrete subset Y of X, we define:
Given a labeling F with range
┌a┐=F(┌F −1(a)┐)
└a┘=F(└F −1(a)┘).
For a subset
Of course, we have:
For the labelings displayed in the example, we have that:
┌2┐={3,5},└2┘={1},└4┘={5},└4┘={1},┌5┐= and └5┘={2,4}.
We will define operations that transform a random structure
We introduce the notion of a refinement in the following. Random operations "refine" the original partial order in that the newly created partial orders of the resulting sequence have underlying sets Xi that are subsets of the original set X and have orders
Definition 14 Let R=
The operations typically transform random structures R into a refinement (R1, . . . , Rη) of R; more precisely they determine refining functions.
Notation 15 We use the following notation: U, referred to as the universe, is a countable list of variables, say U={uη|ηε
PO fin(U)={(X,
The set of all labelings over partial orders from POfin(U) is denoted by
Definition 16 A function φ:
Definition 17 In case we have determined a refinement (R1, . . . , Rη) of R, based on which we can establish that the function φ is refining on R, then we refer to φ in combination with this particular selection of a refinement as a representation for φ. Such a representation is denoted as follows: φ: R
The following definition formalizes the notion of Random Structure Preservation.
Definition 18 A function μ:
∀FεR i�|μ−1(F)∩
The function μ is called strongly RS-preserving if and only if η=1.
Remark 19 1) Note that since multiplicities are required to be non-zero, we obtain, following the notation of Definition 18, that: ∀iε{1, . . . ,η}�μ(
2) The definition of RS-preservation is more general than the informal use of randomness preservation in the literature. The informal use of randomness preservation only regards the preservation of the uniform distribution and does not deal with Random Structures. We capture uniform distribution preservation in case a random structure is mapped to a single random structure and no non-trivial multiplicity is involved (i.e. K=1). This is captured in our context by the notion of a strongly RS-preserving function with multiplicity 1. RS-preserving functions in our context, map a random structure to a multi-sequence of random structures.
Remark 20 It is clear that the definition of RS-preservation could be simplified in case the random structures R1, . . . , Rη have pairwise disjoint underlying partial orders. In that case the definition is equivalent to the following:
∀FεR i�|μ−1(F)|=K i.
Of course, one can always guarantee that the random sequence (R1, . . . , Rη) is such that the underlying partial orders are pairwise disjoint by identifying random structures with the same, i.e. order-isomorphic, underlying partial orders and by adjusting the multiplicities accordingly. We prefer to keep the more general version of RS-preservation at this time, since identification of order-isomorphic partial orders in practice may be costly.
The generalization is important and lifts the applications from rather straightforward reasonings on preservation of uniform distribution based on strong random structure preservation to more intricate applications of a wider scope.
Definition 21 In case we have determined a refinement (R1, . . . , Rη) of R with multiplicities K1, . . . , Kη with respect to some partition
Definition 22 A partition (
Remark 23 Strongly RS-preserving functions are (trivially) uniformly RS-preserving since their representations have partitions of cardinality one.
Notation 24 Typically, and with some abuse of notation, we will not mention the partition involved for RS-representations:
The motivation behind this shorter notation is that once our choice for the refining sequence, the partition and the corresponding multiplicities have been determined, we only need the resulting random sequence in order to determine the average-case time.
Definition 25 A random sequence is a finite sequence of pairs, ((R1,K1), . . . , (Rη,Kη)), each of which consists of a random structure R paired with a multiplicity K.
We extend RS-preserving functions from random structures to random sequences as follows:
Definition 26 (RS-preservation on a random sequence)
If ((R1,K1), . . . , (Rη,Kη)) is a random sequence and t is RS-preserving on each of the random structures R1, . . . , Rη, where
∀iε{1, . . . η}�μ:Ri
then we denote this by:
μ:((R1,K1), . . . , (Rη,Kη))
We say in that case that:
μ is RS-preserving on the random sequence ((R1,K1), . . . , (Rη,Kη)).
We omit the straightforward verification of the following two results.
Proposition 27 If μ: ((R1,K1), . . . , (Rη, Kη))
((R1 1,K1 1�K1), . . . , (R1 η
Lemma 28 The composition of RS-preserving functions on random sequences is RS-preserving.
For strongly RS-preserving functions, Proposition 27 yields the following immediate corollary.
Corollary 29 If μ: R1
Remark 30 Note that no zero-value problem arises with the above division since for every random structure R one has |R|≧1. Indeed, if R is the random structure over the empty set,—then |R|=1 where R consists of the "empty function".
Definition 31 Random structures that are the image of some discrete random structure Ak for a (strongly) RS-preserving function are called A-constructible (Atomic-constructible).
To illustrate a basic application of Corollary 29, we remark that the random structure
We introduce the notion of an isolated subset of a partial order. Isolated subsets have the following important property: given a Random Structure
The notion of an isolated subset will be useful to allow the extension of our operations from a definition on the random structure determined by an isolated subset of a given Random Structure to the entire Random Structure. Conversely, isolated subsets are useful to define a notion of projection of a given Random Structure to the Random Structure determined by the given isolated subset.
An informal definition of an isolated subset I is that I is a subset of the underlying set of a Random Structure for which the extremal elements (with respect to the restriction of the order to the set I) are the only exit and entrance points of the set I to related points in the complement, which motivates the choice of the adjective isolated. This is captured by condition 1 of Definition 32. Moreover, we require that every point that does not belong to the set I and is directly above a maximal (directly below a minimal) element of I must be directly above (directly below) every maximal (minimal) element of I, which is captured by condition 2 of Definition 32. We formalize this in the following definition.
Definition 32 Given a finite partial order (X,
An atomic isolated subset, or
Since a component of a partial order has no outside connections, clearly every component of a partial order (cf. Section 2.1) is isolated and thus any set of components of a partial order is isolated.
We consider a partial order with Hasse diagram as displayed below. The isolated sub set I is determined by the elements contained in the ellipse on the diagram.
The Hasse diagram below provides an example where the set {
We define the useful notion of completely connected subsets of a partial order and proceed to give an alternative characterization of a isolated subset.
Definition 35 Given a partial order (X,
The sets A and B are said to be completely connected (cc)
Remark 36 If A is completely below B then A and B are discrete sets and A∩B=.
We continue Example 33 below and illustrate the sets A=M(I) and B=┌M(I)┐ which are completely connected and the sets C=└η(I)┘ and D=η(I) which are completely connected. We remark that the sets A, B, C and D are discrete subsets.
Remark 37 If at least one of the sets A or B is empty then the pair A and B is completely connected.
Lemma 38 Given a finite partial order (X,
└I−η(I)┘⊂I and ┌I−M(I)┐⊂I 1
└η(I)┘ is completely below η(I) 3
M(I) is completely below ┌M(I)┐. 3
Proof: Exercise.
Remark 39 If I is an isolated subset of (X,
We illustrate Remark 39 via the Example 33, where the set I consists of three isolated components displayed below.
Finally, we define the result of removing an isolated subset from a given partial order.
We define the notion of a strictly isolated subset of a partial order. In order to do this, the notion of a seam is useful.
Definition 40 A seam of a partial order (X,
a) A is completely below B
b) A≠, B≠ and (A↓)∪(B↑)=X
In the example below the pair (A,B) forms a seam of the given partial order.
Comment: By condition b) and Remark 36 one has |X|≧2.
We leave the proofs of Lemma 42, Lemma 44 and Corollary 45 as an exercise.
Lemma 42 If (A,B) is a seam of (X,
Notation 43 If (A,B) is a seam of (X,
Lemma 44
Corollary 45 |
Definition 46 A strictly isolated subset I of a partial order (X,
a) └η(I)┘≠
b) ┌M(I)┐≠
An atomic strictly isolated sub set of a partial order is a strictly isolated subset for which the restriction of the order to this subset is the discrete order.
Notation 47 If (X,
Ā=┌M(A)┐↑ and A =└η(A)┘↓.
Lemma 48 Every strictly isolated subset of a partial order is isolated.
Proof: If (X,
Remark 49 The empty set , the set X, and every union of components of X are isolated since for each such set A: └η(A)┘=┌M(A)┐=.
The partial order displayed below has the set I={
Definition 51 Given a partial order (X,
Clearly we have that SI⊂I and AI ⊂I and ASI=SI∩AI.
As mentioned in the introduction to this Section, isolated subsets possess an important property in that the restriction of all labelings of a random structure to the isolated subset forms multiple copies of the Random Structure over this isolated subset. This is captured by Proposition 54 below. We first need the following technical lemma.
Lemma 52 In case I is an isolated subset of X we also have that:
In case I is strictly isolated we also have that:
Proof: We leave 1) and 3) as an exercise and sketch the proof for 2). To show 2), we consider the set consisting of the restrictions of the labelings of
Notation 53 Consider a random structure R=
We use the following notation: ≈ for the identity up to label-isomorphism.
Proposition 54 Let R=
Proof: We sketch the proof: 1) and 3) follow directly from Lemma 52 b) and c). 2) is an easy consequence of 1).
We illustrate these results on some basic examples below.
The isolated subset Y in the four element binary tree (X,
In the following example the strictly isolated subset indicated by the two elements contained in the ellipse. The restrictions of the labelings to this strictly isolated subset consists of K=2 copies of the random structure
Moreover, we have K=|
Finally, we present an example of a non-isolated subset Y of which the elements again are contained in the ellipse below. The restriction of the labelings to this subset do not form a number of copies of a random structure. Indeed, the restriction of the final labeling to Y, with labels 4 and 2 on Y, only represents one labeling of the newly created restricted discrete two-element partial order (Y,=), while the second labeling of (Y,=), with the labels 2 and 4, is missing.
The notion of an atomic isolated subset introduced in Definition 32 will be useful in defining the operation "random split".
An atomic isolated subset intuitively forms a discrete subset in a random structure for which any labeling, when restricted to this set, forms a set of pairwise free labels. i.e. the labels simply can be permuted on this set without violating the labeling condition. The following Lemma captures this idea. The proof of the following Lemma is a trivial exercise. In fact one can show that the two conditions stated in Lemma 56 are equivalent. The verifications are of a technical nature and we omit them at this stage since we will only avail of the implication below.
Lemma 56 Given a random structure
Remark 57 This fact enables one to easily determine, for two given elements of an isolated atomic multiset, what the probability is that the label of the first element is smaller than the label of the second element. Indeed, it is easy to see that these events are independent and that the probability is �. For atomic strictly isolated subsets I of a given random structure
whenever aε{F(I)|Fε
Proposition 58 1) I is strictly isolated
2) I= or Ī=
Proof: To verify 1), we show that in case I is strictly isolated, both L and I are strictly isolated. The converse is left as an exercise.
Assume that I is strictly isolated. Then:
a) └η(I)┘≠
b) ┌M(I)┐≠
If └η(I)┘=0 then we know that I=(└η(I)┘=)↓= and hence I is strictly isolated. Similarly Ī is strictly isolated in case ┌M(I)┐=. Thus we can assume that └η(I)┘≠ and ┌M(I)┐≠. We remark that in particular (*)I≠.
By a) and b) we obtain that: (└η(I)┘,η(I)) and (M(I),┌M(I)┐) each form a seam.
We verify that Ī is strictly isolated. The proof for I is similar.
Note ┌M(Ī)┐=┌M(┌M(I)┐)↑)┐=┌M(X)┐=
However └η(Ī)┘=└η(┌M(I)┐↑)┘=└┌M(I)┐┘=M(I) where the last two equalities follow from the fact that (M(I),┌M(I)┐) forms a seam.
Since by (*) we know that I≠, we obtain that M(I)≠ and hence └η(Ī)┘≠.
Hence, in order to verify that Ī is strictly isolated, it suffices to verify that (└η(Ī)┘,η(Ī) forms a seam. But this follows since we have verified above that └η(Ī)┘=M(I) and η(Ī)=┌M(I)┐ and since (M(I),┌M(I)┐) is a seam.
We proceed to verify 2) under the assumption that I is a subset which satisfies Ī=. The case where I= is similar.
We show that I strictly isolated implies that X−I is strictly isolated. The converse is shown in a similar way.
Since Ī=, we obtain that ┌M(I)┐↑= and hence, since I is strictly isolated, we know that X−I=I. By 1) we know that I is strictly isolated and hence X−I is strictly isolated.
Finally we state the following Lemma, leaving the proof as an exercise, which sheds some light on the relations between the notions of a seam, isolated and strictly isolated.
Lemma 59 The following statements are equivalent:
2) ∃I.⊂I⊂X,Ī= and I is strictly isolated.
3) ∃I.⊂I⊂X,I= and I is strictly isolated.
In case X is a component of (X,
4) ∃I.⊂I⊂X, I and X−I are isolated.
We will distinguish two types of RS-representations for RS-preserving functions, the contractive ones, which reduce the underlying set to a strict subset of this set, and the non-contractive ones, which leave the underlying set of a random structure unchanged.
Definition 60 An RS-representation μ:
The Extension Process states that it suffices to define non-contractive RS-representations on an isolated subset of the partial order of a given Random Structure and subsequently to extend these functions to RS-representations of RS-preserving functions on the entire Random Structure. For contractive RS-representations the Extension Process holds on condition that the extension occurs on a strictly isolated subset.
The Extension Process will be used to define three of the basic operations: the Random Product and the Random Split, which are non-contractive operations, and the Random Deletion, which is contractive. The fourth operation, the Random Projection, can be defined without the aide of the Extension Process.
As usual, with some abuse of notation, we will denote the restriction of the partial order
Notation 61 Ref (
The following definition extends the label-isomorphism
Definition 62 Given
Lemma 63 Definition 62 is sound, i.e., using the notation of Definition 62,
Proof: Let φεRef (
We remark that since refining functions are surjective,∀F′ε
To show that
where ∀iε{1, . . . ,η}.
The following lemma, which uses the notation of Definition 62, illustrates that the relabeling operator {circumflex over (Ψ)} preserves RS-representations.
Lemma 64 If
it suffices to remark that since
We now introduce an Extension Operator which extends a refining function defined on a random structure S, determined by an isolated subset of a given random structure R, to the entire random structure R.
Definition 65 Suppose that I is an isolated subset of (X,
The following lemma shows that Definition 65 is sound.
Lemma 66 Let Gε
We determine a representation for the extension Ext(G,I)(φ) of φ.
Then: ∀iε{1, . . . ,η}.
and Ext(G,I)(φ) is refining with representation:
Proof: We show that ∀iε{1, . . . ,η}.
Note that Ii is an isolated subset of (X,
We remark that {Fr
We verify that the function Ext(G,I)(φ) is refining. Note that
We use the notations of Definition 65 and of Lemma 66 in Theorem 67.
Theorem 67 (Extension Process) Consider a random structure
If a) μ is non-contractive or b) (μ is contractive and I is strictly isolated) and if
is RS-preserving then
Proof: To verify a), we consider a non-contractive RS-preserving representation of μ: μ:
Since μ is RS-preserving there is a partition
Since I is isolated we know by Lemma 52 1) that
We define the following collection of sets: for iε{1, . . . , n} we let:
We verify that the collection
We remark that μ is RS-preserving and hence surjective.
Thus, by Lemma 66, Ext(G,I)(μ) is surjective and:
This equality combined with (*) implies that ∀H ε
Part b) for contractive functions and strictly isolated sets follows by a similar argument.
Notation 68 We remark that the extension Ext(G,I) (μ) given by the Extension Process is independent of G and hence will be denoted in the following by: Ext(I)(μ).
In Section 5.6 we discuss two counter-examples illustrating that the condition "strictly isolated" can not be weakened to the condition "isolated" for the case of contractive representations.
In the following sub section we outline the fundamental data structuring problem as described in [MR98] and then proceed to present randomness preserving versions of the main operations involved for the case of random structures.
We focus on partial order data structures which allow one to incorporate all of the basic operations of the basic data structuring problem listed in [MR95] in the context of randomized algorithms.
We briefly discuss these operations below. We should point out that the following discussion is intended to be motivational. Indeed, the intricacies of randomness preservation will require some operations to be more restrictive than in a general context. We only present the operations since they form a nice summary of the most fundamental data structuring operations.
For the fundamental data structuring problem one is required to maintain a collection of sets of items so as to efficiently support certain types of queries and operations. Each item i is an arbitrary record indexed by a key k(i) drawn from a totally ordered universe. We assume that each item belongs to a unique set and that the keys are all distinct.
The operations to be supported in this context are:
Join(S1, i, S2) where iεS1∪S2: replace the sets S1 and S2 by the triple (S1′, i, S2′), where for all items j in S1′, k(j)<k(i) and for all items j in S2′, k(i)<k(j) and the union of S1 and S2 equals the union of S1′ and S2′.
We should point out that [MR95] presents these operations in a different simplified fashion. Indeed, the solution of the data structuring problem presented in [MR95] uses binary search trees. When operating on such trees one typically considers two sets S1 and S2 consisting of the elements "left" of the root, all of which have keys smaller than the root key and the elements "right" of the root, all of which have keys greater than the root key. We refer to two sets that satisfy this condition as a "pre-split pair". For pre-split pairs, the operations above can be formulated to start from a pre split pair of sets S1, S2 and end up with the same pair of sets S1, S2 rather than with an altered pair S1′, S2′. We generalized the operations to data structures where we assume that two parts S1, S2 of the structure are not necessarily pre-split.
The first operation, which concerns the creation of a new empty data structure (in the above case a set) we simply interpret in our context as creating an empty random data structure. This is taken care of in our context via the use of a constant indicating the empty structure. Since a join obviously is very similar to a split, from a set theory point of view, we will focus on finding RS-preserving versions for the second up to the sixth operation.
The operations listed in [MR95] however are not necessarily RS-preserving and are restricted to the context of trees. We will ensure that our data structure operations are randomness preserving and that arbitrary data structures can be incorporated. Random structures form the basic building blocks of random sequences, i.e. of the data structures, and consist of labeled partial orders. This approach allows for the inclusion of traditional data structures, including of course lists, heaps, etc. The operations are random product, random insertion, random deletion, random projection and a random split, each of which has been designed in a novel way to guarantee randomness preservation of the underlying data structures.
The random insertion can easily be inferred from the random product: it simply consists of the random product of a singleton random structure with an arbitrary random structure. Direct access to elements of a random structure will be restricted, with the exception of access via projections on a singleton isolated subset.
Comment: The operations introduced below can easily be extended to take more arguments than specified in their definition. The details are of a straightforward technical nature and have been omitted in the paper. We will restrict the definitions to the minimum number of arguments in each case.
Convention 69 In the following we will consider arbitrary label sets of natural numbers, i.e. we no longer require that label sets form an initial segment of the natural numbers.
Remark 70 We will typically first define the operations on partial orders, then define the operation on labelings and finally define the operation on a random structure. To generalize the operations we will use two extension results. We will use the Extension Process (Theorem 67) to allow the operations to be applied to isolated subsets of the partial order corresponding to a random structure. Finally, though we will not state this explicitely for each operation, we define the randomness-preserving extension of each operation, from random structures to random sequences, via Definition 26.
In order to define the random product, we first define the product of two finite partial orders. Then we define the product of two labelings and we extend this definition to sets of labelings. Finally, we define the random product on a random structure as a unary operation, which performs an operation on two sub structures of the given random structure and reproduces a new random structure.
Definition 71 Given two finite disjoint partial orders (X1,
The set X1
It is easy to verify that the partial order
If we consider the sets X1=
Clearly the sets X1 and X2 always form a pair of completely connected subsets (cf. Definition 35) of the product partial order (X1
We define the product of two labelings as a first step towards the definition of the random product of two random structures.
Let F1,F2 be labelings on finite partial orders (X1,
Let F1, F2 be disjoint labelings which are provided as inputs.
We define the product of the two labelings. To avoid technicalities, we assume in the following pseudo-code that the labelings F1 and F2 of which the product is taken are (implicitly) processed first to retrieve a new function F, consisting of the join of the labelings F1 and F2. The creation of F will be indicated in the final pseudo-code for the random product by the initial code line: F=F1∪F2, where we consider the graph union of these functions.
We will also assume the implicit generation of the restrictions of this function F, i.e. F
The pseudo-code to generate a labeling from F=F1∪F2 is specified below.
while └b┘ ≠ and b <
Push-Up (a,F)
while ┌a┐ ≠ and a >
As before, we will use Push-Down and Push-Up freely in the pseudo-code, without specifying which version we use since this is a matter of choice of implementation.
As usual we will define the operations on isolated subsets of a given random structure. We will show that the operations are randomness preserving for the case of strictly isolated subsets and then generalize to arbitrary isolated subsets via the Extension Process (Theorem 67).
We provide the pseudo-code for the Labeling-Product Algorithm where the inputs for the algorithm are the disjoint labelings F1 and F2. We denote the function F returned by the Labeling-Product algorithm as F1
F := F1 ∪ F2; while a := swap (a,b,F); Push-Down(b,F); Push-Up (a,F) Return F
Lemma 73 If F1 and F2 are disjoint labelings then F1
Proof: This follows via straightforward yet technically lengthy verifications from the pseudo-code of the random product algorithm. We omit the details.
In the example given below, we consider two labelings F1 and F2 for the partial orders displayed below and illustrate the steps involved in executing the Labeling-Product algorithm. We indicate the selection of labels of extremal elements by full circles and these elements occur swapped in the following picture. For each while loop execution, initiated by an original swap of labels of two extremal elements, the other pairs of elements to be swapped are linked in the picture via a double arrow (in dashed line display). These elements occur swapped in the following picture. The final picture illustrates the end result of the computation, i.e. F1
Definition 75 Let
is defined by:
The following result is important to obtain that the Random Product is an RS-preserving operation.
Proof: Consider two disjoint partial orders (X1,
We present a proof.
We view the execution of the labeling product algorithm as a series of swaps along chains of X1
In order to show the result, we assume that we have two labelings F1, F1′ of the partial order (X1,
We will display the labels on the chain determined by the swap sequence arising from the call to F1
[a1,a2, . . . , aη],[b1, b2, . . . , bk],
where (a,b) is the first pair which is swapped by the algorithm, aη=a, b1=b, the sequence [a1, a2, . . . , aη] consists of the labels in the labeled partial order (X1,
In the above, we allow the case where η=0 and k=0, i.e. no swap occurs.
Similarly, we display the labels on the chain determined by the swap sequence arising from the call to F1′
[a1′,a2′, . . . , aη′],[b1′,b2′, . . . , bl′].
where (a′, b′) is the first pair which is swapped by the algorithm, aη′=a′, b1′=b′, the sequence [a1′, a2′, . . . , aη′] consists of the labels in the labeled partial order (X1,
In the above, we again allow the case were η=0 and l=0, i.e. no swap occurs.
We remark that Ra(F1)=Ra(F1′)=
We show that a=a′. The case b=b′ is similar. The algorithm selects the maximal label a at depth 0 in the labeled partial order (X1,
We remark that this fact does not alter, even after the first two push operations in the algorithm have been run through a number of times. Inductively one can show that Ra(F1)=Ra(F1′) remains true. Indeed, in case a<b no swaps will occur and the result holds trivially. Otherwise, after the first series of swaps has happened for the first two while loops, we obtain that in Ra(F1), the label a simply has been replaced by the label b and in F1′ the same has taken place. Hence we preserve the fact that the ranges of the respective labelings coincide, which suffices to yield the desired property.
It follows by the fact that a=a′ and b=b′ at the start of each swap sequence, the number of non-trivial swap sequences induced by F1
Hence we can focus on the last swap sequences induced by F1
Consider these final chains along which the labels are swapped, i.e. the chain
[G1 −1(a1),G1 −1(a2), . . . , G1 −1(aη)],[G2 −1(b1),G2 −1(b2), . . . , G2 −1(bk)]
and the chain
[(G1′)−1(a1′),(G1′)−1(a2′), . . . , (G1′)−1(aη′)],[(G2′)−1(b1′),(G2′)−1(b2′), . . . , (G2′)−1(bl′)].
To show injectivity for the final swap sequences, it suffices that these chains must be identical.
Indeed, assume that these paths are the same, say a path denoted by P. Since F1
We claim that it is always the case that the swap sequences corresponding to b must be the same for G1 and G′1 and hence, by the above, the final swap operations form an injective operation.
We recall that since F1
We clarify the situation for both labelings H1 and H1′ in the following figure. In H1 the label b will be swapped with a label α while in H1′ the label b will be swapped with a label β.
Since after these swaps the labels of
We now obtain a contradiction since from labeling H1 it is clear that α<β while from labeling H1′ we obtain that β<α.
Hence we cannot have divergence of the path and the result follows.
Since the same argument holds for α, we obtain that both swap paths must be identical.
The proof can now be concluded by an inductive argument remarking that the same must hold for every pair of swap sequences, when run through in reverse order of their occurrence. Since on elements outside the swap paths, no labels are ever swapped, we obtain that F1=F1′ and F2=F2′.
Finally we need to verify that the label-product function is surjective. It suffices to verify that |
We remark that
We obtain the following immediate corollary.
Corollary 77 Let
In the example given below, we illustrate that the creation of the random product of labelings is an injective process. We do not display all cases, but restrict our attention to the case of a fixed set of labelings which can be used on the first partial order ({1, 2, 3, 4}) and a fixed set of labelings which can be used on the second partial order ({5, 6, 7}). It is easy to verify that the number of possible combinations of labelings for the given partial orders from the set of labels {1, 2, 3, 4, 5, 6, 7} is
which prevents a complete illustration of all cases. The first five combinations of pairs of labelings are displayed in bold design at the top of the following page, followed by the computation steps, while the next five combinations are displayed again on the next page in bold design, followed by the computation steps.
We define the binary random product below, which may be the first type of product that comes to mind, followed by the unary random product which is the one that will be used in the applications.
Definition 79 Let
Definition 80 Consider a random structure
We define the unary random product to be the function:
where ∀Fε
Theorem 81 Consider a random structure
Proof: By the Extension Process it suffices to verify that the random product μI
such partitions.
We provide an example of the unary random product.
Consider the Hasse Diagram of the following tree:
We display the eight labelings of the tree, where we selected the two leaves at the deepest level, i.e. χ1 and χ2, to form the atomic isolated subset I and labels for this set have been indicated as below.
We apply the unary random product to the isolated subset I={χ1,χ2} and we use the components I1={χ1} and I2={χ2}. The result is displayed below. The multiplicity involved is
Indeed, obtain two copies of a random structure, a first copy consisting of the labelings marked by (I), i.e. the labelings with odd indices, and a second copy consisting of the labels marked by (II), i.e. the labelings with even indices.
We first define a contractive version of the Random Projection, referred to as the strong Random Projection which takes a random structure and one of its isolated subsets as argument and restricts the labelings to this isolated subset, destroying the complement of this isolated subset in the process.
Definition 83 Let (X,
Definition 84 The strong Random Projection on an isolated subset I of a random structure R=
Next we consider the Random Projection which produces a copy of the restriction of a labeling to an isolated subset.
Definition 85 Let (X,
Definition 86 The Random Projection on an isolated subset I of a random structure R=
Theorem 87 Consider an isolated subset I of a random structure R=
In case I is strictly isolated, we have: K=|
With some abuse of notation we write the following:
The abuse lies in the fact that the resulting random structure is produced in addition to the original random structure, which is unchanged and which is not displayed in the above notation. Proj(I,R) is an RS-preserving operation where
In case I is strictly isolated, we have: K=|
Proof: These results follow from Proposition 54.1 and Proposition 54.3 respectively.
Remark 88 The relation "isolated subset" is transitive, i.e. if J is an isolated subset of a given isolated subset I of a partial order then J is an isolated subset of this partial order. Hence there is no need to apply the Extension Process for the case of the Random Projections.
We consider the example of a strong random projection on an isolated subset of the random structure
We illustrate the effect of a strong random projection on
copies of
We define the random split operation first on an atomic random structure
Definition 90 We define the random split operation on a discrete partial order (X,
For every ηε{1, . . . ,η} we define Ξχ to be the partial order obtained on X via the transitive reflexive closure of the relationX χ∪
The random split of the discrete partial order (X,
The partial order Ξχ is illustrated via the following diagram:
We illustrate the resulting sequence of partial orders obtained via a random split on the discrete four-element partial order (X,
The general definition of the random split operation requires a formulation in terms of random structures. Since a split involves an operation on an atomic isolated subset, we first discuss the result of carrying out a split operation on an atomic random structure,
We first define the random split operation on a single labeling of an atomic random structure
Pseudo-code for random split Splitχ(F) on a labeling F of
while u<v do
while F[χu]<a do u:=u+1;
while F[χv]>a do v:=v−1;
if u<v then swap(F[χu], F[χv],F)
Remark 92 Let
We define Splitχ(
In the following we will identify (for each ηε{1, . . . ,η});
G(χk)<G(χ) if k<η,G(χ)=aη and G(χl)>G(χ) if l>η.
It is easy to verify that any choice of χ will produce the same set of functions, i.e. ∀χ,χ′εX. Splitχ(
For every choice of χεX, we let
Remark 93 We remark that
Lemma 94 For all
1) ∀ηε{1, . . . ,η}. Splitχ
2) |Splitχ −1(G)∩
Proof: To show 1), we remark that the inclusion from left to right follows from the definition of the pseudo-code of the Split operation. To show the converse, let GεR=
To show 2), we remark that for every G, G′ ε
Proposition 95 For all
Proof: We remark that
From Proposition 95 and the Extension Process (Theorem 67), we obtain (using the notation of Theorem 67):
Theorem 96 Let R=
where ┘iε{1, . . . ,η}.
The following example illustrates the effect of a split on an atomic strictly isolated subset I. This subset has no degree of freedom on the labels for the set X−I. Indeed, X−I consists of the maximum and the minimum of the underlying partial order and hence there is a unique label assigned to each of these elements. For such an atomic strictly isolated subset, the effect of a split is essentially the same as the effect of a split on atomic random structures
We illustrate the effect of a split on the following partial order (X,
We consider the following enumeration of the elements of I: ∀iε{1, . . . , 4}. yi=χi+1. After performing the split on I={χ2, . . . ,χ5}, we obtain the sequence:
We continue the example and consider the set of labels
We consider the atomic isolated subset I of
The split of the partial order (X,
Finally, we display the result of the operation Ext(I)(Split)
Clearly η=4 and η=3. Thus
copies of the random structure
The following example illustrates the effect of a split on an atomic isolated subset I of a given random structure
We consider the same tree and random structure over this tree as in Example 82. After performing a split, Ext(I)(Split)(R) determined by the atomic isolated subset I enumerated by Ψ1=χ1,Ψ2=χ2, and by the Extension Process, Theorem 67, we obtain a set of labelings for a new partial order as displayed below.
We obtain two copies of a random structure indicated by (I) and (II) above. In fact, the multiplicities determined by the Extension Theorem are:
I.e. the split operation, as defined, does not automatically identify these random structures. Of course this identification can be achieved via a simple adaptation of the definition of the split operation if desired or during the time analysis later if this turns out to be useful. In that case would obtain the same end result as for the unary random product discussed in Example 82.
In this subsection we introduce two important data structure operations
Remark 99 We chose to implement the Deletion operations such that the label a to be deleted will be returned by the operation. The element χ labeled by a however will be removed from the partial order under consideration. It is easy to see that the operations could be defined in an alternative way such that the element χ is actually kept after deletion as a minimum of the partial order, where a is kept as the label of this new minimum. We prefer to interpret the deletion operation in the usual way, i.e. leading to the removal of an element.
Definition 100 Consider (X,
We leave the straightforward proof of the following lemma to the reader.
Lemma 101 Let (X,
We define the Random Deletion operations on a partial order.
Definition 102 Given a finite partial order (X,
We recall that the greatest (least) label must occur at a maximal (minimal) element (cf. Remark 9).
Definition 103 We define the operation of deleting the largest label a from a given labeling F as follows: DelM(F)=F
We state the following RS-preservation result for the operation DelM which returns a sequence of random structures, each of which has multiplicity 1. Similar results hold for the operation Delη.
Proposition 104 If
2) DelM
Proof: Exercise.
We illustrate the deletion of the minimum label via Delm on the following example.
We circle the label 1 to be deleted.
The effect of deleting the label 1 is given by:
Hence we obtain two random structures, consisting of the labelings from the set {2, 3, 4} of a connected V-shaped partial order and of a partial order consisting of a two point component and a single element component.
The effect of deleting the label 2 on the other hand does not yield a sequence of random structures. This is explained by the fact that the minimum label always has to occur at a minimal element. The label 2 does not and for instance occurs once at a maximal element. If we were to delete the label 2 from each of the five labelings, the result would be the following set of labelings, which do not form a sequence of random structures:
The operations of deleting an extremal label will take as inputs the labelings from a random structure, where these labelings are stored in a variable X. Hence the operations will be denoted as: DelM(X) and Delη(X) for the deletion of a maximal label and a minimal label respectively. These operations remove, for any given labeling, the extremal element from the partial order corresponding to the largest label. The operations return this largest label and replace the random structure by a new sequence of random structures as described above.
We consider here the case of labels for elements which are not necessarily extremal. It is clear that the deletion of an internal label cannot simply occur by removing a label from all possible labelings where connections with other elements are deleted in a similar way as for the deletion of an extremal label. The same problem arises as for the deletion of the label 2 in Example 105.
In order to delete an arbitrary label a from a random structure, for a given labeling F, we proceed as follows in two steps. First we percolate an internal label to a position where it becomes a label of an extremal element. Then we carry out the deletion of the newly created extremal label as described in the previous section.
In the following we will assume that the label a to be deleted actually occurs as a label in the random structure.
Percolation of a label a is carried out as follows:
Search for the index i of the element χi with label a. This search can start for instance at the minimal (or maximal) labels, exhaustively searching labels at every level until the label in question is found.
We sketch two methods to remove the label, via downwards or upwards percolation, each of which can be applied in our context.
We describe the process of percolating an element downwards.
Here we replace the value of a by a value less than any label from the labeling F under consideration. This value is only a technical aid and is indicated by a−. The label a−, which will become a part of the given labeling, is then pushed down in the usual way, i.e. the process is exactly the opposite as in the definition of
The label a− is systematically swapped with the largest label of among the elements which are immediately below the element labeled with a−, in case there are at least two elements immediately below the given element, or with the label of the single element immediately below the element labeled with a− (depending on which is the case) until label a− becomes the label of a minimal element. Of course, in case a− was already a label of a minimal element, no swaps are necessary.
Remark 106 The above distinction between more than one element and a single element immediately below a given element means that in practice the algorithm will need η−1 comparison in case there are η≧2 children below the node under consideration (in order to determine the maximum label of the children) and, at first glance, it would appear that no comparisons need to be made in case of a single child below the node under consideration. Indeed, in case of a single child, we can immediately perform a swap since the parent node is labeled with a− which by definition is smaller than the label of the unique child. However, in practice one also needs to determine whether a parent has one or more children, which inherently involves a comparison. In order to obtain a more fair representation of cost, we will assume in the following that heaps are full binary trees, i.e. every parent has exactly two children, some of which may be the empty tree. A leaf then is a node for which both children are empty. In case of a single child, one comparison will be counted to determine this situation. We will return to this issue in the analysis of Percolating Heapsort.
Next we describe the process of percolating an element upwards.
We can alternatively replace the label of a by a value which is larger than all labels from F, denoted by a+ and push-up the label in a similar way.
Finally, the operations Del and
To define the operations on labelings, we consider two inputs: an index k and a labeling F.
We can now define the deletion of an arbitrarily selected label of a given labeling, which generalises the deletion of extremal labels.
Del(k,F) is defined to be the operation of percolating the k-th smallest label a downwards as a label a− followed by the deletion of the extremal element labeled by a−. The output returned is the deleted label and the random structure is updated to be the newly obtained sequence of random structures, i.e. a sequence of partial orders all labeled from the same set of labels to form the random structures. The definition of
We note that in contrast with the deletion operation which generates a sequence of random structures, the percolation operation only generates a single random structure.
For deletion operations we set aside in the definition of data structure operations a countable set of storage variables U, V, W . . . which are used to make allocations of the deleted labels to a singleton random variable, i.e. a random variable of size one. These can then be inter combined of course with the join operation.
The Delete operations hence return the deleted label and update the random structure to a new sequence of random structures as described above.
We illustrate both deletion processes in the following example.
Consider the partial order (X,
For a given set of labels
To continue the example, we illustrate the result of removing the second smallest label, which for the case of our example is the label 2, from the above random structure via the
We first illustrate the
We illustrate below the effect of removing the second smallest label via the
We illustrate the effect on the next four labelings.
Hence we obtain a sequence of three new random structures, identified by (I), (II) and (III), each of which is labeled from the set of labelings {1, 3, 4, 5}. Of course, one can see that (II) and (III) are identical. Hence they can be identified during an analysis of the deletion process. Since however the copies created in this way depend on the structure of the original partial order, we will not identify the copies at this stage and treat each as a partial orders would require too much time in general. Later on, in a complexity analysis of an algorithm involving a deletion process, if needed, we can make the necessary identifications during the set up of the recurrence equations depending on the partial order under consideration.
Removing label 2 via the Del method:
We only illustrate the end result which consists of a single new random structure with an extra singleton random structure V labeled with 2:
The following result states that the Deletion operation is RS-preserving. The proof is similar to (and essentially contained in) the proof of the RS-preservation of the Random Product since both operations are based on the push-down/push-up operations. Hence we will not include the proof here.
Theorem 108 Let R=
where a is the k-th smallest label of
Remark 109 We remark that both deletion operations transform the empty Random Structure to .
As for the previous operations, all versions of the random deletion can be extended via the Extension Process (Theorem 67) to isolated subsets and finally extended to arbitrary random sequences via Definition 26.
We provide two counter-examples demonstrating that the Extension Process can not be generalized to isolated subsets for the case of contractive operations.
We illustrate that the deletion operation on isolated subsets does not allow for an extension as in The Extension Process (Theorem 67).
Consider the partial order given in Example 12f) and the corresponding random structure
Consider the same random structure
Uniformly RS-preserving functions have been introduced in Definition 22. By Remark 23 and the fact that the Random Product and the Random Projection are strongly RS-Preserving, it follows that these operations are uniformly RS-preserving. We leave it as a straightforward exercise to verify that the Random Split is uniformly RS-preserving. However the Random Deletion is not uniformly RS-preserving. This can be readily verified from Example 107. If one applies the Random Deletion operation DelM to each of the eight labelings displayed in Example 107, a partition yielding an RS-representation of this operation necessarily constitutes of three components: one component of cardinality 2 and two components of cardinality 3. This follows from an inspection of the three partial orders corresponding to the Random Sequence which has been obtained as the result of the deletion.
In the following we state the results for RS-preserving data structure operations.
Remark 112 1) Let P be a data structure operation and R and R′ two random sequences, where R=[{right arrow over (R)}p,{right arrow over (K)}p] and P:[{right arrow over (R)}p,{right arrow over (K)}p]→R′. As usual, the exact time of P on an input labeling F, denoted by TP(F), is the total number of comparisons made by P during the execution of the data structure operation P for the input F. We will indicate the average time for a data structure operation by