CN106294348B

CN106294348B - For the real-time sort method and device of real-time report data

Info

Publication number: CN106294348B
Application number: CN201510242599.4A
Authority: CN
Inventors: 杨闯
Original assignee: SHENZHEN ZMODO TECHNOLOGY Co Ltd
Current assignee: Aizhi Technology Shenzhen Co ltd; Zmodo Technology Shenzhen Corp ltd
Priority date: 2015-05-13
Filing date: 2015-05-13
Publication date: 2019-07-09
Anticipated expiration: 2035-05-13
Also published as: CN106294348A

Abstract

The present invention relates to a kind of real-time sort methods for real-time report data, comprising: obtains the data currently reported；Current data is ranked up on the basis of multiple subsequences that reported data is formed, the data that subsequence is included have ordinal relation, also there is ordinal relation, comprising the following steps: judge whether current data should be arranged in the centre of two data for the same subsequence that sorting data has been formed between subsequence；If, subsequence locating for the position is divided into two new subsequences as division points by the position that should be then arranged using current data, so that the ordinal relation between subsequence and the ordinal relation between reported data are constant, current data is aligned in any one subsequence in two new subsequences；Otherwise, current data is aligned in established subsequence.The above method is a kind of sort method of efficient stable.In addition, also providing a kind of real-time collator for real-time report data.

Description

For the real-time sort method and device of real-time report data

Technical field

The present invention relates to real time data processing fields, more particularly to a kind of real-time sequence side for real-time report data Method and device.

Background technique

With the development of internet technology, the work and life of people increasingly be unable to do without internet, and various internets are answered With the service provided people with convenience.The user volume that some Internet applications are possessed is even up to more than one hundred million ranks.

Internet application, may in order to realize the analysis mining of user preferences or the analysis mining of certain potential rules It needs to apply data from user terminal collection is relevant in real time, and will be sorted in real time using data.That is, often receiving new application Data are then ranked up on the basis of sorting data immediately.

Due to Internet application provide service have real-time, it is thus possible to it is required that in sequencer procedure sorting data it Between sequence do not change, therefore, it is necessary to be sorted in real time using a kind of stable sort method application data.And What is received due to Internet application is magnanimity using data, therefore, it is necessary to using a kind of higher method of efficiency to data It is sorted in real time.

Summary of the invention

Based on this, it is necessary to provide a kind of efficient and stable real-time sort method and dress for real-time report data It sets.

A kind of real-time sort method for real-time report data, comprising the following steps:

Obtain the data currently reported；

Current data is ranked up on the basis of multiple subsequences that reported data is formed, the subsequence is wrapped Have between the data contained and follow the ordinal relation of preset ordering rule, also has that follow this preset between the subsequence The ordinal relation of ordering rule, comprising the following steps:

Judge whether current data should be arranged in the same of sorting data formation according to the preset ordering rule The centre of two data of a subsequence；

If current data should be arranged in the centre of two data for the same subsequence that sorting data has been formed, with Subsequence locating for the position is divided into two new subsequences for division points by the position that current data should arrange, and is made Ordinal relation between the internal data of two new subsequences maintains that original ordinal relation is constant, two new subsequences are opposite In the ordinal relation and sequence of the divided subsequence relative to other subsequences of other subsequences that sorting data is formed Relationship be consistent and two new subsequences between ordinal relation and two new subsequences data for being included exist Ordinal relation in divided subsequence is consistent, and current data is further aligned to this according to preset ordering rule In any one subsequence in two new subsequences；

If current data should not be arranged in the centre of two data for any one subsequence that sorting data has been formed, Then current data is aligned in established subsequence according to preset ordering rule.

The real-time sort method for real-time report data in the present embodiment, has sorted if current data should be arranged in The centre of two data for the same subsequence that data are formed, then should as division points using the position that current data should arrange Subsequence locating for position is divided into two new subsequences, and by current data according to preset ordering rule be aligned to this two In any one subsequence in a new subsequence, to facilitate the data search pending data according to subsequence head and the tail both ends According to arrangement position, data sorting efficiency can be improved, and the above method is in sorting data shape to the data currently reported At subsequence on the basis of be ranked up, do not change original ordinal relation between sorting data, be a kind of stable Sort method.

Wherein one implement in, it is described reported data formed multiple subsequences on the basis of to current data into Row sequence the step of include:

Each subsequence head end data and endian data that current data and sorting data are formed are compared；

Judge the data whether current data is greater than in a subsequence head end data and endian data and is less than another A data draw subsequence locating for the position as division points if so, entering the position that should be arranged using current data The step of being divided into two new subsequences；

Judge the data whether current data is greater than in the adjacent rear end data and head end data of two adjacent subsequences And it is less than another data, if so, current data is aligned to appointing in two subsequences according to preset ordering rule It anticipates a subsequence；

Judge whether should be arranged in front of first subsequence according to preset ordering rule current data, if so, Then current data is aligned in first subsequence according to preset ordering rule；

Judge whether should be arranged in behind the last one subsequence according to preset ordering rule current data, if It is current data then to be formed into a new subsequence, and the subsequence for making this new is relative to other established subsequences For the last one subsequence.

In the present embodiment, current data is compared with each subsequence head end data and endian data, rather than will Current data is compared with each of each subsequence data, can reduce number of comparisons, to improve data sorting effect Rate.

It is described in one of the embodiments, that current data is aligned to two new sons according to preset ordering rule The step in any one subsequence in sequence are as follows:

Subsequence belonging to data closest with current data in two new subsequences is obtained, current data is pressed It is aligned in the subsequence belonging to this according to preset ordering rule；

Step current data being aligned to according to preset ordering rule in established subsequence are as follows:

Subsequence belonging to data closest with current data in the established subsequence is obtained, by current data It is aligned in the subsequence belonging to this according to preset ordering rule.

In the present embodiment, current data is aligned to belonging to the closest data of current data according to preset ordering rule Subsequence, the quantity for the subsequence that sorting data is formed can be reduced, to reduce the head end number of current data and subsequence According to the number compared with endian data, to improve sequence efficiency.

In one of the embodiments, the method also includes:

Judge whether the quantity for the data that the subsequence that current data is added is included is more than or equal to threshold value, if so, will The subsequence is divided into two subsequences.

In the present embodiment, when the quantity of the data of sub-sequence is more than or equal to threshold value, subsequence is divided into two sub- sequences Column, can reduce the number searched in subsequence when sequence, to improve sequence efficiency.

The threshold value is equal to twice of the extraction of square root that reported data estimates total amount in one of the embodiments,.

In the present embodiment, the time complexity of the above-mentioned real-time sort method for real-time report data is O (N), wherein N It indicates that reported data estimates total amount, there is lower time complexity.

A kind of real-time collator for real-time report data, comprising:

Data acquisition module, for obtaining the data currently reported；

Sorting module, multiple subsequences for being formed in reported data on the basis ofs, are ranked up current data, There is the ordinal relation for following preset ordering rule between the data that the subsequence is included, also have between the subsequence There is the ordinal relation for following the preset ordering rule；

The sorting module comprises the following modules:

Position judging module has been arranged for judging current data according to whether the preset ordering rule should be arranged in Ordinal number according to two data of the same subsequence of formation centre, if so, starting the first subsequence division module, otherwise, Start the second sorting module；

First subsequence division module, the position for that should be arranged using current data will be locating for the position as division points Subsequence is divided into two new subsequences, and the ordinal relation between the internal data of two new subsequences is made to remain former There is the ordinal relation for other subsequences that ordinal relation is constant, two new subsequences are formed relative to sorting data and is drawn The subsequence being divided to relative to the ordinal relation of other subsequences be consistent and two new subsequences between ordinal relation Ordinal relation of the data for being included with two new subsequences in divided subsequence is consistent；

First sorting module, for current data to be aligned in two new subsequences according to preset ordering rule Any one subsequence in；

Second sorting module, for current data to be aligned in established subsequence according to preset ordering rule.

The real-time collator for real-time report data in the present embodiment, has sorted if current data should be arranged in The centre of two data for the same subsequence that data are formed, then should as division points using the position that current data should arrange Subsequence locating for position is divided into two new subsequences, and by current data according to preset ordering rule be aligned to this two In any one subsequence in a new subsequence, to facilitate the data search pending data according to subsequence head and the tail both ends According to arrangement position, data sorting efficiency can be improved, and above-mentioned apparatus forms the data currently reported in sorting data Subsequence on the basis of be ranked up, do not change original ordinal relation between sorting data, be a kind of stable row Sequence device.

The position judging module includes comparison module, first judgment module, the second judgement in one of the embodiments, Module, third judgment module and the 4th judgment module；Second sorting module includes intermediate insertion module, head end insertion mould Block, tail end are inserted into module, in which:

The comparison module is used for each subsequence head end data and tail end for forming current data with sorting data Data are compared；

The first judgment module is for judging whether current data is greater than in a subsequence head end data and endian data A data and be less than another data, if so, starting the first subsequence division module；

Second judgment module, for judge current data whether be greater than two adjacent subsequences adjacent rear end data and Data in head end data and be less than another data, if so, starting is described intermediate to be inserted into module；

Third judgment module is for judging first son whether should be arranged according to preset ordering rule current data Before sequence, if so, starting the head end insertion module；

4th judgment module is for judging whether the last one should be arranged according to preset ordering rule current data Behind subsequence, if so, starting the tail end insertion module；

The intermediate insertion module is used to current data being aligned to described two adjacent sub- sequences according to preset ordering rule Any one subsequence in column；

Current data for being aligned in first subsequence by the head end insertion module according to preset ordering rule

The tail end insertion module is used to forming current data into a new subsequence, and the subsequence phase for making this new It is the last one subsequence for other established subsequences.

First sorting module is used to obtain in described two new subsequences and current in one of the embodiments, Current data is aligned to according to preset ordering rule the subsequence belonging to this by subsequence belonging to the closest data of data In；

Second sorting module is for obtaining data institute closest with current data in the established subsequence Current data is aligned in the subsequence belonging to this by the subsequence of category according to preset ordering rule.

Described device in one of the embodiments, further include:

Quantity judgment module, for judging whether the quantity for the subsequence data that are included that current data is added is greater than In threshold value；

Second subsequence division module, if the quantity for the data that the subsequence for current data to be added is included be greater than etc. In threshold value, then the subsequence is divided into two subsequences.

In the present embodiment, the time complexity of the above-mentioned real-time collator for real-time report data is O (N), wherein N It indicates that reported data estimates total amount, there is lower time complexity.

Detailed description of the invention

Figure 1A is in one embodiment for the flow diagram of the real-time sort method of real-time report data；

Figure 1B is the flow diagram of step S104 in one embodiment；

Fig. 2 is the flow diagram of step S104 in another embodiment；

Fig. 3 is the storage schematic diagram of subsequence in one embodiment；

Fig. 4 A and Fig. 4 B are that the real-time sort method for real-time report data in one embodiment forms subsequence Schematic diagram；

Fig. 5 A is in one embodiment for the structural schematic diagram of the real-time collator of real-time report data；

Fig. 5 B is the structural schematic diagram of sorting module 52 in one embodiment；

Fig. 6 is the structural schematic diagram of sorting module 52 in another embodiment；

Fig. 7 is in one embodiment for the structural schematic diagram of the real-time collator of real-time report data.

Specific embodiment

As shown in Figure 1A, in one embodiment, a kind of real-time sort method for real-time report data, including it is following Step:

Step S102 obtains the data currently reported.

In one embodiment, the data that client currently reports can be obtained by server.

Step S104 is ranked up current data on the basis of multiple subsequences that reported data is formed, sub- sequence Arranging has the ordinal relation for following preset ordering rule between included data, also default with this is followed between subsequence Ordering rule ordinal relation.

Above-mentioned preset ordering rule can be ordering rule or ordering rule from big to small from small to large etc..

One subsequence is greater than another subsequence, it is believed that all data that the subsequence is included are greater than another All data that subsequence is included.

In one embodiment, the ordinal relation between data that subsequence is included can with the corresponding label of data into Line flag, for example, may make the corresponding label of relatively large data label corresponding always greater than relatively small data, or Person, the corresponding label of relatively large data are always less than the label of relatively small data.For example, a subsequence is included Data be sequentially stored in an array according to the ordinal relation between data, if data are in array according to from small to large Sequence is stored, then the small array element of subscript is always less than or equal to the big array element of subscript；Conversely, if data are in array In stored according to sequence from big to small, then the small array element of subscript is always greater than being equal to the big array element of subscript.

In another embodiment, the ordinal relation between data that subsequence is included can use the corresponding physics of data Arrangement position relationship indicates.For example, the data that can included by a subsequence according to the ordinal relation between data successively It is stored in a continuous physical space, if data are stored in the physical space according to sequence from small to large, The small array element of physical storage address is always less than or equal to the big array element of physical storage address；Conversely, if data are at this It is stored in physical space according to sequence from big to small, then the small array element of physical storage address is always greater than equal to object Manage the big array element of storage address.

In another embodiment, the ordinal relation between data that subsequence is included can use the corresponding logic of data Arrangement position relationship indicates.For example, the data that a subsequence is included can be stored in a single linked list, if data exist It is stored in the single linked list according to sequence from small to large, then the data of upper node storage are always less than in single linked list In the data of next node storage, vice versa.

In one embodiment, the ordinal relation between subsequence can be marked with the corresponding label of subsequence.Example Such as, it may make the corresponding label of relatively large subsequence label corresponding always greater than relatively small subsequence, alternatively, phase Always it is less than the label of relatively small data to the corresponding label of biggish data.For example, the smallest subsequence can be marked The 3rd group etc. is identified as labeled as the 2nd group, the small subsequence of third for the 1st group, secondary small subsequence.

In another embodiment, the ordinal relation between subsequence can be directed toward to indicate with mutual pointer, If the corresponding pointer of a subsequence is directed toward another subsequence, then it represents that the subsequence has relative to another subsequence to be followed The first relationship of preset ordering rule.For example, subsequence can be indicated with the data object comprising data item and pointer entry, Wherein data item indicates another subsequence for being directed toward for storing the data that sub-series of packets contains, pointer entry.If A pairs of subsequence The pointer answered is directed toward subsequence B, then illustrates that subsequence A has the first pass for following preset ordering rule relative to subsequence B System.

As shown in Figure 1B, in one embodiment, step S104 the following steps are included:

Step S124, judges whether the current data obtained should be arranged in sorting data according to preset ordering rule Otherwise the centre of two data of the same subsequence formed, executes step S164 if so, thening follow the steps S144.

In one embodiment, current data should be arranged in the same of sorting data formation according to preset ordering rule The centre of two data of one subsequence, is equivalent to, and current data should be arranged in two according to preset ordering rule The centre of sorting data, and two data belong in the same subsequence that sorting data is formed and (rather than belong to two A different subsequence).

Subsequence locating for the position is divided into two as division points by step S144, the position that should be arranged using current data A new subsequence so that ordinal relation between the internal data of two new subsequences maintain original ordinal relation it is constant, Two new subsequences are opposite with divided subsequence relative to the ordinal relation for other subsequences that sorting data is formed Ordinal relation in other subsequences be consistent and two new subsequences between ordinal relation and two new sons Ordinal relation of the data that sequence is included in divided subsequence is consistent, and enters step S154.

If current data is greater than a data in a subsequence head end data and endian data and be less than another data, The position that should be arranged according to preset ordering rule current data is then searched in the subsequence.Specifically, implementing at one In example, the position that can should be arranged according to binary chop rule searching current data.

The data that two new subsequences of ordinal relation and this between two new subsequences are included are divided Ordinal relation in subsequence is consistent, that is, is indicated, the ordinal relation between the data that divided subsequence is included In, if the data that a subsequence (being denoted as sequence 1) is included in two new subsequences (are denoted as relative to another subsequence Sequence 2) data that are included have first relationship, the then ordinal relation between two new subsequences are as follows: the subsequence (sequence 1) there is first relationship relative to another subsequence (sequence 2).

For example, the 1st sequence, the 2nd sequence and the 3rd sequence according between them ordinal relation (for example, the 1st sequence it is minimum, 2nd sequence takes second place, the 3rd sequence is maximum) to follow preset ordering rule (for example, ordering rule from small to large) arrangement as follows: 1st sequence { x₁₁x₁₂2nd sequence { x₂₁x₂₂x₂₃3rd sequence { x₃₁, wherein the data behind each sequence in bracket indicate sequence The data for being included.If the 2nd sequence divide and forms two new subsequences: { x₂₁x₂₂And { x₂₃, then this two it is new The ordinal relation for the internal data that subsequence is included maintains original ordinal relation constant, for example, subsequence divides preceding x₂₁Relatively In x₂₂With first relationship, x after subsequence divides₂₁Relative to x₂₂Or there is first relationship.

Moreover, ordinal relation and former 2nd sequence of the two new subsequences relative to former 1st sequence and former 3rd sequence Ordinal relation relative to former 1st sequence and former 3rd sequence is consistent, that is, if the 1st sequence is relative to divided subsequence With first relationship, then the 1st sequence subsequence new relative to two still has a first relationship, and the 3rd sequence is relative to being drawn The subsequence divided has in rear relationship, then the 3rd sequence subsequence new relative to two still has in rear relationship.If with sub- sequence Arranging corresponding label indicates ordinal relation between subsequence, then can be the 4th sequence by former 3rd sequence mark, new by two Subsequence is individually identified as the 2nd sequence and the 3rd sequence.

In addition, due to x₂₁And x₂₂Relative to x in divided subsequence₂₃With first relationship, therefore, x₂₁And x₂₂It is right The subsequence answered is relative to x₂₃Corresponding subsequence also has first relationship.It, can after by former 3rd sequence mark being the 4th sequence By { x₂₁x₂₂Corresponding subsequence labeled as the 2nd sequence, by { x₂₃Corresponding subsequence is labeled as the 3rd sequence.

Current data is aligned to according to preset ordering rule any one in two new subsequences by step S154 In a subsequence.

In one embodiment, son belonging to data closest with current data in two new subsequences can be obtained Current data is aligned in the subsequence belonging to this by sequence according to preset ordering rule.

Specifically, current data can be divided into current data subsequence belonging to the nearest data, and make The ordinal relation of other data follows above-mentioned preset ordinal relation in current data and the subsequence.

For example, current data is x, based on above-mentioned example, if x and x₂₂Distance be less than x and x₂₃Distance, then by x It is divided into x₂₂In affiliated subsequence, and it is above-mentioned preset suitable that the ordinal relation of x and other data in the subsequence is followed Order relation, for example, the ordinal relation between the data that subsequence is included is with the corresponding physical arrangement positional relationship of data come table Show, x₂₁And x₂₂It is sequentially stored in a continuous physical space, x₂₁It is stored in x₂₂Position before, then can be in the continuous object X is stored in x in reason space₂₂Later.In another example if the ordinal relation between the data that subsequence is included is marked with label Note, and x₂₁Corresponding label is less than x₂₂Corresponding label, then the corresponding label of settable x is greater than x₂₂Corresponding label.

Current data is aligned in established subsequence by step S164 according to preset ordering rule.

Established subsequence is the subsequence that reported data is formed.

In one embodiment, step S104 is the following steps are included: current data is formed with sorting data each Subsequence head end data and endian data are compared；

Judge the data whether current data is greater than in a subsequence head end data and endian data and is less than another A data, if so, thening follow the steps step described in S144 and S154；

Fig. 2 shows the implementation processes of step S104 in one embodiment.As shown in Fig. 2, step S104 includes following step It is rapid:

Step S202, judge the data whether current data is greater than in a subsequence head end data and endian data and Less than another data, if so, thening follow the steps S204, otherwise, step S206 is executed.

Subsequence locating for the position is divided into two as division points by step S204, the position that should be arranged using current data A new subsequence so that ordinal relation between the internal data of two new subsequences maintain original ordinal relation it is constant, Two new subsequences are opposite with divided subsequence relative to the ordinal relation for other subsequences that sorting data is formed Ordinal relation in other subsequences be consistent and two new subsequences between ordinal relation and two new sons Ordinal relation of the data that sequence is included in divided subsequence is consistent, and enters step S205.

Current data is aligned to according to preset ordering rule any one in two new subsequences by step S205 In a subsequence.

Step S206, judges whether current data is greater than in the adjacent rear end data and head end data of two adjacent subsequences One data and be less than another data, if so, then follow the steps S208, otherwise, execute step S210.

Current data is greater than a data in the adjacent rear end data and head end data of two adjacent subsequences and is less than another One data, is equivalent to, and should be arranged in the endian data of a subsequence and another according to preset ordering rule current data The centre of the head end data of one subsequence, two subsequences are adjacent, and the endian data is adjacent with the head end data.

Current data is aligned to according to preset ordering rule any one in the two adjacent subsequence by step S208 Subsequence.

In one embodiment, sub- sequence belonging to data closest with current data in the two adjacent subsequence can be obtained Current data is aligned in the subsequence belonging to this by column according to preset ordering rule.

Step S210 judges before whether should being arranged in first subsequence according to preset ordering rule current data Otherwise face, executes step S214 if so, thening follow the steps S212.

Current data is aligned in first subsequence by step S212 according to preset ordering rule.

Current data should be arranged in front of first subsequence, that is, current data should be arranged in first Before the head end data of a subsequence, in such cases, current data can be arranged in the head end data of first subsequence Before, so that current data becomes the head end data of first subsequence.

Step S214 judges whether the last one subsequence should be arranged according to preset ordering rule current data Below, if so, current data is formed a new subsequence, and the subsequence for making this new is relative to other established Subsequence is the last one subsequence.

In above-described embodiment, current data is compared with each subsequence head end data and endian data, rather than Current data is compared with each of each subsequence data, number of comparisons can be reduced, to improve data sorting Efficiency.

In above-described embodiment, current data is aligned to the closest data institute of current data according to preset ordering rule The subsequence of category can reduce the quantity for the subsequence that sorting data has been formed, to reduce the head end of current data and subsequence The number that data and endian data compare, to improve sequence efficiency.Because if two adjacent datas in same subsequence Apart from larger, then the probability that data are inserted between two data is also larger, thus by the subsequence be divided into two it is new The probability of subsequence also increases accordingly.

In one embodiment, the above-mentioned real-time sort method for real-time report data is further comprising the steps of: according to The ordinal relation between data that ordinal relation and sub-series of packets between each subsequence contain, which successively obtains in subsequence, wraps The data contained constitute ordered sequence, to obtain the corresponding ordered sequence of reported data.

If the ordinal relation of a subsequence and another subsequence are as follows: a subsequence has relative to another subsequence There is first relationship, then first obtain the data in the subsequence, obtains the data in another subsequence afterwards；

And obtain the sequence of data in each subsequence then are as follows: if a data have relative to another data it is first Relationship, then first obtain the data, obtains another data afterwards.

The real-time sort method for real-time report data in above-described embodiment, has been arranged if current data should be arranged in Ordinal number, then will as division points using the position that current data should arrange according to the centre of two data of the same subsequence of formation Subsequence locating for the position is divided into two new subsequences, and current data is aligned to this according to preset ordering rule In any one subsequence in two new subsequences, wait sorting according to the data search at subsequence head and the tail both ends to facilitate Data sorting efficiency can be improved in the arrangement position of data；And the above method to the data currently reported in sorting data shape At subsequence on the basis of be ranked up, do not change original ordinal relation between sorting data, be a kind of stable Sort method.

In one embodiment, the above-mentioned real-time sort method for real-time report data is further comprising the steps of: judgement Whether the quantity for the data that the subsequence of addition current data is included is more than or equal to threshold value, if so, the subsequence is divided into Two subsequences.

In one embodiment, which is equal to twice of the extraction of square root that reported data estimates total amount.That is, the threshold value isWherein, N is that reported data estimates total amount.To may make the data sorting algorithm of the application in a worst case scenario Time complexity be only O (N), have lower time complexity.Reported data estimate total amount be pre-estimate report The total amount of data.The reported data estimates total amount and can be set and be stored in advance.

In one embodiment, when subsequence being divided into two subsequences, it may make the number between two new subsequences Data bulk is equal or difference is no more than 1.That is, if the data bulk of subsequence is m, two new subsequences being divided into In, the data bulk of one of them new subsequence can be rounded for m/2, and the quantity of another new subsequence is then to be divided sub- sequence The difference of the data bulk of column and the data bulk (m/2 rounding) of the new subsequence.

In the present embodiment, subsequence is separated in half, subsequence can be reduced and divide number, to improve sequence efficiency.

Illustrate the above-mentioned real-time sort method for real-time report data below in conjunction with specific example.

In one embodiment, each subsequence that sorting data has been formed is with one comprising data item and pointer entry Data object indicates；Data item is for storing the data that sub-series of packets contains, and data item stores son according to preset ordering rule The data that sequence includes, data item can be fixed array or dynamic array, can also be single linked list or double linked list etc.；Pointer entry packet Forwarding pointer and consequent pointer are included, forwarding pointer is used to be directed toward the previous subsequence for having first relationship relative to this subsequence, Backwarding pointer is used to be directed toward relative to this subsequence the first relationship and to abide by rear relationship with the latter subsequence in rear relationship Follow preset ordering rule.If established subsequence is arranged according to preset ordering rule, arranged in two adjacent subsequences Preceding subsequence is arranged to be known as arranging posterior son relative to previous subsequence of the posterior subsequence with first relationship is arranged Sequence is known as the latter subsequence for having in rear relationship relative to the subsequence being arranged in front.

In one embodiment, which further includes mark and last mark at first, at first mark for marking or The data at first (namely data at first of subsequence) stored in data item are directed toward, are finally identified for marking or being directed toward data item The final data (namely final data of subsequence) of middle storage.The data that sub-series of packets contains are arranged according to preset ordering rule Column, first number therein is stated to be the data at first of subsequence, and the last one data is known as the final data of subsequence.

In one embodiment, when a subsequence is divided into two new subsequences, in order to describe simplicity, by two First subsequence is denoted as a1 in a new subsequence, and posterior subsequence is denoted as a2, and will be divided the corresponding number of subsequence It is denoted as A1 according to object, is denoted as A0 with the corresponding data object of previous subsequence of first relationship relative to subsequence is divided, A2 is denoted as with the corresponding data object of latter subsequence in rear relationship relative to subsequence is divided.Symbol in the present embodiment Number title is used only as marking relevant object being not used as limiting the present invention in order to describe.

A new data object can be created, A ' is denoted as, stores a subsequence in two new subsequences with the A ', And another new subsequence is stored with A1.

If with A ' storage a1, a2 is stored with A1, then the forwarding pointer of A ' can be directed toward A0, the backwarding pointer of A0 is directed toward A ', and the backwarding pointer of A ' is directed toward A1, the forwarding pointer of A1 is directed toward A '.

Further, a1 is stored with the data item of A ', the mark at first of A ' is directed toward the data at first in a1, most by A ' Mark is directed toward the final data in a1 afterwards.

Further, the data that a1 includes are deleted in the data item of A1, then are only left the data that a2 includes, and by A1's Mark is directed toward the data at first in a2 at first, and the last mark of A1 is had been directed to the final data in a2, because a2 is most Data are the final data for being divided subsequence afterwards, therefore the data that the last mark for not needing modification A1 is pointed.

Whenever subsequence head end or tail end be inserted into data when, then the data are arrived according to preset ordering rule storage In the data item of corresponding data object, if also, be inserted into data in head end, the mark at first of data object is modified, so that most First mark is directed toward the data of the insertion, if being inserted into data in tail end, modifies the last mark of data object, so that last mark It is directed toward the data of the insertion.

In one embodiment, it has formed subsequence to access by head pointer or tail pointer, which is directed toward The subsequence at first of subsequence is formed, tail pointer is directed toward the last subsequence for having formed subsequence.Subsequence is according to preset row Sequence is regularly arranged, and first subsequence therein is known as subsequence at first, and the last one subsequence is known as last subsequence.Son Sequence is arranged according to preset ordering rule, and all data that first sub-series of packets contains are all relative to containing in rear sub-series of packets Data all have first relationship.

Fig. 3 is the storage schematic diagram of subsequence in one embodiment.

As shown in figure 3,302,304,306 in Fig. 3 be all the data object for indicating subsequence, the forward direction of data object refers to Needle is labeled as pre, and backwarding pointer is labeled as nx, and mark is labeled as top at first, and finally mark is labeled as bot；It is directed toward sub- sequence at first The head pointer of column is labeled as head, is directed toward the tail pointer of last subsequence labeled as tail.

The data item of data object 302 successively storing data: the top of mark at first of x7, x3, x1, data object 302 are directed toward X7 finally identifies bot and is directed toward x1, illustrates that x7 has the first relationship of preset ordering rule of following relative to x3, x3 relative to X1 has the first relationship for following preset ordering rule.

Head pointer head is directed toward data object 302, and it is pre- to illustrate that the subsequence that data object 302 indicates is acted on for each subsequence If ordering rule arrangement when first subsequence.

The backwarding pointer of data object 302 is directed toward data object 304, illustrates all data phases that data object 302 stores All data stored for data object 304 all have the first relationship for following preset ordering rule.

To which the data being directed toward by the top of mark at first of the access head pointer head data object 302 being directed toward can obtain Get data x7 at first, successively access data object 302 store other data, according to access order by the data of access into Row arrangement obtains ordered sequence: x7, x3, x1.Then the data object 304 that the backwarding pointer nx of data object 302 is directed toward is accessed At first mark top be directed toward data, data x6 can be got, successively access data object 304 store other data, continue The data of access are added to ordered sequence according to access order, then obtain ordered sequence: x7, x3, x1, x6, x4, x5.According to this Continue to access and sort that ordered sequence can be obtained: x7, x3, x1, x6, x4, x5, x9, x8, x2.

It is illustrated below to by process of the data storage of real-time report into data object.

For example, successively getting the following data of real-time report: 125,267,15,1,18,230,100,66,77,50, 90,109,600,40,35,31, threshold value is arranged to 5 and (is approximately equal toWherein, 16 total amount is estimated for reported data), When i.e. the quantity of the sub-sequence data that are included is more than or equal to 5, then subsequence is divided into two new subsequences.

Successively the data of real-time report are ranked up according to sequence from small to large, Fig. 4 A to Fig. 4 B is shown each time The subsequence formed after sequence.Wherein, each horizontally-arranged multiple subsequences indicate a ranking results.Each horizontally-arranged subsequence In, ordinal relation from small to large is followed between the subsequence that arranges from left to right.It is arranged from top to bottom in each subsequence Data follow ordinal relation from small to large.

The data relationship between data that ordinal relation and sub-series of packets between subsequence contain can use above-mentioned implementation The data object of example description indicates.

As shown in Fig. 4 A to 4B, ordering iteration process is as follows:

(1) the 1st subsequence of 125 formation is taken.

(2) 267 are taken, due to 267 > 125, so forming a new subsequence for 267, and is arranged in the 1st subsequence Later.

(3) 15 are taken, due to 15 < 125, i.e., 15 less than the 1st subsequence head end data, then be arranged in the 1st son for 15 The head end of sequence becomes the new head end data of the 1st subsequence.

(4) take 1, due to 1 < 15, i.e., 1 less than the 1st subsequence head end data, then be arranged in the 1st subsequence for 1 Head end, become the new head end data of the 1st subsequence.

(5) 18 are taken, due to 15 <, 18 < 125, by the 1st subsequence be divided into two subsequences { 115 } and { 125 }, and 18 distances 15 are closer relative to 18 distances 125, therefore, by 18 be divided into 15 belonging to subsequence, by 15 arrangement To the tail end of the subsequence, become the endian data of the subsequence.

(6)~(15) successively take 230,100,66,77,50,90,109,600,40,35, are aligned to son in the manner described above In sequence, the subsequence that the alignment processes of each data are formed is corresponding in turn to the 6th to 15 horizontally-arranged listed subsequence in Fig. 4.

Since the data bulk of the 15th the 2nd horizontally-arranged subsequence is equal to 5, the 2nd subsequence is divided into two New subsequence.

(16) 31 are taken, due to 31 < 35, i.e., 31 less than the 2nd subsequence head end data, then be arranged in the 2nd son for 31 The head end of sequence becomes the new head end data of the 2nd subsequence.

Subsequence is accessed according to the ordinal relation between the ordinal relation and the data that contain of sub-series of packets between subsequence The data for including, can be obtained ordered sequence: 1,15,18,31,35,40,50,66,77,90,100,109,125,267,230, 600。

In the above-mentioned real-time sort method for real-time report data, data number of comparisons includes: current data and sub- sequence The number that included data are compared is arranged, and, time of the current data compared with the head end data of subsequence and endian data Number.If the data bulk maximum value that subsequence is included is m, the number being compared with the included data of subsequence is maximum Are as follows:

The case where considering worst, the data bulk m that subsequence is included estimates total amount N close to reported data, and current Number maximum of the data compared with the head end data of subsequence and endian data is no more than reported data and estimates total amount N.Therefore, should In the case of, the time complexity of the above-mentioned real-time sort method for real-time report data is O (N²).And it is above-mentioned in real time on In the real-time sort method of count off evidence, the quantity for the data that sub-sequence includes reachesWhen, that is, it is grouped, therefore, The time complexity of the above-mentioned real-time sort method for real-time report data is O (N), to have higher ranked efficiency.

As shown in Figure 5A, in one embodiment, a kind of real-time collator for real-time report data, including data Obtain module 50 and sorting module 52, in which:

Data acquisition module 50 is for obtaining the data currently reported.

Sorting module 52 is used to be ranked up current data on the basis of multiple subsequences that reported data is formed, There is the ordinal relation for following preset ordering rule between the data that subsequence is included, also have between subsequence and follow this The ordinal relation of preset ordering rule.

The preset ordering rule can be ordering rule or ordering rule from big to small from small to large etc..

As shown in Figure 5 B, in one embodiment, sorting module 52 includes position judging module 522, the first subsequence stroke Sub-module 524, the first sorting module 526 and the second sorting module 528, in which:

Position judging module 522 is used to judge whether the current data obtained should be arranged according to preset ordering rule The centre of two data for the same subsequence that sorting data has been formed, if so, the first subsequence division module of starting 524, otherwise, start the second sorting module 528.

The position that first subsequence division module 524 is used to arrange using current data will be locating for the position as division points Subsequence be divided into two new subsequences so that ordinal relation between the internal data of two new subsequences remains former There is the ordinal relation for other subsequences that ordinal relation is constant, two new subsequences are formed relative to sorting data and is drawn The subsequence being divided to relative to the ordinal relation of other subsequences be consistent and two new subsequences between ordinal relation Ordinal relation of the data for being included with two new subsequences in divided subsequence is consistent, further, Start the first sorting module 526.

In one embodiment, if the first subsequence division module 524 is greater than a subsequence head end number for current data According to a data in endian data and less than another data, then search in the subsequence according to preset ordering rule The position that current data should arrange.Specifically, in one embodiment, can be answered according to binary chop rule searching current data The position of the arrangement.

First sorting module 526 is used to current data being aligned to two new subsequences according to preset ordering rule In any one subsequence in.

In one embodiment, the first sorting module 526 can obtain most adjacent with current data in two new subsequences Current data is aligned in the subsequence belonging to this by subsequence belonging to close data according to preset ordering rule.

Specifically, current data can be divided into current data belonging to the nearest data by the first sorting module 526 Subsequence, and the ordinal relation of other data in current data and the subsequence is made to follow above-mentioned preset ordinal relation.

Current data is aligned in established subsequence by the second sorting module 528 according to preset ordering rule.

Established subsequence is the subsequence that reported data is formed.

As shown in fig. 6, position judging module 522 includes comparison module 602, first judgment module 604, the second judgment module 606, third judgment module 608 and the 4th judgment module 610；Second sorting module 528 includes intermediate insertion module 612, head end It is inserted into module 614, tail end is inserted into module 616, in which:

Comparison module 602 is used for each subsequence head end data and tail end number for forming current data with sorting data According to being compared.

First judgment module 604 is for judging whether current data is greater than in a subsequence head end data and endian data One data and be less than another data, if so, starting the first subsequence division module 524.

Second judgment module 606, for judge current data whether be greater than two adjacent subsequences adjacent rear end data and Data in head end data and be less than another data, if so, starting is intermediate to be inserted into module 612.

Third judgment module 608 is for judging whether first should be arranged according to preset ordering rule current data Before subsequence, if so, starting head end is inserted into module 614.

4th judgment module 610 is for judging whether last should be arranged according to preset ordering rule current data Behind a subsequence, if so, starting tail end is inserted into module 616.

Centre insertion module 612 is for current data to be aligned in two adjacent subsequences according to preset ordering rule Any one subsequence.

In one embodiment, current data can be aligned to this according to preset ordering rule by intermediate insertion module 612 Any one subsequence in two adjacent subsequences.In one embodiment, intermediate insertion module 612 can obtain the two adjacent son Current data is aligned to this according to preset ordering rule by subsequence belonging to the data closest with current data in sequence In affiliated subsequence.

Current data for being aligned in first subsequence by head end insertion module 614 according to preset ordering rule.

Current data should be arranged in front of first subsequence, that is, current data should be arranged in first Before the head end data of a subsequence, in such cases, current data can be arranged in first son by head end insertion module 614 Before the head end data of sequence, so that current data becomes the head end data of first subsequence.

Tail end is inserted into module 616 and is used to forming current data into a new subsequence, and the subsequence phase for making this new It is the last one subsequence for other established subsequences.

In one embodiment, the above-mentioned real-time collator for real-time report data further includes that ordered sequence constitutes mould Block (not shown), for according to the sequence between the ordinal relation and the data that contain of sub-series of packets between each subsequence Relationship successively obtains the data for including in subsequence and constitutes ordered sequence, to obtain the corresponding ordered sequence of reported data.

The real-time collator for real-time report data in above-described embodiment, has been arranged if current data should be arranged in Ordinal number, then will as division points using the position that current data should arrange according to the centre of two data of the same subsequence of formation Subsequence locating for the position is divided into two new subsequences, and current data is aligned to this according to preset ordering rule In any one subsequence in two new subsequences, wait sorting according to the data search at subsequence head and the tail both ends to facilitate Data sorting efficiency can be improved in the arrangement position of data；And above-mentioned apparatus to the data currently reported in sorting data shape At subsequence on the basis of be ranked up, do not change original ordinal relation between sorting data, be a kind of stable Collator.

As shown in fig. 7, in one embodiment, the above-mentioned real-time collator for real-time report data further includes quantity Judgment module 702 and the second subsequence division module 704, in which:

Whether the quantity for the data that quantity judgment module 702 is used to judge that the subsequence that current data is added is included is greater than Equal to threshold value.

If the quantity for the data that subsequence of the second subsequence division module 704 for current data to be added is included is greater than Equal to threshold value, then the subsequence is divided into two subsequences.

In one embodiment, when subsequence is divided into two subsequences by the second subsequence division module 704, two be may make Data bulk between a new subsequence is equal or difference is no more than 1.That is, being divided if the data bulk of subsequence is m At two new subsequences in, the data bulk of one of them new subsequence can be rounded for m/2, and another new subsequence Quantity is then the difference of the data bulk for being divided subsequence and the data bulk (m/2 rounding) of the new subsequence.

Illustrate the above-mentioned real-time collator for real-time report data below in conjunction with specific example.

It in one embodiment,, will be by order to describe simplicity when a subsequence is divided into two new subsequences It divides the corresponding data object of subsequence and is denoted as A1, previous subsequence of the subsequence with first relationship is corresponding relative to being divided Data object be denoted as A0, be denoted as relative to being divided subsequence and having in the corresponding data object of latter subsequence of rear relationship A2；And subsequence first in two new subsequences is denoted as a1, posterior subsequence is denoted as a2.Symbol in the present embodiment Number title is used only as marking relevant object being not used as limiting the present invention in order to describe.

First subsequence division module 524 and the second subsequence division module 704 can create a new data object, note For A ', a subsequence in two new subsequences is stored with the A ', and stores another new subsequence with A1.

If with A ' storage a2, with A1 store a1 the case where and so on, details are not described herein.

First sorting module 526 and the second sorting module 528, can whenever when the head end or tail end of subsequence are inserted into data The data are stored according to preset ordering rule into the data item of corresponding data object, if also, be inserted into data in head end, The mark at first of data object is then modified, so that mark is directed toward the data of the insertion at first, if being inserted into data in tail end, is modified The last mark of data object, so that last mark is directed toward the data of the insertion.

Each technical characteristic of embodiment described above can be combined arbitrarily, for simplicity of description, not to above-mentioned reality It applies all possible combination of each technical characteristic in example to be all described, as long as however, the combination of these technical characteristics is not deposited In contradiction, all should be considered as described in this specification.

The embodiments described above only express several embodiments of the present invention, and the description thereof is more specific and detailed, but simultaneously It cannot therefore be construed as limiting the scope of the patent.It should be pointed out that coming for those of ordinary skill in the art It says, without departing from the inventive concept of the premise, various modifications and improvements can be made, these belong to protection of the invention Range.Therefore, the scope of protection of the patent of the invention shall be subject to the appended claims.

Claims

1. a kind of real-time sort method for real-time report data, comprising the following steps:

Obtain the data currently reported；

Current data is ranked up on the basis of multiple subsequences that reported data is formed, the subsequence is included There is the ordinal relation for following preset ordering rule between data, also have between the subsequence and follow the preset sequence The ordinal relation of rule, comprising the following steps:

Judge whether current data should be arranged in the same height that sorting data is formed according to the preset ordering rule The centre of two data of sequence；

If current data should be arranged in the centre of two data for the same subsequence that sorting data has been formed, with current Subsequence locating for the position is divided into two new subsequences for division points by the position that data should arrange, and makes two Ordinal relation between the internal data of new subsequence maintains that original ordinal relation is constant, two new subsequences are relative to The ordinal relation and ordinal relation of the divided subsequence relative to other subsequences for other subsequences that sorting data is formed Be consistent and two new subsequences between ordinal relation and two new subsequences data for being included drawn The ordinal relation in subsequence divided is consistent, and current data is further aligned to this two according to preset ordering rule In any one subsequence in new subsequence；

It, will if current data should not be arranged in the centre of two data for any one subsequence that sorting data has been formed Current data is aligned in established subsequence according to preset ordering rule.

2. the real-time sort method according to claim 1 for real-time report data, which is characterized in that described on Count off includes: according to the step of being ranked up on the basis of multiple subsequences of formation to current data

Judge the data whether current data is greater than in a subsequence head end data and endian data and is less than another number According to if so, subsequence locating for the position is divided by the position that should be arranged described in executing using current data as division points The step of two new subsequences；

Judge the data whether current data is greater than in the adjacent rear end data and head end data of two adjacent subsequences and small In another data, if so, current data is aligned to according to preset ordering rule any one in two subsequences A subsequence；

Judge whether should be arranged in front of first subsequence according to preset ordering rule current data, if so, pressing Current data is aligned in first subsequence according to preset ordering rule；

Judge whether should be arranged in behind the last one subsequence according to preset ordering rule current data, if so, Current data is formed into a new subsequence, and the subsequence for making this new is last relative to other established subsequences One subsequence.

3. the real-time sort method according to claim 1 for real-time report data, which is characterized in that it is described will be current Data are aligned to the step in any one subsequence in two new subsequences according to preset ordering rule are as follows:

Subsequence belonging to data closest with current data in two new subsequences is obtained, by current data according to pre- If ordering rule be aligned in the subsequence belonging to this；

Obtain subsequence belonging to data closest with current data in the established subsequence, by current data according to Preset ordering rule is aligned in the subsequence belonging to this.

4. the real-time sort method according to claim 1 for real-time report data, which is characterized in that the method is also Include:

Judge whether the quantity for the data that the subsequence that current data is added is included is more than or equal to threshold value, if so, by the son Sequence is divided into two subsequences.

5. the real-time sort method according to claim 4 for real-time report data, which is characterized in that described threshold value etc. Twice of extraction of square root of total amount is estimated in reported data.

6. a kind of real-time collator for real-time report data characterized by comprising

Data acquisition module, for obtaining the data currently reported；

Sorting module, multiple subsequences for being formed in reported data on the basis ofs, are ranked up current data, described There is the ordinal relation for following preset ordering rule between the data that subsequence is included, also have between the subsequence and abide by Follow the ordinal relation of the preset ordering rule；

The sorting module comprises the following modules:

Position judging module, for judging whether current data should be arranged in the number that sorted according to the preset ordering rule According to the centre of two data of the same subsequence of formation, if so, otherwise the first subsequence division module of starting starts Second sorting module；

First subsequence division module, position for that should be arranged using current data are division points by sub- sequence locating for the position Column are divided into two new subsequences, and the ordinal relation between the internal data of two new subsequences is made to remain original suitable The ordinal relation for other subsequences that order relation is constant, two new subsequences are formed relative to sorting data with it is divided Subsequence relative to the ordinal relation of other subsequences be consistent and two new subsequences between ordinal relation with should Ordinal relation of the data that two new subsequences are included in divided subsequence is consistent；

First sorting module, for current data to be aligned to appointing in two new subsequences according to preset ordering rule It anticipates in a subsequence；

7. the real-time collator according to claim 6 for real-time report data, which is characterized in that sentence the position Disconnected module includes comparison module, first judgment module, the second judgment module, third judgment module and the 4th judgment module；It is described Second sorting module includes intermediate insertion module, head end insertion module, tail end insertion module, in which:

The each subsequence head end data and endian data that the comparison module is used to form current data with sorting data It is compared；

The first judgment module is for judging whether current data is greater than in a subsequence head end data and endian data one A data and be less than another data, if so, starting the first subsequence division module；

Second judgment module, for judging whether current data is greater than the adjacent rear end data and head end of two adjacent subsequences Data in data and be less than another data, if so, starting is described intermediate to be inserted into module；

Third judgment module is for judging first subsequence whether should be arranged according to preset ordering rule current data Before, if so, starting the head end insertion module；

4th judgment module is for judging last sub- sequence whether should be arranged according to preset ordering rule current data Behind column, if so, starting the tail end insertion module；

The intermediate insertion module is for current data to be aligned in described two adjacent subsequences according to preset ordering rule Any one subsequence；

Tail end insertion module is used to form current data one new subsequence, and the subsequence for making this new relative to Other established subsequences are the last one subsequence.

8. the real-time collator according to claim 6 for real-time report data, which is characterized in that the first row Sequence module is for obtaining subsequence belonging to data closest with current data in described two new subsequences, by current number It is aligned in the subsequence belonging to this according to according to preset ordering rule；

Second sorting module is for obtaining belonging to data closest with current data in the established subsequence Current data is aligned in the subsequence belonging to this by subsequence according to preset ordering rule.

9. the real-time collator according to claim 6 for real-time report data, which is characterized in that described device is also Include:

Quantity judgment module, for judging whether the quantity for the subsequence data that are included that current data is added is more than or equal to threshold Value；

Second subsequence division module, if the quantity for the data that the subsequence for current data to be added is included is more than or equal to threshold Value, then be divided into two subsequences for the subsequence.

10. the real-time collator according to claim 9 for real-time report data, which is characterized in that the threshold value Equal to twice of the extraction of square root that reported data estimates total amount.