JPH04127321A - Sorting system by count classifying method utilizing relative key - Google Patents

Abstract

PURPOSE:To decrease the hardware quantity and to sort a large quantity of records in order of a key value at a high speed by executing sorting by a count classifying method utilizing a relative key, and setting a counter area to one. CONSTITUTION:Only one counter 4a is provided, and for instance, a key value of a record inputted to the beginning of an input buffer 1 is set as a reference value, and a difference between the key value of the record of the reference value and the key value of each record is calculated as a relative key = (the key before conversion) - (the key of the reference value). As a result, when its relative key is 'negative', '1' is added to the counter 4a, and when the relative key is 'positive' or '0', a processing for leaving the value of the counter 4a as it is executed to all records stored in the input buffer 1. Also, it is repeated that the record having the reference key is skipped and transferred in the weak direction by its number. In such a way, sorting can be executed at a high speed, and also, the hardware quantity is curtailed, and the processing of many records can be executed.

Description

[Detailed Description of the Invention] [Summary] Regarding a sorting method based on a count classification method using relative keys, the present invention provides a method for sorting a large number of records in the order of key values with a small amount of hardware and at high speed. The system is equipped with an input buffer and an output buffer for storing a plurality of records, a work area for the plurality of input records, and a counter area for ordering each record. In order to sort the records in the order of their key values and store them in the output buffer, only one counter area is provided, and a specific record is Set the key value as the standard value, set that key value as '0゛, and set the relative key that is the relative value of the key of the above standard value to the key value of other records as relative key = (before conversion) The relative key of each record is calculated as (key) - (key of reference value) and stored in the above work area, and the relative key of the stored work area is "
If it is "negative", add "1" to the counter area, and if the relative key is "positive J" or "0", repeat the process to leave it as it is, and all records in the input buffer are added. When the process is finished, the record set as the reference value above is transferred to the skipped location of the "empty" output buffer by the value set in the counter area above, and then the record is sorted. .

[Industrial application field]

The present invention relates to a sorting method using a count classification method using relative keys.

Recently, data processing by computer systems has been carried out in various fields, and when the data consists of a large number of records, it is sorted using specific information in the records as a key.

In this case, it is required to be able to sort at high speed with as little hardware (for example, memory) as possible.

[Prior art and problems to be solved by the invention] FIG. 2 is a diagram explaining a sorting method based on the conventional count classification method, in which (a) shows an example of a Nordonia configuration;
) to (b4) schematically show a sorting method based on the count classification method.

When sorting multiple records using the count classification method, (a) as shown in the figure, input buffer 1, output buffer 2, and input record work area 3 are used.
and a counter area (hereinafter sometimes referred to as a counter) 4 for assigning the order of each record.

Below, the procedure of sorting method using count classification method (bl
) to (b4).

1) First, set the value of counter 4 to 0, enter the key value (8") of the first record (record 1) into work area 3, and point to input buffer 1. Do nothing other than that. (See figure (bl)) 2) Input the key value of the next record into the work area 3,
Check the key value of the record that has already been input. The inspection will be conducted according to the following rules, and based on the results,
Adjust the value of counter 4.

(b) When the key value of the record that has already been input is smaller than the key value of the latest record (stronger as a key value), add 1 to the counter 4 of the latest record.

(b) When the key value of the record that has already been input is larger than the key value of the latest record (weak as a key value), add 1° to the counter 4 of the record that has already been input.

3) Repeat the process in 2) for all records input to the input buffer 1 (records 1 to 4 in this example).

To explain with a specific example, when the key value ('3') of record 2 is input into the work area 3, the above-mentioned check is performed against the key value ('8') of record I that has already been input.

The key value of the entered record 1 is the latest record 2
is weaker than the key value (specifically, the key value is larger), so according to the rule (b) above, °1" is added to the counter 4 of the input record, and as a result, the counter 4 becomes (
b2) As shown in the figure.

Next, when the key value (°2”) of the latest record 3 is input into the work area 3, the above-mentioned However, as a result of following the rule (b) above, the values of counter 4 of each record 1, 2.3 are "2", "1", "
0”.

Next, the key value ('7') of the latest record 4 is input into the work area 3, and the above inspection is performed between the key value of record 3 and each key value of records 1 and 2 that have already been input. If it is done, according to the above rule (b) with record l,
Between records 2 and 3, as a result of following the above rule (a), the value of counter 3 of record 1 becomes "2°→"3', and the value of counter 3 of record 2°3 becomes that superior. 4's counter 3 becomes "r+1+1.2", resulting in the result as shown in figure (b3).

4) When the above inspection of the key values of all the records input to the input buffer 1 is completed, transfer them to the output buffer 2 at a position that is, for example, "l" larger than the counter value of each record. (( b4) See figure) Tweet the above process to all records to be sorted,
Example Eva, input buffer Iterate with the number of records in 1 as a unit.

When sorting is performed using the conventional counter classification method described above, the same number of counters 4 as the input buffer 1 is used.
The problem is that records cannot be transferred to the output buffer 2 until all the records input to the input buffer l have been inspected, and the sorting procedure requires There was a problem in that it was necessary to execute an instruction to compare the key values between the two, which took time.

In view of the above-mentioned conventional drawbacks, the present invention provides a method for sorting a large number of records in the order of key values with a small amount of hardware and at high speed when sorting is performed using a count classification method using relative keys. The purpose is to capture and provide information.

[Means to solve the problem]

The above problem can be solved by a sorting method based on a count classification method using relative keys configured as follows.

An input buffer and an output buffer for storing a plurality of records, a work area for the plurality of input records, a counter area for ordering each record, and a key for the records stored in the input buffer. This method sorts the values in order of value and stores them in the output buffer. Only one counter area is provided, and the key value of a specific record is sorted in the order of values and stored in the output buffer. Set as the reference value,
Let that key value be °0゛, and for the key values of other records, use the relative key that is the relative value to the key of the above standard value, relative key = (key before conversion) - (key of standard value) Calculate and store the relative key value of each record in the above work area, and if the relative key of the stored work area is "negative",
Add °'1' to the above counter area, and the relative key becomes "
If the value is ``correct'' or ``0'', the process is repeated, and when it is completed for all records in the input buffer, the ``free'' area is filled by the value set in the counter area (4a). The configuration is such that the record set as the reference value is repeatedly transferred to the skipped location in the output buffer for sorting.

[Effect]

That is, according to the present invention, the input buffer is provided with an input buffer and an output buffer for storing a plurality of records, a work area for the plurality of input records, and a counter area for ordering each record. To sort the records stored in the input buffer in the order of their key values and store them in the output buffer, a single counter is provided, for example, the key value of the record input first in the input buffer is used as a reference. As a value, calculate the difference between the key value of the record of the reference value and the key value of each record as relative key = (key before conversion) = (key of reference value), and if the relative key is "negative" If so, add '1' to the above counter, and if the relative key is "correct" or "0", perform a process on the input buffer that makes the value of the counter its superior. Perform this for all stored records.

Through this process, if there is a record with a stronger key value (specifically, a smaller key value) than the reference key, the number of records will be counted in the counter, so the record with the reference key will be counted. Sorting can be performed by repeating the process of skipping and transferring in the weaker direction by that number.

Furthermore, in this sorting method, the operation between records is not a comparison operation in the conventional count classification method, but a simple subtraction, so the sorting can be performed at a correspondingly high speed.

Also, the counter has only one counter for one set of input buffers.
It is possible to reduce the amount of hardware and process a correspondingly large number of records. In addition, this count classification method is an internal sorting technique that reads all input records into the input buffer and sorts them (that is, a technique that reads all input records into the input buffer and sorts them). When the relative keys of all other records are calculated for the first reference record input into the input buffer, the reference record can be transferred to the output buffer, and the empty input buffer is Since it is possible to input a subsequent new record, it is necessary to move the record and create a key, that is, input the new record into the input buffer, the key value of the record,
Alternatively, the process of transferring the relative key value to the work area and pointing to the input buffer can be performed in parallel. As a result, in the so-called external sorting technique, which is performed when there are more input records than the input buffer and the above internal sorting technique cannot be used, when generating a string that is the sort result for the input buffer, the main The effect of being able to utilize the count classification method of the invention is obtained.

〔Example〕

Embodiments of the present invention will be described in detail below with reference to the drawings.

FIG. 1 is a diagram showing an embodiment of the present invention, (a)
shows a configuration example, and (bl) to (b6) schematically show the sorting operation by the count classification method of the present invention.

The present invention includes an input buffer 1 and an output buffer 2 for storing a plurality of records, a work area 3 for the plurality of input records, and a counter area 4a for ordering each record. Records stored in input buffer 1 are sorted in order of key values and output to output buffer 2.
In order to store data in the input buffer 1, only one counter area 4a is provided, and the key value of a specific record is set as a reference value for a plurality of records input to the input buffer 1, and the key value of the specific record is set as a reference value. Set the value to °0, and calculate the relative key that is the relative value to the key of the above standard value for the key value of other records as relative key = (key before conversion) - (key of standard value) Then, each record is stored in the work area 3, and if the relative key of the stored work area is "negative", "1" is added to the counter area 4, and the relative key is "positive j". , or if it is "0", repeat the process and when it is completed for all records in the input buffer l,
Only the value set in the counter area 4a above is "empty"
A means necessary to carry out the present invention is a means for sorting by repeatedly transferring the record set as the reference value to a skipped location in the output buffer 2 of the above. Note that the same reference numerals indicate the same objects throughout the figures.

Hereinafter, a sorting method based on the count classification method using relative keys according to the present invention will be explained with reference to FIG.

In the present invention, as shown in FIG. (a), an input buffer 1, an output buffer 2. A work area 3 for storing key values of input records and only one counter area (counter) 4a are provided.

(1) First, set the value of the counter 4a to 'O°, and use the key value of the key part of the first record l as the reference value of the relative key.
The key value is stored in the work area 3 and points to the input buffer 1 where the first record is stored. (
(See figure (bl)) (2) Using part of the key of the next record 2 and part of the key of record 1, which is the reference value above,
A relative key is generated using the formula: relative key - (key before conversion) - (key of reference value) and stored in the work area 3. (See figure (b2)) (3) At this time, the relative key stored in the work area 3 is "
If the relative key is "negative", the counter 4a is set to +1'; if the relative key is "positive" or "0", the counter 4a is left as is.

(4) The processes in (2) and (3) above are performed on all records stored in the input buffer 1 (in this example,
Perform this for records 1 to 4). ((b3), (b
(4) Refer to the figure) (5) When the above processing is completed for all records, the output buffer 2 becomes empty by the value of the counter 4a.
is skipped and the record (record 1) set as the reference value is transferred to that location.

This is because the value of the counter 4a indicates the number of records that have a stronger key value (specifically, a smaller key value) than the record that has the key value that is the reference value. . (See figure (b5)) (6) When the transfer of the first record 1 is completed, set the second input record 2 as the record with the next reference value, and set the value of the counter 4a to "0". , repeat the above (2) to (6). (See figure (b6)) Transfer the last record (record 4 in this example) to the vacant location at that time, and transfer it to the input buffer 1.
The sorting process for records 1 to 4 stored in .

If the number of records to be sorted is greater than the number in the input buffer 1, the first record of the next block (in this example, , record 5~), and in the first record, enter that key value, and in subsequent records,
Generate a relative key using the first record of the block as a reference value, store it in the work area 3, and repeat the adjustment of the counter 4a as described above. When the input buffer is full, Sorting is performed by repeatedly transferring the record of the reference value to the output buffer.

When all the sorting results (called strings as mentioned above) generated by this repeated process have been collected, the first record of each string is extracted in the order of generation.
By rearranging and generating one string, it is possible to sort more records than the number of input buffers l. This sorting technique is referred to as an external sorting technique, as described above.

As described above, the sorting method based on the count classification method using relative keys of the present invention can also be used to generate strings for external sorting techniques.

〔Effect of the invention〕

As explained above in detail, the sorting method based on the count classification method using relative keys of the present invention is different from the conventional count classification method in which one counter area (counter ), whereas by using a relative key, only one counter area is required, and that much more records can be processed. Furthermore, although the count classification method is an internal sorting technique, by introducing a relative key, the record used as the reference value is moved to the output buffer at the time when relative keys are created for all remaining records. Therefore, it is possible to move the record, input the first record of the next block into the input buffer, and
Key creation such as setting the key value of the record and setting the relative key can be performed in parallel in the work area. Therefore, as described above, it is possible to utilize the sorting technique based on the count classification method using relative keys of the present invention in string generation using the external sorting technique. Furthermore, by using relative keys, the number of comparison instructions required in the conventional count classification method can be minimized, and the sorting execution time can be reduced.

[Brief explanation of the drawing]

FIG. 1 is a diagram showing an embodiment of the present invention. FIG. 2 is a diagram illustrating a saw using a conventional count classification method. It is. In the drawing, 1 is an input buffer, and 2 is an output buffer. 3 is the work area. 4.4a is a counter area (counter). are shown respectively. Input buffer work area Counter area Output buffer (b3) Input buffer work area Counter area output buffer (b4) Figure (Part 2) Input buffer A1Yiβ11 area (a) Input buffer work area (bl Input Buffer work area (b2: Counter area output buffer Counter area output buffer Counter area output buffer

Claims (1)

[Claims] An input buffer (1) and an output buffer (2) for storing a plurality of records, a work area (3) for the plurality of input records, and a counter area for ordering each record. (4a), the records stored in the input buffer (1) are sorted in the order of key values and stored in the output buffer (2);
Provide only one a), set the key value of a specific record as a reference value for multiple records input to the input buffer (1), and set that key value as '0'. , for the key values of other records, calculate the relative key, which is the relative value of the key of the standard value above, as relative key = (key before conversion) - (key of standard value), and calculate the relative key of each record. If the relative key value is stored in the work area (3) above, and the relative key of the stored work area is "negative",
Add '1' to the above counter area (4), and if the relative key is 'correct' or '0', repeat the process to leave it as is for all records in the input buffer (1). When the process is finished, the record set as the reference value is transferred to the skipped location of the "empty" output buffer (2) by the value set in the counter area (4a) above, and then sorted. A sorting method based on a count classification method using relative keys.