Re: C# Deque found on the web--thanks to The Game Programming Wiki

Jon Skeet [C# MVP] wrote:
I'm curious what it is about your implementation that makes insertion of new items faster than if using a linked list?

The queue is ordered by priority, so it can use a binary search to find the correct insertion point. Binary search on a linked list isn't terribly fast :)

Well, not on an actual linked list. On a SortedList, it'd be fast, but then you have problems with insertions and removals and keeping the tree balanced, that sort of thing.

Admittedly it won't matter unless you've got thousands of items on the queue...

Nope. And I'd suggest that a more traditional approach, maintaining an ordered list of queues would work fine too (assuming that for a given priority, tasks are still FIFO). The ordered list could be a SortedList if one wants, but I think a regular list (linked or otherwise) maintained by insertion sort would be fine, given that the number of unique priorities is likely to be low.

You could have your queues and eat them too. :)

Pete
.

Relevant Pages

  • Re: Lahman, how ya doing?
    ... >> A priority queue is an interesting idea. ... So Timer just enqueues the event on the right queue. ... >effectively starts at the same time on the current tick. ... >was triggered just gets time-sliced based on priority. ...
    (comp.object)
  • Re: Lahman, how ya doing?
    ... Suppose you had 64 Thermometers and at run time you wanted to give priority to some of them dynamically (e.g., where the temperature gradient was greatest) because processing all 64 samples at once can't be done in a single "tick". ... So Timer just enqueues the event on the right queue. ... So I addressed both the bitmap processing basics via indexed OR mask and the deferredBitmap variable assumption about bit count. ...
    (comp.object)
  • Re: cooperative multitasking scheme
    ... >> equal priority or where priorities aren't specifically used. ... where I choose not to use preemption at ... the action of the timing event is to move the process from the sleep queue ... I very much appreciate having a sleep queue. ...
    (comp.arch.embedded)
  • Re: Best way to design multithreading application
    ... The data acquisition is more important than UI updates, ... adding it to a Queue 1 as it acquires more. ... B, which is medium-to-high priority, loops over and over, and when it ... But when the threads involved are dependent on each other, as they are here, it makes little sense to make one thread higher priority than another, and for the reason you note: you really do need each of these threads to, at least on average, process the data at the same rate, otherwise you will eventually consume all your resources (memory in this case, though having the UI lag behind the actual processing is probably not desirable either). ...
    (microsoft.public.dotnet.framework)
  • Re: So... What are the alternatives? Was: I dont use an RTOS because...
    ... This configuration parameter decides whether or not preemption is allowed. ... queue will be treated as though they have equal priority. ... The real-time clock serves two primary purposes in my O/S. ...
    (comp.arch.embedded)