Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-10-06
2001-10-30
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06311188
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to computer systems. More particularly, the present invention relates to array element selection with reduced memory consumption.
2. Description of the Related Art
In software applications, data is typically manipulated through the use of various data structures. The data structures selected for a particular software application must provide adequate memory as well as permit efficient retrieval of the data during execution of the application. By way of example, arrays are often used when a predetermined number of data elements are to be processed.
Often, array elements are stored in a predetermined order and are therefore processed consecutively. However, under a variety of circumstances, processing of each array element in an alternate order is preferable. By way of example, each array element may correspond to a particular software process. It may therefore be desirable to change the priority of one or more processes through selecting each process, or array element, in the desired priority order. As yet another example, it may be desirable to process the array in a random order.
When elements in an array are not processed in a consecutive order, it is necessary to maintain a record of the elements that have been selected. Conventional methods typically require the allocation of a second array data structure. By way of example, a corresponding element in a second array of boolean values may be flagged when the array element is selected. As yet another example, a second array or equivalent memory space may be allocated to store each selected element in the array.
Allocating duplicate memory space to process a single array results in inefficient use of available memory. This is particularly problematic in systems with limited data storage space. By way of example, memory space is limited in applications implemented in firmware or embedded systems. Accordingly, it would be desirable if each element in an array could be processed in a non-consecutive order without using a second array or equivalent memory space.
Prior to processing an array, the elements in the array are commonly sorted. One standard sort algorithm that may be used to sort array elements is the “bubble sort” algorithm. According to the “bubble sort” algorithm, adjacent array elements are compared and swapped if they are not in the correct order. In this manner, each pair of adjacent elements is compared and swapped until the smallest (or largest) element “bubbles” to the top of the array. This process is repeated until the entire array is sorted. Thus, since numerous passes are required and multiple pairs of elements must be compared in order to sort the array, this algorithm is inefficient and therefore impractical to implement in most applications. Moreover, this algorithm does not permit an array to be processed and sorted according to any selection criteria. Accordingly, it would be desirable if an array could be sorted and processed according to any order such that each element may be selected and processed without duplication.
SUMMARY OF THE INVENTION
The present invention provides methods and apparatus for reordering and processing elements in an array in a non-consecutive order. This is accomplished through swapping each selected array element with an unselected array element. Accordingly, each array element may be reordered upon selection and processed.
According to one aspect of the present invention, a method for processing elements in an array is disclosed. One of the plurality of elements is selected. The element may be selected according to any order, such as a specified priority order or a random order. The selected element is then swapped with an unselected element in the array. This may be accomplished through separating each selected element from each element that remains to be selected. The selected element may then be processed. Alternatively, the method may be used to reorder the entire array which may then be processed according to the order of selection.
The present invention permits reordering and processing of array elements according to a specified order. This may be accomplished through swapping each selected element with an element that remains to be selected. Accordingly, memory utilized during reordering and processing of the array is minimized.
REFERENCES:
patent: 5621908 (1997-04-01), Akaboshi et al.
patent: 5704057 (1997-12-01), Cho
patent: 5806064 (1998-09-01), Garza
patent: 5857207 (1999-01-01), Lo et al.
Lippman, “C + + Primer”, Jul. 1989, pp. 47-49.*
Edward M. Reingold et al., “Transposition Sorting”, 1977, Combinatorial Algoritms, Theory & Practice, p. 283-285.
Jerry M. Rosenberg, Jun. 1987, Dictionary of Computer Information Processing & Telecommunications, 2ndEdition, p. 66.
Alfred V. Aho et al., “3.2 Radix Sorting”,Jun. 1974, The Design and Analysis of Computer Algorithms, pp. 77 & 102.
Beyer Weaver & Thomas
Black Thomas
Jung David
Sun Microsystems Inc.
LandOfFree
Method and apparatus for element selection exhausting an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for element selection exhausting an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for element selection exhausting an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2556534