Author |
Topic: shared memory queues (Read 516 times) |
|
cuckoo
Junior Member
Gender: 
Posts: 57
|
 |
shared memory queues
« on: Jul 24th, 2007, 10:43pm » |
 Quote  Modify
|
Give a good data structure for having n queues (n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space.
Any good ideas?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: shared memory queues
« Reply #1 on: Jul 25th, 2007, 12:44am » |
Quote Modify
|
You could use an list/tree/heap of linked lists.
Of course that'd waste a lot of space on pointers if the elements you store are small.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sk
Newbie
Posts: 45
|
|
Re: shared memory queues
« Reply #2 on: Sep 3rd, 2007, 7:45pm » |
Quote Modify
|
u can use a circular queue with n heads and tails.
queue full condition is checked if the tail hits the next head.
tail[i] hits head[i+1%n];
whenever a new queue has to be created, the space between the last tail and the first head can be divided into 2 segments and the new queue head can be assigned to lasttail + (lasttail - firsthead)/2 % n.
Maybe some math can be adjusted here to determine which is the best alocation.
-----
other alternative
as towr suggested list of queues, or trees
|
| « Last Edit: Sep 3rd, 2007, 7:45pm by sk » |
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: shared memory queues
« Reply #3 on: Sep 4th, 2007, 1:34am » |
Quote Modify
|
I don't quiet get the reason behind using a list/tree/heap of linked list, as towr has said. Are we using the list/tree/heap to assign some kind of priority to the queues?
|
|
IP Logged |
All signatures are false.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: shared memory queues
« Reply #4 on: Sep 4th, 2007, 4:44am » |
Quote Modify
|
on Sep 4th, 2007, 1:34am, gotit wrote:| I don't quiet get the reason behind using a list/tree/heap of linked list, as towr has said. Are we using the list/tree/heap to assign some kind of priority to the queues? |
|
Or some kind of sorting.
It really depends on why we want n different queues in the first place.
In any case we need a datastructure to tie the n queues together in some way, and since n is not fixed, we need a variable datastructure to do this. Lists, trees and heaps then come to mind.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print