Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa
The array is one of the most widely used data constructs. Because of its
vast utility, specialized arrays with unique properties become important.
A constant time array has the property that initialization (constructor),
finalization (destructor), and random access are all constant time (O(1))
operations. For this project, an additional property was included; this
would be a dynamically bound array. Because of this dynamic bounds
property, I will use the Set_Bounds operation and the
constructor interchangibly.
For most array implementations, the constructor is implemented in one of two ways:
The first possibility is that each element of the array is allocated memory and initialized. This method takes linear time, O(n), and thus for larger arrays and for larger element types, this constructor time can quickly become non-trivial. The Array currently in the RESOLVE Catalog is implemented with this method.
The second possibility is to allocate memory for the array, but leave all the elements uninitialized. This method is quite unstable because it relies on the client of the array to make sure that each element of the array is properly initialized. It is likely that the client will initialize every element upon constructing the array.
A constant time array with the previously mentioned properties illustrates the space vs. time trade-off. In order to give the array its constant time properties, extra memory overhead must be allocated. This memory overhead is significant, but not unreasonable.
A [much] more complete treatise on this subject can be found in the paper by Weide and Harms, Efficient Initialization and Finalization of Data Structures: Why and How, OSU-CISRC-8/89-TR11. The rest of this page depends on having a thorough understanding of this document.
The dynamically bound property of this array had an interesting consequence regarding the destructor. By following the example in the Weide paper, the destructor simply puts the array in a history of previous lives. This method works well for statically bound arrays, but may be undesirable for dynamically bound arrays. This is because upon putting the dynamically bound array into history of previous lives, the only [obvious] way that that array will ever be reused is if the array's client happens to set the bounds of an array with exactly the same length. Depending on the application, this circumstance may or may not be likely. Assuming the worst case, client never uses the same size of array twice, the history would grow into a huge wad of unused memory. This behavior could easily be labeled as unacceptable. One partial solution to this problem would be to reuse any array in the history that is greater than or equal to the size of the array to construct. Here is an example:
Let's say the client initializes arrays of size 100, 200, and 1000. The client then destroys these three arrays. So now the history contains memory for 100, 200, and 1000 element arrays. The client now wants to make a new array with a size of 500. Instead of allocating an entirely new chunk of memory, we could partially reuse the 1000 element array from the history. This method seems better than allocating brand new space for a 500 element array.
A better solution would be one that could more fully reuse the historic arrays. I have not explored any further possibilities.
The rest of the scheme described in the Weide paper is entirely applicable to this array. Use of the Time Stamp and Validation helper arrays is applicable. Additionally the algorithm to determine if an array element has been accessed will work.
An implementation for the dynamically bound constant time array has yet to be completed.