JP3319391B2 - High-speed data alignment device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a high-speed data sorting apparatus which sorts data at a high speed by examining a distribution state of data in advance and setting appropriate data as a reference value for quick sorting.

[0002]

2. Description of the Related Art Quick sorting is a method that is widely and generally used as high-speed sorting. In the quick sort, certain data is used as a boundary (referred to as a reference value in the present invention), and data is divided into larger data and non-larger data. Significantly affected. The reference value is
Use of the median value of the data as much as possible reduces unnecessary comparisons and movements, and speeds up alignment.

[0003]

However, in the prior art, since data having a rank of half the number of data is simply used as a reference value, there is a problem that high speed cannot be exhibited depending on the arrangement of data. Was. Also, when trying to calculate the reference value accurately, a memory that depends on the number of data is needed to understand the distribution state of the data,
Uses the memory resources needed for the sort itself,
On the contrary, there was a problem that the sorting time was delayed.

[0004] The present invention has been made in view of the above-described circumstances. By maintaining the distribution state of data with rough accuracy, quick sorting can be executed efficiently to perform high-speed sorting. It is an object of the present invention to provide a high-speed data alignment device that can be used for data analysis other than alignment.

[0005]

According to the first aspect of the present invention, there is provided a high-speed data sorting apparatus for rearranging data having a rank which is half the number of data as a reference value. It is characterized by comprising a data distribution status investigating means for examining a data distribution status, and quick sorting means for performing a quick sort based on the data distribution status by the data distribution status investigating means.

Further, according to the invention described in claim 2, according to claim 1,
In the high-speed data alignment device described above, the data distribution status investigation unit includes a distribution table generation unit that generates a distribution table for grasping a data distribution status, and stores data in the distribution table generated by the distribution table generation unit. And a distribution table registering means for registering.

[0007] According to the third aspect of the present invention, the first aspect of the present invention.
In the high-speed data sorting device described above, the data distribution status investigating means further includes a distribution table normalizing means for compressing the distribution table in order to register data outside the scale of the distribution table. I do.

In the present invention, the data distribution status is checked by the data distribution status checking means, and quick sorting is performed by the quick sorting means based on the data distribution status. Therefore, it is possible to perform quick sorting efficiently and perform high-speed sorting. In addition, since the distribution status can be held with appropriate accuracy while suppressing the amount of memory to be used, it is possible to use the distribution table for data analysis other than alignment.

[0009]

Embodiments of the present invention will be described below with reference to the drawings. A. Configuration of Embodiment FIG. 1 is a block diagram showing an overall configuration according to an embodiment of the present invention. In the figure, an input device 1 is composed of a magnetic disk or the like, reads data to be sorted one record at a time, and transfers it to a data processing device 2. The data processing device 2 includes a CPU or the like that processes data,
The input device 1 is controlled by a program stored in the
Are arranged in ascending or descending order based on the order of the keys, and output to the output device 3. Storage medium 4
Is composed of a magnetic disk, a CD-ROM, or the like in which a control program for aligning data obtained from the input device 1 using the data processing device 2 is stored. The output device 3 includes a display device or the like that outputs the alignment result by the data processing device 2.

The data processing apparatus 2 comprises a data distribution status examination means 21 for examining the distribution status of data, and a quick sort means 22 for performing a quick sort based on the data distribution status. The data distribution status investigation unit 21 includes a distribution table generation unit 211 that generates a distribution table for grasping the distribution status of data, and a distribution table registration unit 212 that registers data in the distribution table.
And distribution table normalizing means 213 for compressing the distribution table to register data outside the scale of the distribution table.

FIG. 2 is a conceptual diagram showing a configuration example of the distribution table. The distribution table is a two-dimensional array composed of values serving as sorting keys and the number of records, and each value is represented by a real number with the highest precision that can be handled on the data processing device 2. Conceptually, as shown in FIG. 2, it can be regarded as a two-dimensional real number graph in which a value serving as a sort key is set on the horizontal axis and the number of records is set on the vertical axis.

In the data processing device 2 described above, alignment is performed at high speed as described below. First, the data is passed to the data distribution status investigation unit 21. The data distribution status investigation means 21 creates a distribution table by the distribution table creation means 211 when the first data is obtained, and thereafter registers the data in the distribution table by the distribution table registration means 212 every time data is read.

If the data cannot be registered because the data exceeds the range of each axis (hereinafter referred to as scale) of the corresponding table, the distribution table normalizing means 213 is called,
By compressing the distribution table in the vertical / horizontal direction, the scale is expanded and the corresponding data is registered. By registering all the data in the distribution table, the distribution table shows a rough distribution state of the entire data. Lastly, the quick sorting means 22 calculates an intermediate value for efficiently performing quick sorting based on the distribution table, thereby making it possible to perform sorting at a higher speed than in a conventional apparatus.

B. Next, the operation of this embodiment will be described in detail with reference to FIG. 1, FIG. 3, FIG. 4, and FIG. First, the control program is read from the storage medium 4 to the data processing device 2, and the data processing device 2 is initialized. Next, the input device 1
Reads one record of data to be sorted (step A1) and passes the data to the data distribution status examination means 21. When this is the first data, the distribution table creating means 211
Determines the scales of the vertical and horizontal axes and the step size of each axis according to an interactive means using a dialog box or initial values, and creates a distribution table (step A2).
~ A4).

Here, it is assumed that the distribution table is represented as a two-dimensional real number array as described above. Each data is registered in the analysis table 1 by the analysis table registration means 212 (step A7). Data that does not match the value of each axis, such as when the key value is a real number, is registered after being approximated to a closer value. When data exceeding the scale is registered, the distribution table is normalized by the distribution table normalizing means 213 (steps A5 to A6).

The normalization is performed by compressing the distribution table in the axial direction beyond the scale (steps B1 to B).
4). That is, assuming that the distribution tail before compression is shown in FIG. 5A, if the data exceeds the key value,
As shown in FIG. 5B, the distribution table is compressed in the horizontal direction (step B2). If the number of records exceeds the number, the distribution table is compressed in the vertical direction as shown in FIG. 5C (step B4). . The compression ratio is a fixed value determined in advance. Then, the corresponding data is registered in the distribution table by the distribution table registration means 212 (step A7). Registration is
After the distribution table is normalized, the data is also subjected to the same normalization.

Next, the quick sort means 22 calculates an intermediate value based on the distribution table, and executes quick sort as needed using the value as a reference value (steps A8 to A1).
0), and finally output the alignment result to the output device 3 (step A11).

[0018]

As described above, according to the present invention,
Since the data distribution state is used, there is an advantage that quick sorting can be executed efficiently and sorting can be performed at high speed. In addition, since the distribution state can be held with appropriate accuracy while suppressing the amount of memory used, there is an advantage that the use of the distribution table can be used for data analysis other than alignment.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an overall configuration according to an embodiment of the present invention.

FIG. 2 is a conceptual diagram illustrating a configuration example of a distribution table.

FIG. 3 is a flowchart for explaining the operation of the present embodiment.

FIG. 4 is a flowchart illustrating an operation of normalization.

FIG. 5 is a conceptual diagram illustrating normalization of a distribution table.

[Explanation of symbols]

 REFERENCE SIGNS LIST 1 input device 2 data processing device 3 output device 4 storage medium 21 data distribution status investigation means 22 quick sort means 211 distribution table creation means 212 distribution table registration means 213 distribution table normalization means

Claims (3)

(57) [Claims] 1. A high-speed data sorting apparatus that sorts data having a rank of half the number of data as a reference value, wherein: a data distribution status investigating means for examining a data distribution status; A high-speed data sorting apparatus, comprising: a quick sort unit that performs a quick sort based on a situation. 2. The data distribution status investigating means includes: a distribution table generating means for generating a distribution table for grasping a data distribution status; and a distribution registering data in the distribution table generated by the distribution table generating means. 2. The high-speed data sorting apparatus according to claim 1, further comprising a table registration unit. 3. The data distribution status investigating means further comprises a distribution table normalizing means for compressing the distribution table to register data outside the scale of the distribution table. 2. The high-speed data alignment device according to 1.