CN109710542A - A kind of completely N-ary tree construction method and device - Google Patents
A kind of completely N-ary tree construction method and device Download PDFInfo
- Publication number
- CN109710542A CN109710542A CN201811631948.1A CN201811631948A CN109710542A CN 109710542 A CN109710542 A CN 109710542A CN 201811631948 A CN201811631948 A CN 201811631948A CN 109710542 A CN109710542 A CN 109710542A
- Authority
- CN
- China
- Prior art keywords
- node
- memory headroom
- index value
- address
- full
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000010276 construction Methods 0.000 title claims abstract description 33
- 238000000034 method Methods 0.000 claims abstract description 26
- 230000001174 ascending effect Effects 0.000 claims description 10
- 230000006870 function Effects 0.000 description 11
- 238000010586 diagram Methods 0.000 description 8
- 238000004590 computer program Methods 0.000 description 6
- 230000008569 process Effects 0.000 description 6
- 238000004891 communication Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 2
- 230000006399 behavior Effects 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000015572 biosynthetic process Effects 0.000 description 1
- 238000004422 calculation algorithm Methods 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 239000006185 dispersion Substances 0.000 description 1
- 235000013399 edible fruits Nutrition 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000003993 interaction Effects 0.000 description 1
- 238000011835 investigation Methods 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 230000008439 repair process Effects 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The present embodiments relate to technical field of data processing, specifically, it is related to a kind of completely N-ary tree construction method and device, this method can calculate the required memory space summation of full N-ary tree based on the number of nodes of full N-ary tree, and memory headroom is obtained according to required memory space summation, memory headroom is distributed each node into full N-ary tree by multiple index values based on setting, so, memory headroom can disposably be distributed, improve the excessive problem of storage allocation space number, it is mutually deposited the memory headroom address memory headroom address by root node and child node whether identical as set memory space address being directed toward based on pointer, it can be avoided the problem of data are excessively dispersed, and then reduce the generation of Cache Missing phenomenon.
Description
Technical field
The present embodiments relate to technical field of data processing, in particular to a kind of full N-ary tree construction method and dress
It sets.
Background technique
Cache memory be the access speed for the processing speed and memory of alleviating processor and centre plus high speed
Memory, access speed is higher than memory, and when calculating first searches data to be used in Cache memory whether there is, such as
Fruit exists, then is calculated using the data in Cache memory, data are first dispatched into Cache from memory otherwise and are deposited
In reservoir, then reuse, if it does not exist, this phenomenon is known as Cache Missing, once this phenomenon, processor occurs
It will stop executing again after current work waits data dispatch to come in, in this way, being unfavorable for the high-speed computation of processor.But
Existing Cache memory can have the phenomenon that Cache Missing mostly.
Summary of the invention
In view of this, can be avoided Cache Missing the present invention provides a kind of full N-ary tree construction method and device
The generation of phenomenon.
The embodiment of the invention provides a kind of full N-ary tree construction methods, which comprises
For each node in full N-ary tree, corresponding index value is set；
The quantity for calculating the node of full N-ary tree, the required memory space for calculating the full N-ary tree according to the quantity are total
With memory headroom is obtained according to the required memory space summation, multiple index values based on setting are by the memory headroom point
It is assigned to each node；Wherein, the memory headroom that each node is distributed is provided with memory headroom address；
Pointer is created, the memory headroom address for the root node for being directed toward the pointer in the full N-ary tree；
Whether the memory headroom address for judging that the pointer is directed toward is identical as set memory space address, if not identical, looks into
It is corresponding to obtain the index value for each index value found out for the index value for finding out all child nodes of the root node
The memory headroom address of the corresponding child node of the index value is stored in the root node by the memory headroom address of child node
Space is deposited, the memory headroom address of the root node is stored in the memory headroom of the corresponding child node of the index value.
Optionally, the method also includes:
The pointer is set to be directed toward next memory headroom address, wherein the corresponding section in the next memory headroom address
The index value of point is bigger than the index value of the root node by one；
Judge whether next memory headroom address and the set memory space address are identical；
If not identical, the index value of all child nodes of the corresponding node in next memory headroom address is found out；
For each index value found out, the memory headroom address of the corresponding child node of the index value is obtained, the index value is corresponding
The memory headroom address value of father node of child node be stored in the memory headroom of the corresponding child node of the index value, under described
One memory headroom address is stored in the memory headroom of the father node of the corresponding child node of the index value；
If they are the same, determine that the full N-ary tree building is completed.
Optionally, the step of corresponding index value being set for each node in full N-ary tree, comprising:
Obtain the depth value of each node；
It is followed successively by each node setting index value according to the ascending sequence of depth value, it is identical for depth value
Multiple nodes set gradually index value according to setting sequence.
Optionally, for the identical multiple nodes of depth value, the step of setting gradually index value according to setting sequence, packet
It includes:
For the identical multiple nodes of depth value, index value is set gradually according to by left-to-right sequence.
Optionally, the step of multiple index values based on setting distribute the memory headroom to each node, packet
It includes:
By the memory headroom according to the ascending sequence mean allocation of index value to each node.
The embodiment of the invention also provides a kind of full N-ary tree construction device, described device includes:
Index value setup module, for corresponding index value to be arranged for each node in full N-ary tree；
Memory headroom distribution module, the quantity of the node for calculating full N-ary tree calculate described full according to the quantity
The required memory space summation of N-ary tree obtains memory headroom, multiple ropes based on setting according to the required memory space summation
Draw value to distribute the memory headroom to each node；Wherein, the memory headroom that each node is distributed is provided with
Memory headroom address；
Pointer creation module, for creating pointer, the memory for the root node for being directed toward the pointer in the full N-ary tree is empty
Between address；
Judgment module, for judge memory headroom address that the pointer is directed toward and set memory space address whether phase
Together, if it is not identical, the index value of all child nodes of the root node is found out, for each index value found out, is obtained
The memory headroom address of the corresponding child node of the index value is stored in by the memory headroom address of the corresponding child node of the index value
The memory headroom address of the root node is stored in the corresponding child node of the index value by the memory headroom of the root node
Deposit space.
Optionally, described device further include:
Module is adjusted, for making the pointer be directed toward next memory headroom address, wherein next memory headroom
The index value of the corresponding node in address is bigger than the index value of the root node by one；
The judgment module is also used to judge that next memory headroom address and the set memory space address are
It is no identical；
If not identical, the index value of all child nodes of the corresponding node in next memory headroom address is found out；
For each index value found out, the memory headroom address of the corresponding child node of the index value is obtained, the index value is corresponding
The memory headroom address value of father node of child node be stored in the memory headroom of the corresponding child node of the index value, under described
One memory headroom address is stored in the memory headroom of the father node of the corresponding child node of the index value；
If they are the same, determine that the full N-ary tree building is completed.
Optionally, the index value setup module is that each node setting in full N-ary tree is corresponding in the following manner
Index value:
Obtain the depth value of each node；
It is followed successively by each node setting index value according to the ascending sequence of depth value, it is identical for depth value
Multiple nodes set gradually index value according to setting sequence.
Optionally, the index value setup module is directed to the identical multiple nodes of depth value in the following manner, according to setting
It is fixed sequentially to set gradually index value:
For the identical multiple nodes of depth value, index value is set gradually according to by left-to-right sequence.
Optionally, the memory headroom distribution module in the following manner multiple index values based on setting by the memory
Space is distributed to each node:
By the memory headroom according to the ascending sequence mean allocation of index value to each node.
The embodiment of the invention also provides a kind of electronic equipment, including memory, processor and storage are on a memory
And the computer program that can be run on a processor, the processor realize that above-mentioned one kind is full when executing the computer program
N-ary tree construction method.
The embodiment of the invention also provides a kind of computer readable storage medium, the readable storage medium storing program for executing includes computer
Program, the electronic equipment computer program controls the readable storage medium storing program for executing when running where execute a kind of above-mentioned full N fork
Tree constructing method.
Beneficial effect
A kind of full N-ary tree construction method and device provided in an embodiment of the present invention, can be based on the number of nodes of full N-ary tree
The required memory space summation of full N-ary tree is calculated, and memory headroom is obtained according to required memory space summation, based on setting
Multiple index values distribute memory headroom to each node into full N-ary tree, so, it is possible disposably to be divided memory headroom
Match, improves the excessive problem of storage allocation space number, the memory headroom address and set memory space being directed toward based on pointer
The whether identical memory headroom address by root node and child node in address is mutually deposited, and can be avoided that data excessively disperse asks
Topic, and then reduce the generation of Cache Missing phenomenon.
Detailed description of the invention
In order to illustrate the technical solution of the embodiments of the present invention more clearly, below will be to needed in the embodiment attached
Figure is briefly described, it should be understood that the following drawings illustrates only certain embodiments of the present invention, therefore is not construed as pair
The restriction of range for those of ordinary skill in the art without creative efforts, can also be according to this
A little attached drawings obtain other relevant attached drawings.
Fig. 1 is the block diagram of a kind of electronic equipment 10 provided by the embodiment of the present invention.
Fig. 2 is a kind of flow chart of full N-ary tree construction method provided by the embodiment of the present invention.
Fig. 3 is a kind of structural schematic diagram of full N-ary tree provided by the embodiment of the present invention.
Fig. 4 is a kind of module frame chart of full N-ary tree construction device 20 provided by the embodiment of the present invention.
Icon:
10- electronic equipment；11- memory；12- processor；13- network module；
20- expires N-ary tree construction device；21- index value setup module；22- memory headroom distribution module；The creation of 23- pointer
Module；24- judgment module；25- adjusts module.
Specific embodiment
In order to make the object, technical scheme and advantages of the embodiment of the invention clearer, below in conjunction with the embodiment of the present invention
In attached drawing, technical scheme in the embodiment of the invention is clearly and completely described, it is clear that described embodiment only
It is a part of the embodiments of the present invention, instead of all the embodiments.The present invention being usually described and illustrated herein in the accompanying drawings
The component of embodiment can be arranged and be designed with a variety of different configurations.
Therefore, the detailed description of the embodiment of the present invention provided in the accompanying drawings is not intended to limit below claimed
The scope of the present invention, but be merely representative of selected embodiment of the invention.Based on the embodiments of the present invention, this field is common
Technical staff's every other embodiment obtained without creative efforts belongs to the model that the present invention protects
It encloses.
It should also be noted that similar label and letter indicate similar terms in following attached drawing, therefore, once a certain Xiang Yi
It is defined in a attached drawing, does not then need that it is further defined and explained in subsequent attached drawing.
Tree is a kind of important data structure in computer science, such as balance N-ary tree can be used to realize lookup algorithm,
Search efficiency is promoted, is used to carry out division management according to certain rules to a limited region in graphics, to mention
Rise computational efficiency.
Inventor further investigation reveals that, existing full N-ary tree constructing technology is mostly recursively in the construction of a N-ary tree node
Its child node is constructed in function respectively, continues to construct its child node in its child node, the child node of each node is by its own
It is responsible for construction.In currently existing scheme, need at runtime for the independent storage allocation of each node, storage allocation is a phase
To slow operation, large overhead can be generated.In addition, also will cause node dispersion in memory, data distribution excessively disperses to make
At a large amount of Cache Missing phenomenon, it is unfavorable for the high-speed computation of processor.
Defect present in the above scheme in the prior art, is that inventor is obtaining after practicing and carefully studying
As a result, therefore, the solution that the discovery procedure of the above problem and the hereinafter embodiment of the present invention are proposed regarding to the issue above
Scheme all should be the contribution that inventor makes the present invention in process of the present invention.
Based on the studies above, the embodiment of the invention provides a kind of full N-ary tree construction method and devices, can effectively reduce
The generation of Cache Missing phenomenon.
Fig. 1 shows the block diagram of a kind of electronic equipment 10 provided by the embodiment of the present invention.The embodiment of the present invention
In electronic equipment 10 have data storage, transmission, processing function, as shown in Figure 1, electronic equipment 10 include: memory 11, place
Manage device 12, network module 13 and a kind of full N-ary tree construction device 20.
It is directly or indirectly electrically connected between memory 11, processor 12 and network module 13, to realize the biography of data
Defeated or interaction.It is electrically connected for example, these elements can be realized from each other by one or more communication bus or signal wire.
It is stored with a kind of full N-ary tree construction device 20 in memory 11, a kind of full N-ary tree construction device 20 includes at least one can
It is stored in the software function module in the memory 11 in the form of software or firmware (firmware), the processor 12 is logical
Cross the full N-ary tree building of one of software program and module, such as the embodiment of the present invention that operation is stored in memory 11
Device 20, thereby executing various function application and data processing, the i.e. full N-ary tree building of one of realization embodiment of the present invention
Method.
Wherein, the memory 11 may be, but not limited to, random access memory (Random Access Memory,
RAM), read-only memory (Read Only Memory, ROM), programmable read only memory (Programmable Read-Only
Memory, PROM), erasable read-only memory (Erasable Programmable Read-Only Memory, EPROM),
Electricallyerasable ROM (EEROM) (Electric Erasable Programmable Read-Only Memory, EEPROM) etc..
Wherein, memory 11 is for storing program, and the processor 12 executes described program after receiving and executing instruction.
The processor 12 may be a kind of IC chip, the processing capacity with data.Above-mentioned processor 12
It can be general processor, including central processing unit (Central Processing Unit, CPU), network processing unit
(Network Processor, NP) etc..It may be implemented or execute each method, step disclosed in the embodiment of the present invention and patrol
Collect block diagram.General processor can be microprocessor or the processor is also possible to any conventional processor etc..
Network module 13 is used to establish the communication connection between electronic equipment 10 and other communication terminal devices by network,
Realize the transmitting-receiving operation of network signal and data.Above-mentioned network signal may include wireless signal or wire signal.
It is appreciated that structure shown in FIG. 1 is only to illustrate, electronic equipment 10 may also include it is more than shown in Fig. 1 or
Less component, or with the configuration different from shown in Fig. 1.Each component shown in Fig. 1 can using hardware, software or its
Combination is realized.
The embodiment of the present invention also provides a kind of computer readable storage medium, and the readable storage medium storing program for executing includes computer journey
Sequence.Electronic equipment 10 computer program controls the readable storage medium storing program for executing when running where executes a kind of following full N fork
Tree constructing method.
Fig. 2 shows a kind of flow charts of full N-ary tree construction method provided by the embodiment of the present invention.The method is related
Process defined in method and step be applied to electronic equipment 10, can be realized by the processor 12.It below will be to shown in Fig. 2
Detailed process be described in detail:
In the present embodiment, be illustrated by taking full binary tree as an example, further, with depth value be 2 full binary tree into
Row explanation.
Corresponding index value is arranged for each node in full N-ary tree in step S21.
Fig. 3 is please referred to, obtains the depth value of each node first, depth value ascending according to depth value, same
Index value, obtained index value are as follows: I are arranged by sequence from left to right0、I1、I2、I3、I4、I5And I6。
Step S22, calculates the quantity of the node of full N-ary tree, and the required memory space for calculating full N-ary tree according to quantity is total
With memory headroom is obtained according to required memory space summation, multiple index values based on setting distribute memory headroom to each
Node.
For example, memory headroom needed for each node is 1MB, then completely the required memory space summation of N-ary tree is 7MB, therefore,
The memory headroom of acquisition is 7MB.
Further, according to the ascending sequence of index value by 7MB mean allocation to each node, wherein Mei Gejie
The distributed memory headroom of point is provided with memory headroom address.
Wherein, after for each node-classification memory headroom, the memory headroom of each node is reset into sky.
Node index value and corresponding memory headroom address are as shown in table 1:
Table 1
| Node | Memory headroom address |
| I0 | 501-510 |
| I1 | 511-520 |
| I2 | 521-530 |
| I3 | 531-540 |
| I4 | 541-550 |
| I5 | 551-560 |
| I6 | 561-570 |
It is appreciated that can be realized the disposable distribution of memory headroom by above-mentioned memory headroom distribution method, avoiding
The excessive bring of storage allocation number crosses large overhead and the time waits, and ensure that the high-speed computation of processor, is embodied in game layer
Face enables to game more smooth flow.
Step S23 creates pointer, the memory headroom address for the root node for being directed toward pointer in full N-ary tree.
In the present embodiment, two pointers: start pointer and end pointer are created.
Wherein, start pointer is directed toward node I0Memory headroom address beginning, that is, 501, end pointer is directed toward the
One leaf node (I3) memory headroom address beginning, that is, 531.
Step S24 judges whether the memory headroom address of pointer direction and set memory space address are identical.
Specifically, judge start pointer be directed toward memory headroom address and end pointer be directed toward memory headroom address whether
It is identical, if they are the same, shows that binary tree building is completed, if not identical, turn to step S25.
Step S25 finds out the index value of all child nodes of root node, for each index value found out, obtains
The memory headroom address of the corresponding child node of the index value is stored in by the memory headroom address of the corresponding child node of the index value
The memory headroom address of the root node is stored in the corresponding child node of the index value by the memory headroom of the root node
Deposit space.
For example, the memory headroom address 501 that start pointer is directed toward is not equal to the memory headroom address that end pointer is directed toward
531, at this point, finding out root node I0All child nodes index value: I1And I2, for I1, memory headroom address 511 is deposited
It is stored in root node I0Memory space, memory headroom address 501 is stored in node I1Memory space, for I2Make similar behaviour
Make.
It is appreciated that the index value of first child node of the node that index value is x is N*x+1, with the root of the present embodiment
Node I0For, the index value of first leaf node is 0*2+1=1, i.e. I1。
Step S26 makes pointer be directed toward next memory headroom address.
For example, make start pointer be directed toward memory headroom address 511, it is understood that for start pointer according to index value by
Small successively to move backward a position to big sequence, under original state, start pointer is directed toward root node I0Memory headroom
Location 501, after completing step S25, start pointer is directed toward node I1Memory headroom address 511.
Step S27 judges whether next memory headroom address and set memory space address are identical, according to judging result
Carry out respective operations.
It is appreciated that the operation of this step is similar with step S25.
For example, start pointer is directed toward node I1Memory headroom address 511 and end pointer be directed toward memory headroom address
531 is identical, searches egress I1Child node I3And I4, for node I3, memory headroom address 531 is stored in node I1's
Memory headroom, by node I1Memory headroom address 511 be stored in node I3Memory headroom, and so on, until start refers to
Needle is moved to node I3, in this way, completing the building of full binary tree.
By above-mentioned construction method, it can be avoided data and excessively disperse, so that the data of entire full binary tree are all arranged in
In one section of continuous memory headroom, such distribution is Cache close friend.
On the basis of the above, as shown in figure 4, the embodiment of the invention provides a kind of full N-ary tree construction device 20, described one
The full N-ary tree construction device 20 of kind includes: index value setup module 21, memory headroom distribution module 22, pointer creation module 23, sentences
Disconnected module 24 and adjustment module 25.
Index value setup module 21, for corresponding index value to be arranged for each node in full N-ary tree.
Since index value setup module 21 is similar with the realization principle of step S21 in Fig. 2, do not say more herein
It is bright.
Memory headroom distribution module 22, the quantity of the node for calculating full N-ary tree calculate described according to the quantity
The required memory space summation of full N-ary tree obtains memory headroom according to the required memory space summation, based on the multiple of setting
Index value distributes the memory headroom to each node；Wherein, the memory headroom setting that each node is distributed
There is memory headroom address.
Since memory headroom distribution module 22 is similar with the realization principle of step S22 in Fig. 2, do not say more herein
It is bright.
Pointer creation module 23, for creating pointer, the memory for the root node for being directed toward the pointer in the full N-ary tree
Space address.
Since pointer creation module 23 is similar with the realization principle of step S23 in Fig. 2, do not illustrate more herein.
Judgment module 24, for judge memory headroom address that the pointer is directed toward and set memory space address whether phase
Together, if it is not identical, the index value of all child nodes of the root node is found out, for each index value found out, is obtained
The memory headroom address of the corresponding child node of the index value is stored in by the memory headroom address of the corresponding child node of the index value
The memory headroom address of the root node is stored in the corresponding child node of the index value by the memory headroom of the root node
Deposit space.
Since judgment module 24 and step S24, step S25 in Fig. 2 are similar with the realization principle of step S27, herein
Do not illustrate more.
Module 25 is adjusted, for making the pointer be directed toward next memory headroom address, wherein next memory is empty
Between the corresponding node in address index value it is bigger than the index value of the root node by one.
Since adjustment module 25 is similar with the realization principle of step S26 in Fig. 2, do not illustrate more herein.
To sum up, a kind of completely N-ary tree construction method and device provided by the embodiment of the present invention, by carrying out memory headroom
Disposably, it continuously distributes, improves the excessive problem of storage allocation space number, can be avoided that data excessively disperse asks
Topic, and then reduce the generation of Cache Missing phenomenon.
In several embodiments provided by the embodiment of the present invention, it should be understood that disclosed device and method, it can also
To realize by another way.Device and method embodiment described above is only schematical, for example, in attached drawing
Flow chart and block diagram show that the devices of multiple embodiments according to the present invention, method and computer program product are able to achieve
Architecture, function and operation.In this regard, each box in flowchart or block diagram can represent module, a program
A part of section or code, a part of the module, section or code include that one or more is patrolled for realizing defined
Collect the executable instruction of function.It should also be noted that in some implementations as replacement, function marked in the box
It can occur in a different order than that indicated in the drawings.For example, two continuous boxes can actually be held substantially in parallel
Row, they can also be executed in the opposite order sometimes, and this depends on the function involved.It is also noted that block diagram and/or
The combination of each box in flow chart and the box in block diagram and or flow chart, can the function as defined in executing or dynamic
The dedicated hardware based system made is realized, or can be realized using a combination of dedicated hardware and computer instructions.
In addition, each functional module in each embodiment of the present invention can integrate one independent portion of formation together
Point, it is also possible to modules individualism, an independent part can also be integrated to form with two or more modules.
It, can be with if the function is realized and when sold or used as an independent product in the form of software function module
It is stored in a computer readable storage medium.Based on this understanding, technical solution of the present invention is substantially in other words
The part of the part that contributes to existing technology or the technical solution can be embodied in the form of software products, the meter
Calculation machine software product is stored in a storage medium, including some instructions are used so that a computer equipment (can be a
People's computer, electronic equipment 10 or the network equipment etc.) execute all or part of step of each embodiment the method for the present invention
Suddenly.And storage medium above-mentioned includes: USB flash disk, mobile hard disk, read-only memory (ROM, Read-Only Memory), deposits at random
The various media that can store program code such as access to memory (RAM, Random Access Memory), magnetic or disk.
It should be noted that, in this document, the terms "include", "comprise" or its any other variant are intended to the packet of nonexcludability
Contain, so that the process, method, article or equipment for including a series of elements not only includes those elements, but also including
Other elements that are not explicitly listed, or further include for elements inherent to such a process, method, article, or device.
In the absence of more restrictions, the element limited by sentence "including a ...", it is not excluded that including the element
Process, method, article or equipment in there is also other identical elements.
The foregoing is only a preferred embodiment of the present invention, is not intended to restrict the invention, for the skill of this field
For art personnel, the invention may be variously modified and varied.All within the spirits and principles of the present invention, made any to repair
Change, equivalent replacement, improvement etc., should all be included in the protection scope of the present invention.
Claims (10)
1. a kind of full N-ary tree construction method, which is characterized in that the described method includes:
For each node in full N-ary tree, corresponding index value is set；
The quantity for calculating the node of full N-ary tree calculates the required memory space summation of the full N-ary tree according to the quantity,
Obtain memory headroom according to the required memory space summation, multiple index values based on setting by the memory headroom distribute to
Each node；Wherein, the memory headroom that each node is distributed is provided with memory headroom address；
Pointer is created, the memory headroom address for the root node for being directed toward the pointer in the full N-ary tree；
Whether the memory headroom address for judging that the pointer is directed toward is identical as set memory space address, if not identical, finds out
The index value of all child nodes of the root node obtains the corresponding sub- section of the index value for each index value found out
The memory headroom address of point, the memory that the memory headroom address of the corresponding child node of the index value is stored in the root node are empty
Between, the memory headroom address of the root node is stored in the memory headroom of the corresponding child node of the index value.
2. full N-ary tree construction method according to claim 1, which is characterized in that the method also includes:
The pointer is set to be directed toward next memory headroom address, wherein the corresponding node in the next memory headroom address
Index value is bigger than the index value of the root node by one；
Judge whether next memory headroom address and the set memory space address are identical；
If not identical, the index value of all child nodes of the corresponding node in next memory headroom address is found out；For
The each index value found out obtains the memory headroom address of the corresponding child node of the index value, by the corresponding son of the index value
The memory headroom address value of the father node of node is stored in the memory headroom of the corresponding child node of the index value, will be described next
Memory headroom address is stored in the memory headroom of the father node of the corresponding child node of the index value；
If they are the same, determine that the full N-ary tree building is completed.
3. full N-ary tree construction method according to claim 1, which is characterized in that for each node setting in full N-ary tree
The step of corresponding index value, comprising:
Obtain the depth value of each node；
It is followed successively by each node setting index value according to the ascending sequence of depth value, it is identical multiple for depth value
Node sets gradually index value according to setting sequence.
4. full N-ary tree construction method according to claim 1, which is characterized in that the identical multiple nodes of depth value are directed to,
The step of setting gradually index value according to setting sequence, comprising:
For the identical multiple nodes of depth value, index value is set gradually according to by left-to-right sequence.
5. full N-ary tree construction method according to claim 1, which is characterized in that multiple index values based on setting are by institute
State the step of memory headroom is distributed to each node, comprising:
By the memory headroom according to the ascending sequence mean allocation of index value to each node.
6. a kind of full N-ary tree construction device, which is characterized in that described device includes:
Index value setup module, for corresponding index value to be arranged for each node in full N-ary tree；
Memory headroom distribution module, the quantity of the node for calculating full N-ary tree calculate the full N fork according to the quantity
The required memory space summation of tree obtains memory headroom, multiple indexes based on setting according to the required memory space summation
Value distributes the memory headroom to each node；Wherein, in the memory headroom that each node is distributed is provided with
Deposit space address；
Pointer creation module, for creating pointer, the memory headroom for the root node for being directed toward the pointer in the full N-ary tree
Location；
Judgment module, whether the memory headroom address and set memory space address for judging the pointer direction are identical, if
It is not identical, the index value of all child nodes of the root node is found out, for each index value found out, obtains the index
It is worth the memory headroom address of corresponding child node, the memory headroom address of the corresponding child node of the index value is stored in described
The memory headroom of node, the memory that the memory headroom address of the root node is stored in the corresponding child node of the index value are empty
Between.
7. full N-ary tree construction device according to claim 6, which is characterized in that described device further include:
Module is adjusted, for making the pointer be directed toward next memory headroom address, wherein next memory headroom address
The index value of corresponding node is bigger than the index value of the root node by one；
The judgment module be also used to judge next memory headroom address and the set memory space address whether phase
Together；
If not identical, the index value of all child nodes of the corresponding node in next memory headroom address is found out；For
The each index value found out obtains the memory headroom address of the corresponding child node of the index value, by the corresponding son of the index value
The memory headroom address value of the father node of node is stored in the memory headroom of the corresponding child node of the index value, will be described next
Memory headroom address is stored in the memory headroom of the father node of the corresponding child node of the index value；
If they are the same, determine that the full N-ary tree building is completed.
8. full N-ary tree construction device according to claim 6, which is characterized in that the index value setup module by with
Under type is that corresponding index value is arranged in each node in full N-ary tree:
Obtain the depth value of each node；
It is followed successively by each node setting index value according to the ascending sequence of depth value, it is identical multiple for depth value
Node sets gradually index value according to setting sequence.
9. full N-ary tree construction device according to claim 8, which is characterized in that the index value setup module by with
Under type is directed to the identical multiple nodes of depth value, sets gradually index value according to setting sequence:
For the identical multiple nodes of depth value, index value is set gradually according to by left-to-right sequence.
10. full N-ary tree construction device according to claim 6, which is characterized in that the memory headroom distribution module passes through
Following manner is distributed the memory headroom to each node based on multiple index values of setting:
By the memory headroom according to the ascending sequence mean allocation of index value to each node.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811631948.1A CN109710542B (en) | 2018-12-28 | 2018-12-28 | Full N-way tree construction method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811631948.1A CN109710542B (en) | 2018-12-28 | 2018-12-28 | Full N-way tree construction method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109710542A true CN109710542A (en) | 2019-05-03 |
| CN109710542B CN109710542B (en) | 2021-03-16 |
Family
ID=66259384
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811631948.1A Active CN109710542B (en) | 2018-12-28 | 2018-12-28 | Full N-way tree construction method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109710542B (en) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111932009A (en) * | 2020-08-10 | 2020-11-13 | 南宁市永恒影像有限公司 | Rectangular optimized layout method and device |
| CN111932011A (en) * | 2020-08-10 | 2020-11-13 | 南宁市永恒影像有限公司 | Rectangular optimization layout method and device based on binary block tree |
| CN112015671A (en) * | 2019-05-28 | 2020-12-01 | 慧荣科技股份有限公司 | Flash memory controller, memory device, and method of accessing a flash memory module |
| CN115834062A (en) * | 2023-02-20 | 2023-03-21 | 浙江奥鑫云科技有限公司 | Enterprise data transmission encryption method for data hosting service |
Citations (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7139765B1 (en) * | 2000-04-03 | 2006-11-21 | Alan Balkany | Hierarchical method for storing data with improved compression |
| CN1955958A (en) * | 2005-10-26 | 2007-05-02 | 腾讯科技（深圳）有限公司 | Sort data storage and split catalog inquiry method based on catalog tree |
| CN102012870A (en) * | 2010-11-18 | 2011-04-13 | 清华大学 | Memory allocation method |
| CN102521334A (en) * | 2011-12-07 | 2012-06-27 | 广东工业大学 | Data storage and query method based on classification characteristics and balanced binary tree |
| CN102880507A (en) * | 2012-09-12 | 2013-01-16 | 科立讯通信股份有限公司 | Method for applying and distributing chain structure message |
| CN103559323A (en) * | 2013-11-22 | 2014-02-05 | 盛杰 | Database implementation method |
| CN105512229A (en) * | 2015-11-30 | 2016-04-20 | 北京奇艺世纪科技有限公司 | IP address regional information storage, query method and device |
| US20170068455A1 (en) * | 2015-09-09 | 2017-03-09 | Intel Corporation | Application execution enclave memory page cache management method and apparatus |
| CN106547603A (en) * | 2015-09-23 | 2017-03-29 | 北京奇虎科技有限公司 | The method and apparatus for reducing the golang language system garbage reclamation times |
| CN107180092A (en) * | 2017-05-15 | 2017-09-19 | 中国科学院上海微系统与信息技术研究所 | A kind of control method of file system, device and terminal |
| CN107229429A (en) * | 2017-06-27 | 2017-10-03 | 郑州云海信息技术有限公司 | A kind of memory space management and device |
| CN107797941A (en) * | 2016-09-06 | 2018-03-13 | 华为技术有限公司 | Memory allocation method and device are coloured for the caching of search tree |
| CN108628753A (en) * | 2017-03-24 | 2018-10-09 | 华为技术有限公司 | Memory headroom management method and device |
-
2018
- 2018-12-28 CN CN201811631948.1A patent/CN109710542B/en active Active
Patent Citations (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7139765B1 (en) * | 2000-04-03 | 2006-11-21 | Alan Balkany | Hierarchical method for storing data with improved compression |
| CN1955958A (en) * | 2005-10-26 | 2007-05-02 | 腾讯科技（深圳）有限公司 | Sort data storage and split catalog inquiry method based on catalog tree |
| CN102012870A (en) * | 2010-11-18 | 2011-04-13 | 清华大学 | Memory allocation method |
| CN102521334A (en) * | 2011-12-07 | 2012-06-27 | 广东工业大学 | Data storage and query method based on classification characteristics and balanced binary tree |
| CN102880507A (en) * | 2012-09-12 | 2013-01-16 | 科立讯通信股份有限公司 | Method for applying and distributing chain structure message |
| CN103559323A (en) * | 2013-11-22 | 2014-02-05 | 盛杰 | Database implementation method |
| US20170068455A1 (en) * | 2015-09-09 | 2017-03-09 | Intel Corporation | Application execution enclave memory page cache management method and apparatus |
| CN106547603A (en) * | 2015-09-23 | 2017-03-29 | 北京奇虎科技有限公司 | The method and apparatus for reducing the golang language system garbage reclamation times |
| CN105512229A (en) * | 2015-11-30 | 2016-04-20 | 北京奇艺世纪科技有限公司 | IP address regional information storage, query method and device |
| CN107797941A (en) * | 2016-09-06 | 2018-03-13 | 华为技术有限公司 | Memory allocation method and device are coloured for the caching of search tree |
| CN108628753A (en) * | 2017-03-24 | 2018-10-09 | 华为技术有限公司 | Memory headroom management method and device |
| CN107180092A (en) * | 2017-05-15 | 2017-09-19 | 中国科学院上海微系统与信息技术研究所 | A kind of control method of file system, device and terminal |
| CN107229429A (en) * | 2017-06-27 | 2017-10-03 | 郑州云海信息技术有限公司 | A kind of memory space management and device |
Non-Patent Citations (1)
| Title |
|---|
| 俞嘉地: "BitTorrent对等网文件共享系统关键技术研究", 《中国优秀硕士学位论文全文数据库 信息科技辑》 * |
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112015671A (en) * | 2019-05-28 | 2020-12-01 | 慧荣科技股份有限公司 | Flash memory controller, memory device, and method of accessing a flash memory module |
| CN111932009A (en) * | 2020-08-10 | 2020-11-13 | 南宁市永恒影像有限公司 | Rectangular optimized layout method and device |
| CN111932011A (en) * | 2020-08-10 | 2020-11-13 | 南宁市永恒影像有限公司 | Rectangular optimization layout method and device based on binary block tree |
| CN111932009B (en) * | 2020-08-10 | 2024-05-21 | 南宁市永恒影像有限公司 | Rectangular optimized layout method and device |
| CN111932011B (en) * | 2020-08-10 | 2024-05-24 | 南宁市永恒影像有限公司 | Rectangular optimization layout method and device based on binary block tree |
| CN115834062A (en) * | 2023-02-20 | 2023-03-21 | 浙江奥鑫云科技有限公司 | Enterprise data transmission encryption method for data hosting service |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109710542B (en) | 2021-03-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109710542A (en) | A kind of completely N-ary tree construction method and device | |
| CN114721833B (en) | Intelligent cloud coordination method and device based on platform service type | |
| CN104239137B (en) | Multi-model Method of Scheduling Parallel and device based on DAG node optimal paths | |
| WO2015172374A1 (en) | System, method and apparatuses for identifying load volatility of a power customer and a tangible computer readable medium | |
| CN112100450A (en) | Graph calculation data segmentation method, terminal device and storage medium | |
| CN108399266A (en) | Data pick-up method, apparatus, electronic equipment and computer readable storage medium | |
| Hendrich et al. | Parallel BVH construction using progressive hierarchical refinement | |
| CN106408126B (en) | A kind of three perfecting by stage methods concurrently gathered towards energy consumption data | |
| CN106067158B (en) | A kind of feature comparison method and device based on GPU | |
| CN103034678A (en) | RkNN (reverse k nearest neighbor) inquiring method based on Voronoi diagram | |
| CN107590570A (en) | A kind of bearing power Forecasting Methodology and system | |
| CN105354313A (en) | Method for carrying out credit assessment by big data | |
| CN109449923A (en) | Quantitative analysis method for operation flexibility of active power distribution system and related product | |
| CN110380906B (en) | A large-scale multi-dimensional fusion virtual network mapping method | |
| CN103077127B (en) | A kind of method and apparatus of specified data migrating objects | |
| CN110070287A (en) | A kind of dynamic task allocation method based on similitude clustering and average thought | |
| CN117150393B (en) | A method and system for identifying weak branches in power systems based on decision trees | |
| CN109493025A (en) | A kind of account generation method and device | |
| CN109086137A (en) | GPU concurrent computation resource configuration method and device | |
| CN109710314B (en) | A method of based on graph structure distributed parallel mode construction figure | |
| CN112437137B (en) | Internet of things data connection method and system | |
| CN112925793A (en) | Distributed mixed storage method and system for multiple structural data | |
| CN107204870B (en) | Resource expansion method and apparatus | |
| CN117556095B (en) | Graph data segmentation method, device, computer equipment and storage medium | |
| CN111536986B (en) | Combined limiting condition data preprocessing method in truck path planning |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |