JPS6132695B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a search device that searches for a maximum value (or minimum value).

In implementing file processing, sorting processing (an operation of rearranging records in a file in ascending or descending order based on a certain key word) is often necessary.

Conventional sorting techniques include internal sorting (insertion method, replacement method, tournament method, etc.) that is executed only on the main memory,
There is external sorting (radix classification method, various merging methods...) that uses storage devices such as magnetic tape or magnetic disks, but the former stores all of the target data on the main storage device. The latter also requires a large number of magnetic tape storage devices and a large amount of work area for sorting on disk. do.

However, this method is especially effective when a high-speed, large-capacity device such as a magnetic disk is used as a file recording medium, and is a method that is particularly effective when a high-speed, large-capacity device such as a magnetic disk is used as a file recording medium. By adding a search unit to search for the maximum or minimum value in the read data, sort processing is performed.

The present application provides a storage means for storing searched data, a means for reading out the searched data from the storage means, a determination means for determining whether the data read by the reading means satisfies the search area condition, and a determination by the determination means. The search device is characterized in that the search area conditions are made variable based on the results, and the search device uses a CPU (Central Rrocessing Unit).
An overview of the processing, including the program processing on the side, is shown in FIG. To explain based on the figure, first, the CPU instructs the readout control circuit of the disk, etc., to the area (start/end address) of the file to be searched, and then the keyword to be searched (hereinafter referred to as key) to the search unit. Start by specifying the upper and lower limit values and either the maximum or minimum value search.

On the other hand, the function of the search unit is to search for the record with the maximum or minimum key value within the specified limit value, and to hold the storage address of that record, that is, the corresponding address. If the CPU
retrieves the corresponding record using this address,
Perform predetermined processing. Furthermore, if you need a record in the next rank, increment or decrement the key of the previous record, set it again as the limit value in the search unit in the same way as before, and run it. , the key values of the retrieved records are in ascending or descending order. Also,
On the search unit side, it is only necessary to always detect the record having the minimum or maximum key value within the limit value specified by the CPU.

In this way, processing equivalent to conventional sorting becomes possible. Note that with the current sequential reading method, if there are multiple records with the same key value, it is not possible to retrieve all of them.

Therefore, this device requires the following functions in addition to the basic operation of searching for the maximum or minimum value described above.

In other words, since the search unit must always perform the search process up to the specified end address, it is possible to find multiple records with the same maximum or minimum key within the specified limit. If the address exists, the address of the last record closer to the end address is stored as the corresponding address in the retained address after the end of the search.

Therefore, if you search for the maximum or minimum value of the same value, set a status flag (hereinafter referred to as the "multiple existence" flag). After the search is complete, if the same flag is set, the upper and lower values will be set. The limit value etc. of the search area is the same as last time.
Only the address is changed to a value minus 1 from the corresponding address and the search process is re-executed.

In other words, assuming that the previous record at the corresponding address has been read and the necessary processing has been performed, there will be no record that is needed for the time being in the area after this corresponding address.
The area to be searched can be up to just before that, and if the same flag is set again, the search can be done in the same way.
By narrowing down the end addresses and repeating the process, all records with the same key value can be retrieved in descending order of storage address.

Furthermore, when searching for the last record with the same value in this way, the "multiple existing" flag is not set. Therefore, in order to retrieve the record of the next key order, it is necessary to return the end address of the search area to its initial value and return to the normal routine. As information for this purpose, as shown in FIG. 1, the flag F4, which is set at the beginning of a routine that detects the same value and narrows the search area based on the end address, is used.

Furthermore, if as a result of the search there is no key record that satisfies the conditions of the given limit value, a status flag "Not Applicable" is set to indicate this, and the entire process can be terminated.

The following points can be considered as advantages of sorting processing using this method.

◎Since no work area is required for sorting, media usage efficiency is extremely high.

◎Search files can be used for file organization, and there are no restrictions on the record position to be stored, so even if there is a high demand for adding or deleting up-dates, these can be handled in real time.

In other words, sequential reading is possible whenever desired.

◎File processing programs become extremely simple.

Hereinafter, the search device of the present invention will be explained in detail.

In Fig. 2, routes for storing limit values from the CPU, search addresses for disks, etc., initial set lines for various counters, flip-flops, etc. are omitted, but when considering the initial values, Counter 15 is the start address value of the search area given by the CPU, all other counters and flip-flops are "zero",
Furthermore, it is assumed that timings 1 and 2 can be obtained when necessary, that the end address of the search area given by the CPU is monitored, and that there is a function to end the processing.

Furthermore, in FIG. 3, A, B, i, F1, F
Symbols such as 2... indicate the same contents as the names in FIG.

In FIG. 2, 1 is a memory in which data to be searched (file) is stored, and its read output is called i. 2 is a memory in which the upper limit value is stored from the CPU in the case of a maximum value search, and the lower limit value is stored in the case of a minimum value search, and this output is called A. 3 is a comparison circuit that compares the outputs of the memory 1 and memory 2;
Assuming that the comparison condition is given from the memory 21, in the case of maximum value search, A≧i is detected, and in the case of minimum value search, A≦i is detected. The output is given to AND gates 11 and 13. 4
is a memory in which the lower limit value is stored by the CPU in the case of maximum value search and the upper limit value is stored by the CPU in the case of minimum value detection, contrary to memory 2, and i is the input terminal, and the read/write control terminal The output of the OR gate 19 is given to , and if this terminal = H, it is read,
=L, it has a writing function. Further, the output terminal is led to an AND gate 6. 5 is a memory having the same function as memory 4, and has the same wiring as memory 4 except that the output of OR gate 18 is given to the read/write control terminal and the output terminal is led to AND gate 7. It is. 6 and 7
is an AND gate that turns on/off the outputs of the memories 4 and 5 depending on the state of the flip-flop 17.
8 is an OR gate for the outputs of AND gates 6 and 7;
The output of the OR gate 8 is led to a comparison circuit 9, and this data will be referred to as "B" hereinafter.

The comparison circuit 9 compares B and i, and the comparison condition is given from the memory 21. In the case of maximum value search, it detects i≧B, and in the case of minimum value search, it detects i≦B. To detect. Further, unlike the comparator circuit 3, its output is output in two systems: an equal sign output (=) and a magnitude output (〓). 11 is an AND gate for taking the logical product of the output of the OR gate 10 and the output of the comparator circuit 3, and the output of this gate allows the data i from the memory 1 to be set to a limit value AorB specified by the CPU if A≦ i≦B or A≧i
It is known that the condition ≧B is satisfied.

Reference numeral 12 denotes a flip-flop, and if the result of the comparison of the target keys in the maximum or minimum value search is i=B, a pulse is output from the equal sign (=) output terminal of the comparison circuit 9 and set via the AND gate 23. Moreover, the output from the AND gate 13 is given to the clear terminal, and is cleared by this.

Incidentally, the output F1 of this flip-flop becomes the status flag for the above-mentioned ``multiple existence''.
13 is an AND gate, which calculates the AND of the output of the comparator circuit 3 and the output of the magnitude output (〓) of the comparator circuit 9, and determines that the condition of A≦i<B or A≧i>B is satisfied. show.

14 is a flip-flop, and gate 1
Set by output of 1. In other words, when the processing of this search unit starts, A≦i≦B or A
If the condition ≧i≧B is satisfied even once, it means that the flip-flop 14 is set, and the above-mentioned "not applicable" status flag is turned off ( ₃ =0). 15 is an address counter that counts the address of the record read from the file in the memory 1 at timing 2 pulses. 16 is and gate 1
The latch circuit receives the contents of the address counter 15 for each load pulse, that is, the latch circuit 16 holds the last address value taken in during processing. If you route the output of to the CPU, you can give the address of the record with the maximum or minimum key value. Reference numeral 17 denotes a flip-flop which repeats setting and resetting every time a condition satisfying pulse of AND gate 11 is output. Its output is called F2. 18 is an OR gate, one of which is supplied with the Q side of the flip-flop 17, and the other with the output from the detection circuit 22. Similarly, 19 is an OR gate, and the output from the flip-flop 17 side and the detection circuit 22 are applied.

The outputs of the OR gates 18 and 19 are led to the read/write terminals of the memories 4 and 5, respectively, and functionally act as an AND of negative logic.

A counter 20 counts the wait in synchronization with data read from the memory 1, and its output is led to the address terminals of the memories 2, 4, 5, and 21. From this, each memory 2,
4, 5, and 21 can be accessed synchronously with records read from memory 1.

Further, it is assumed that the counter 20 is initially set for each record.

The memory 21 is a memory in which the item (or field) configuration and search conditions for each item of records read out from the memory 1 before the start of processing of the search unit is stored in code, and its output is sent to the comparison circuit 3, 9 and a detection circuit 22.

The detection circuit 22 receives the output of the memory 21, detects the passing time of the item for which the maximum or minimum value is searched, and passes the negative signal to the OR gates 18, 1 during that time.
Detection circuit that outputs to 9. Reference numeral 23 denotes an AND gate, which limits the setting condition of "multiple existence" of the status flag of the flip-flop 12 to only after the flip-flop 14 is set. In other words, during one process, from the second time the condition is met, the comparator circuit 9 and the flip-flop 1
2 to detect i=B.

24 is stored in the latch circuit 16 when the flip-flop 12 with the status flag "Multiple Free" is set. 24 is a decrementer for creating an end address in the control circuit 25 by subtracting the address of the last existing record having the same value by 1. Reference numeral 25 denotes a control circuit such as a disk, which receives the start/end address of the search area from the CPU or the decrementer 24, etc., and controls continuous reading within this area. Furthermore, as the end address, information given from the CPU, information from the decrementer 24, and a flag F4 (described in FIG. 1) for determining which one is to be adopted are included.

Next, the actual operation will be sequentially explained using FIGS. 2, 3, and 4. Now, suppose that 10 records are recorded in the target file, that is, memory 1, from addresses 00 to 09, and the target key values of each record are in the order shown in Figure 4, and from the CPU side As a request, suppose you want to read records with key values from 100 to 1000 in ascending order (that is, minimum value search).

First, under the control of the CPU, addresses "00" and "09" are set as search areas in the control circuit 25 of FIG.
Next, store the lower limit value of 100 to memory 2 in Figure 2, the upper limit value of 1000 to memory 4 in Figure 2, and control data indicating the position of the target key in the record and minimum value search. After each data is stored in the memory 21 of FIG. 2, the retrieval unit is started.

As a result, this unit has A=100 and B=1000.
Therefore, we will search for 100≦i≦1000. When reading the first record, the flip-flop 17 in FIG. 2 is reset at the initial stage, so the AND gate 6 turns on and the output of the memory 4 becomes B. On the other hand, in the OR gate 18, since the Q side of the flip-flop 17 is "L", its output is "L" from the detection circuit 22.
During the period, it becomes "L", and the memory 5 enters the write mode and stores i=50.

Since i=50, the comparison circuit 9 is 50≦1000.
outputs the condition satisfied output. However, since 100≦50 does not hold, no output is generated from the comparison circuit 3, and the AND gate 11 is not turned on. Therefore, no changes occur in other parts. Next, when the second record i=408 is read, the memories 4 and 5, flip-flop 17, etc. perform the same operations as before, but since 100≦408, the comparison circuit 3
Since 408≦1000, the output of the comparator circuit 9, that is, the output of the OR gate 10, is generated, and the AND gate 11 generates a pulse that satisfies the condition 100≦408≦1000. , respectively, turns off the "Not Applicable" status flag of the flip-flop 14 ( ₃ = 0), holds the address of the corresponding record, that is, "01" in the address latch 16, and then turns off the flip-flop 17. Set. Further, 408 is stored in the memory 5. When the third, fourth and fifth records are read from this state, since the flip-flop 17 is set, the memory 4 is in the write mode and the memory 5 is in the read mode. Also, since AND gate 6 is off and AND gate 7 is on, comparison circuit 9
The input data B to is switched to the output of memory 5,
Thereafter, a search will be performed using the condition 100≦i≦408.
Therefore, data such as 1573, 671, 85, etc. are ignored.
(However, it is assumed that the address counter 15 is incremented by 1 for each record.) Next, when reading the 6th record, i=270, since the above search condition is satisfied, the previous i=
As with the 408 record, and gate 11
A condition fulfillment signal is output, and this signal causes the flip-flop 14 to set ( ₃ = 0, meaningless after the second time) the latch circuit 16 to reload "05" as the corresponding address. moreover,
The flip-flop 17 is reset so that i=270 written in the memory 4 will be set as B from now on. Due to the above operation, 100≦ after the 7th record
The search condition changes to i≦270, and memory 5 is write/write.
mode. Therefore, the 7th record with i=320 is ignored and the next 8th record with i=270
Then, the condition fulfillment signal is generated again, and latch circuit 1 is activated.
6 is held, and flip-flop 1
7 sets are performed. However, as a special operation this time, the establishment signal from the comparator circuit 9 is i=
270 Therefore, the output on the equal sign (=) side is generated. Then, the flip-flop 12 is set via the AND gate 23, and the "multiple existence" status flag is turned on.

From this state, when the 9th record i=150 is read, the search condition is satisfied, the latch circuit 16 is set to "08", the flip-flop 17 is reset, and from then on, the search condition is 100≦i≦150. will be carried out. On the other hand, the output of the comparison circuit 9 is
Since 270≠150, an establishment signal is output from the magnitude comparison (ⓓ) side, passes through the AND gate 13, and clears the flip-flop 12.

In other words, the "multiple existing" status flag is turned off. Since the next 10th record i=670 is ignored, the process ends in this state.

Therefore, on the CPU side, after detecting the end of processing, first the status flag is set to "Not applicable".
3 is checked, and if it is "L", the address of the latch circuit 16 is extracted and the record i=150 is read using the address "08" of the corresponding record. After performing the necessary processing on this record, in order to search for the next minimum value record,
The lower limit value to be stored in memory 4 is set to i=
Add +1 to 150 to make 151 and restore. Further, the upper limit value 1000 is stored in the memory 5 again, and the search unit is started.

Then, this time, the record with i = 150 is ignored, so the processing result is the corresponding record i = 270, its address is "07", and the status flag "Multiple Existence" = "H". Terminates processing with the status.

Therefore, as mentioned in the overview, after reading this record and performing the necessary processing, use the address "07" - 1 = "06" as the end address of the search, and other conditions for the search. If the search unit is operated as before, the corresponding record this time is i=270, its address "05" will be searched, and the "multiple existence" flag will be turned off and the process will end. Therefore, from now on, the end address will be returned to its initial value, the key value i=270 of the retrieved record will be incremented by 1, and the instruction will be given again. In this way, 320,
408, 670, and 671 are retrieved, and another access returns "Not applicable" and the entire process ends.

In addition, in conventional techniques, when keys with the same value occur during sorting, multiple keys with priorities are set in advance, and the key with the highest priority is sorted first. A common method is to perform a sorting process on keys of lower priority one after another each time they occur, and then output or rearrange them all.

However, in the above explanation, the storage address was used as identification information for key value records with the same value, but in this method as well, as shown in Figure 5, the same value occurs with a certain key, as in conventional sorting. death,
Once the “Multiple Existence” flag is set,
Under the control of the CPU, the search unit is instructed to search for the previously searched key part (item) using the data of the maximum or minimum value searched this time and an equal sign comparison. It instructs the search unit to search for the maximum or minimum value for the next priority item, and instructs the search unit to search for the maximum or minimum value only for records that satisfy all of the given conditions. As a result, this unit searches for the maximum or minimum value in the current item, targeting only records that had the same value in the previous item. In addition, if the status flag returns "Not applicable" from the sorting state of keys with deep priorities, the priority of the target key for maximum or minimum value search will be made shallow, and if "multiple existing" is returned, then the It is better to deepen the priority of the target key. Therefore, it is only necessary to repeat the basic operation of ``incrementing or decrementing the key value of the retrieved record and re-instructing the search unit'' only when both status flags are off. In other words, in this method, any method can be used as a means for extracting keys with the same value during sort processing.

As described above, the search method according to the present invention does not take up a memory work area and can reduce the time required for processing.

[Brief explanation of the drawing]

FIG. 1 is a schematic explanatory diagram of the search method according to the present invention;
Fig. 2 is a block diagram of a search unit using the search method according to the present invention, Fig. 3 is an explanatory diagram of the operation of the block diagram shown in Fig. 2, and Fig. 4 is an explanatory diagram of the search of the block diagram shown in Fig. 2. , FIG. 5 is an explanatory diagram illustrating another embodiment of the search method according to the present invention. 4, 5...memory, 17...flip/flop.

Claims (1)

[Scope of Claims] 1. A storage means for storing searched data, a reading means for reading out the searched data from the storage means, a storage means for storing data serving as a search condition, and the data read by the reading means is determining means for determining whether a search condition stored in a storage means is satisfied in synchronization with reading by the reading means; and a storage means for storing data serving as the search condition based on a determination result by the determining means. A search device comprising: control means for changing data. 2. Claim 1, characterized in that it has a second storage means for storing an address of the storage means as the data of the search condition, and a designation means for specifying the search condition by the address. The search device according to item 1.