1

Topic: Artful queue with a priority

Greetings to all! There is a sequence of elements here such type: class Item {int ID; decimal Level; decimal Measurement1;... decimal MeasurementN;} It is necessary to invent a data structure for storage of this sequence that it serviced here such algorithm: There are two flows -  and the reader. The reader should have possibility 1. To watch this sequence always arranged on Level 2. It is safe to iterate on it without locks of Obnovljatel should be able 1. To interpose new elements. That is new and what not the new is defined on Id 2. To delete existing 3. To update the measured values for existing elements. In an ideal and Level too but if it does not turn out - I will worry 4. To avoid copying of great volumes of the data at insertions and removals 5. Whenever possible to fulfill the enumerated operations for logarithmic modification time happen with a speed 10^2 in a second. Length of sequence of the order 10^4. Some independent copies of this algorithm should work in one process with different, in any way not bound copies of sequences. These copies will be the order 10^1. The reader views sequence some times in a second. It is important, that it always viewed it in decreasing order Level. It is admissible that during review  something changes. The main thing that this update did not bring down to the reader foreach and did not lead to that the review order ceases to be arranged on Level. Thoughts are twisted round queue with a priority. But here there are two independent keys, on one there is a search, and in another - sorting. The algorithm of queue known to me with a priority on the basis of a binary heap does not support it. Implementation language C#. Wanted was in Algorithms to write, but there as on a cemetery. Thanks.

2

Re: Artful queue with a priority

Hello, SergASh, you wrote: SAS> SAS> decimal Level; SAS> And what for type decimal for Level?

3

Re: Artful queue with a priority

Hello, Mihas, you wrote: M> Hello, SergASh, you wrote: SAS>> SAS>> decimal Level; SAS>> M> And what for type decimal for Level? Level fractional on a statement of the problem.

4

Re: Artful queue with a priority

Hello, SergASh, you wrote: SAS> It is necessary to invent a data structure for storage of this sequence, SAS> that it serviced here such algorithm: SAS> There are two flows -  and the reader. SAS> the reader should have possibility SAS> 1. To watch this sequence always arranged on Level SAS> 2. It is safe to iterate on it without locks SAS> Obnovljatel should be able SAS> 1. To interpose new elements. That is new and what not the new is defined on Id SAS> 2. To delete existing SAS> 3. To update the measured values for existing elements. In an ideal and Level too but if it does not turn out - I will worry SAS> 4. To avoid copying of great volumes of the data at insertions and removals SAS> 5. Whenever possible to fulfill the enumerated operations for logarithmic time While there is a sensation that it is necessary to do own  and to use non-blocking collections. SAS> changes happen with a speed 10^2 in a second. Length of sequence of the order 10^4. SAS> Some independent copies of this algorithm should work in one process with SAS> different, in any way not bound copies of sequences. These copies will be SAS> the order 10^2. At such kol-ve updates the structure with a fast insertion is necessary. The tree any artful can? And it is impossible to accumulate and apply changes them , 1 time a second on the timer, with ? SAS> the Reader views sequence some times in a second. It is important, that it always SAS> viewed it in decreasing order Level. It is admissible that during review  SAS> something changes. The main thing that this update did not bring down to the reader foreach and did not result SAS> to that the review order ceases to be arranged on Level. Without own  precisely not to manage. SAS> thoughts are twisted round queue with a priority. But here there are two independent keys, on one SAS> there is a search, and in another - sorting. The algorithm of queue known to me with priority SAS> on the basis of a binary heap does not support it. SAS> implementation language C#. SAS> Wanted was in Algorithms to write, but there as on a cemetery. I all the same in algorithms . There, , at least not  chances of the answer or at least idea. : It is the task for interview or on operation?

5

Re: Artful queue with a priority

Hello, Sharov, you wrote: S> At such kol-ve updates the structure with a fast insertion is necessary. The tree any artful can? S> and it is impossible to accumulate and apply changes them , 1 time a second on the timer, with ? It is desirable, that the reader at each review watched those updates which had time to come by the time of the iteration beginning. That is application stored should be synchronized somehow with the review beginning. So it turns out lock and still synchronization is necessary. S> without own  precisely not to manage. Mean to superimpose lock from structure modification for a while  a following element, and then to remove it while a loop body something does with the received element? S> I all the same in algorithms . There, , at least not  chances of the answer or at least idea. Doubles on  are forbidden, unless are not present? I recently on a stack  so a question simply closed in 15 minutes with the note "go learn to ask correctly". S> : It is the task for interview or on operation? Alas, the fighting task, it is necessary to get out somehow. With an amount of copies of algorithm I got excited, it will manage to be reduced with 10^2 to 10^1.

6

Re: Artful queue with a priority

Hello, SergASh, you wrote: SAS> I recently on a stack  so a question simply closed in 15 minutes with the note "go learn to ask correctly". Because the stack - about programming.  are not capable to envelop more than three lines of the text without code blobs. It is possible to try to set here: https://cs.stackexchange.com Well and generally here good discussion on this subject: https://meta.stackexchange.com/question … ware-engin Questions about designing algorithms, their correctness, or their complexity fit Computer Science best. This is likely to be the best fit for questions that you may have that arise in an algorithms course that is part of a computer science educational program. If you implement algorithms as part of the course, then questions about the coding part should be asked on Stack Overflow, e.g. "why does not my code work?" (post your whole code and explain the desired behavior), what library functions to use, etc. If your implementation is working and you want to make it better, take it to Code Review. Questions about algorithms in the context of analyzing and designing software systems are a good fit on Software Engineering. Questions about numerical algorithms in the context of applications to other sciences (statistics, physics, biology, etc.) may be a better fit for Computational Science. Research-level questions may also be suitable on Theoretical Computer Science.

7

Re: Artful queue with a priority

Hello, SergASh, you wrote: SAS> Thoughts are twisted round queue with a priority. But here there are two independent keys, on one SAS> there is a search, and in another - sorting. The algorithm of queue known to me with priority SAS> on the basis of a binary heap does not support it. Two keys - two binary tree at which nodes to contain the general object representing value, or other structures working with key-value. And remaining it is simple operation with flows.

8

Re: Artful queue with a priority

Hello, SergASh, you wrote: SAS> It is desirable, that the reader at each review watched those updates which had time to come to SAS> to the moment of the beginning of iteration. That is application stored should be synchronized somehow with beginning SAS> review. So it turns out lock and still synchronization is necessary. In the elementary case yes, on idea kol-in elements in one queue small, lock can and approaches on productivity. It is necessary to measure. S>> without own  precisely not to manage. SAS> mean to superimpose lock from structure modification for a while  following SAS> an element, and then to remove it while a loop body something does with the received element? That  judging by the task description there should be the is, , the fact. Lock strategy is already big question. To lock on each element is big lock contention. Lock on 20 elements can? Here besides it is necessary to measure. S>> I all the same in algorithms . There, , at least not  chances of the answer or at least idea. SAS> doubles on  are forbidden, unless are not present? It is possible to transfer entirely a subject in . Or the moderator to ask. Tags moderating see and to inform the moderator. SAS> I recently on a stack  so a question simply closed in 15 minutes with the note "go learn to ask correctly". There can, yes.

9

Re: Artful queue with a priority

Hello, SergASh, you wrote: Not so I understand, in what here a problem.  one! Give on the simple: we implement this collection in the form of the single-connected list. The iterator runs on it strictly "forward". For modifications we use that update of links at us : 1. An insertion. Finding a place for a new element, we at first initialize next to it (it is still invisible to readers). And already then  we change next to the previous element. Those who had time to pass on old next, do not see a new element. Those who was not in time - pass on new next. 2. Removal. Here generally all is simple - we update exactly one next-index, throwing out a deleted element from the list. Thus next deleted still ; if somewhere the reader which iterator specifies in a deleted element at awakening he goes on "following", etc. nearby "sleeps" Even if we will have a set of removals, the reader can "pass" till the end of the list. Thus he risks to read very many already remote elements - depending on the removal order, but it is "an insulation" singularity. 3. Change. We do in three steps: - we prepare new element New. - it is initialized it New. Next in Old. Next -  it is replaced Prev. Next with Old on New. 4. Change with relocation - is not quite clear, whether repeated iteration is terrible. Roughly speaking, when the reader reads up almost up to the end, and here "end" suddenly leaves in the beginning - whether the reader should read again all those elements which he just already read? If it is not terrible - that the algorithm too is trivial.

10

Re: Artful queue with a priority

Hello, Sinclair, you wrote: S> 4. Change with relocation - is not quite clear, whether repeated iteration is terrible. Roughly speaking, when the reader reads up almost up to the end, and here "end" suddenly leaves in the beginning - whether the reader should read again all those elements which he just already read? If it is not terrible - that the algorithm too is trivial. Here, as I understood, it is a question of change Level'. If the reader anew goes on already read elements within the limits of one iteration it breaks the orderliness requirement at bypass. If it manages to be solved somehow for the final decision still it is required two indexes, one on Id, and another on Level', specifying in the beginning of the subsequence corresponding to it Level'

11

Re: Artful queue with a priority

Hello, Qulac, you wrote: Q> Two keys - two binary tree at which nodes to contain the general object representing value, or other structures working with key-value. And remaining it is simple operation with flows. Tree traversal demands lock therefore as the insertion-rebalancing in it cannot be atomic, well or on an extreme measure I do not know as it to make atomic Sinclair offered a perspective variant.

12

Re: Artful queue with a priority

Hello, SergASh, you wrote: SAS> Hello, Qulac, you wrote: Q>> Two keys - two binary tree at which nodes to contain the general object representing value, or other structures working with key-value. And remaining it is simple operation with flows. SAS> tree traversal demands lock therefore as the insertion-rebalancing in it cannot be atomic, well or on an extreme measure I do not know as it to make atomic SAS> Sinclair offered a perspective variant. Elementary quality of operations is such exterior api, and inside quite to themselves there live locks which are implemented either a program or hardware method. Hardly here generally it is possible to do without locks. In this task where it is more important to provide the necessary behavior of the iterator at change of the readable data, and for this purpose it needs to be formalized somehow.

13

Re: Artful queue with a priority

Hello, SergASh, you wrote: SAS> Hello, Sinclair, you wrote: S>> 4. Change with relocation - is not quite clear, whether repeated iteration is terrible. Roughly speaking, when the reader reads up almost up to the end, and here "end" suddenly leaves in the beginning - whether the reader should read again all those elements which he just already read? If it is not terrible - that the algorithm too is trivial. SAS> Here as I understood, it is a question of change Level'. If the reader anew goes on already read elements within the limits of one iteration it breaks the orderliness requirement at bypass. In that case we get a clone of a changeable element, and we interpose it into a new place. The reader who has begun iteration, will move ahead on Next, ignoring change until begins iteration anew. SAS> If it will be possible to solve somehow for the final decision still it is required two indexes, one on Id, and another on Level', specifying in the beginning of the subsequence corresponding to it Level' is not clear, what for. On a condition, the reader is able to be iterated only. Be afraid O (N) by search of a place for an insertion? To begin with it would be necessary to be convinced that the stupid algorithm is insufficiently fast. Otherwise there is a risk to receive unjustified complication. Well, and locks in itself - a piece rather not cheap, and easily can eat all scoring from O (logN).

14

Re: Artful queue with a priority

Hello, Sinclair, you wrote: S>>> 4. Change with relocation - is not quite clear, whether repeated iteration is terrible. Roughly speaking, when the reader reads up almost up to the end, and here "end" suddenly leaves in the beginning - whether the reader should read again all those elements which he just already read? If it is not terrible - that the algorithm too is trivial. SAS>> Here as I understood, it is a question of change Level'. If the reader anew goes on already read elements within the limits of one iteration it breaks the orderliness requirement at bypass. S> in that case we get a clone of a changeable element, and we interpose it into a new place. The reader who has begun iteration, will move ahead on Next, ignoring change until begins iteration anew. SAS>> If it will be possible to solve somehow for the final decision still it is required two indexes, one on Id, and another on Level', specifying in the beginning of the subsequence corresponding to it Level' S> is not clear, what for. On a condition, the reader is able to be iterated only. S> Be afraid O (N) by search of a place for an insertion? S> to begin with it would be necessary to be convinced that the stupid algorithm is insufficiently fast. Certainly I will try in a simple way at first. S> Differently there is a risk to receive unjustified complication. Well, and locks in itself - a piece rather not cheap, and easily can eat all scoring from O (logN). So after all these indexes are necessary only . As, how you reminded me, it one, what for here locks?

15

Re: Artful queue with a priority

Hello, Qulac, you wrote: Q> Elementary quality of operations is such exterior api, and inside quite to themselves there live locks which are implemented either a program or hardware method. Hardly here generally it is possible to do without locks. In this task where it is more important to provide the necessary behavior of the iterator at change of the readable data, and for this purpose it needs to be formalized somehow. There are no there locks, there . Atomic instructions of the processor are used - https://en.wikipedia.org/wiki/Compare-and-swap

16

Re: Artful queue with a priority

Hello, Sharov, you wrote: S> Hello, Qulac, you wrote: Q>> Elementary quality of operations is such exterior api, and inside quite to themselves there live locks which are implemented either a program or hardware method. Hardly here generally it is possible to do without locks. In this task where it is more important to provide the necessary behavior of the iterator at change of the readable data, and for this purpose it needs to be formalized somehow. S> there are no there locks, there . Atomic instructions of the processor are used - https://en.wikipedia.org/wiki/Compare-and-swap I.e. a hardware method as the device does not allow.