|
In the classic producer/consumer problem using a bounded buffer, is it typical that a producer signals the consumer immediately after producing an item and adding it to the buffer, or does the producer wait until the buffer has become full, i.e. the producer checks after producing an item to see if the buffer is full, if so, it signals the consumer?
I'm trying to wrap my head around this pattern. In my multithreaded programming book[^], it illustrates the producer/consumer architecture with a picture of a conveyer belt. At one end is the producer putting items on the belt. At the other end is a consumer taking items off the belt.
However, in looking at the accompanying code, it looks as though the producer signals the consumer after each item is produced (I may be misreading the code). If so, it seems to me that there would only be at most one item on the belt [edit] assuming that they work at the same speed [/edit].
I'm basically trying to figure out how there can be multiple objects in the buffer. A typical scenario, I think, would be that the producer places an item in the buffer and signals the consumer. The consumer removes the item from the buffer and, erm, consumes it.
It releases the buffer immediately after removing the item and signals the producer so that the producer can add more items. As the consumer is comsuming the item, the producer, if it is faster than the consumer, can add several items to the buffer. Either the buffer fills up and the producer has to wait, or the consumer finishes consuming the item and removes another from the buffer.
Is this correct?
The above is how my DelegateQueue[^] works, except that it uses an unbounded buffer, which is a little dangerous, I know.
|
|
|
|
|
Hi,
AFAIK the producer/consumer pattern aims at maximum decoupling of producer and consumer,
that means each of them should be given maximum opportunity to work; hence, the
producer should signal its consumer(s) as soon as something becomes available
(=queue not empty), and the consumer should signal its producer(s) when more could
be produced (=queue not full).
One interesting implementation has two queues, an "idle" one with empty buckets,
and a "work" one with full buckets. A producer takes an empty bucket from the idle
queue, fills it and puts it in the work queue; a consumer takes a full bucket from
the work queue, executes it, and returns the empty bucket to the idle queue.
If both queues have equal capacity, this results in a symmetric situation where a
producer gets triggered by idle queue no longer empty, and consumer gets triggered
by work queue no longer empty.
Hope this helps.
|
|
|
|
|
Luc Pattyn wrote: One interesting implementation has two queues, an "idle" one with empty buckets,
and a "work" one with full buckets. A producer takes an empty bucket from the idle
queue, fills it and puts it in the work queue; a consumer takes a full bucket from
the work queue, executes it, and returns the empty bucket to the idle queue.
If both queues have equal capacity, this results in a symmetric situation where a
producer gets triggered by idle queue no longer empty, and consumer gets triggered
by work queue no longer empty.
Very interesting. I had not heard of this approach before.
Luc Pattyn wrote: Hope this helps.
All of your replies to my posts have been helpful, thank you.
|
|
|
|
|
Well, this seems like a basic data structure question that most experienced programmers would know the answer to, but I've been kinda going in circles on it.
If you look at the members of the IList[^] interface, you get the impression that some of these operations would best be implemented using a linked list and others an array. It's as if the interface wants to have its cake and eat it, too.
The ArrayList[^] class uses a resizeable array to implement the interface.
Arrays are great for accessing elements with O(1) efficiency, while linked lists provide O(n) efficiency. However, insertions into the middle of an array will cause you to have to move the subsequent items further down the array. And if you run out of room, the entire array will need to be copied into a larger array. Linked lists don't suffer from this problem.
Seems to me that index access is the only advantage arrays have in this context over linked lists. I've been trying to think of a way to combine the two data structures to get the advantages of both. A binary tree or skip list with index access algorithms seems to be the closest I can get.
|
|
|
|
|
Leslie Sanford wrote: If you look at the members of the IList[^] interface, you get the impression that some of these operations would best be implemented using a linked list and others an array. It's as if the interface wants to have its cake and eat it, too
Well that often happens: an interface hides the possible implementations;
it is rather user oriented, and not implementation oriented.
So it offers what the user may need, and depending on some circumstances you may
choose a different implementation (e.g. a real linked-list if insertion becomes
predominant, a simple array/arraylist if items mainly get replaced/added and/or
order is not important).
If there were one type of list that would make every one happy, then arrays,
arraylists (and the whole IList interface) would have been obsolete for a long time...
|
|
|
|
|
Leslie Sanford wrote: I've been trying to think of a way to combine the two data structures to get the advantages of both.
Hashtable. Of course, it has its own disadvantages.
----
It appears that everybody is under the impression that I approve of the documentation. You probably also blame Ken Burns for supporting slavery.
--Raymond Chen on MSDN
|
|
|
|
|
Shog9 wrote: Hashtable. Of course, it has its own disadvantages.
I was thinking hashtable in conjunction with a linked list might come close to giving the best of both worlds. If you need in order traversal, you iterate through the linked list. If you need to remove an item, you look it up in the hashtable first (the items serve as keys while the linked list nodes are the values for each entry into the hashtable), get the linked list node, and remove it from the list. This saves having to traverse the list to find the node that needs to be removed.
This has the problem of duplicating the list in the hashtable, which may not be reasonable if the list is large and memory use is a concern. But more importantly for me is that I can't think how the hashtable/linked list combo gives you O(1) index access as an array does. In fact, I can't think of how to access the items in the hashtable by index at all.
|
|
|
|
|
Leslie Sanford wrote: In fact, I can't think of how to access the items in the hashtable by index at all.
A perfect hash would give you O(1) - the hash would be guaranteed to correspond to only one entry in the table. Whether or not a perfect hash is feasible depends a lot on what you're using for keys, as well as how much time is acceptable for calculating the hash.
But i was thinking more along the lines of chained hash tables[^], which are essentially an array of linked lists - this is the technique used by MFC's various CMap classes. Their performance can be very consistent but iteration tends to be rather poor unless table size and hash functions are chosen carefully.
----
It appears that everybody is under the impression that I approve of the documentation. You probably also blame Ken Burns for supporting slavery.
--Raymond Chen on MSDN
|
|
|
|
|
Shog9 wrote: A perfect hash would give you O(1) - the hash would be guaranteed to correspond to only one entry in the table. Whether or not a perfect hash is feasible depends a lot on what you're using for keys, as well as how much time is acceptable for calculating the hash.
Understood. But just to be clear, what I meant by not knowing how to access items in a hashtable by index was that I don't know how you could treat a hashtable as an array. Say you're using keys of a certain type. To get the value associated with the a key in a hashtable, you do this:
Value someValue = hashTable[someKey];
However, say we want the 10th item added to the hashtable. I don't know how we do this:
Value someValue = hashTable[9];
We can't treat the index itself as a key because as items are removed or inserted somewhere at the beginning or middle, we'd have to update all of the subsequent indexes; we're back where we started from.
Shog9 wrote: But i was thinking more along the lines of chained hash tables[^], which are essentially an array of linked lists - this is the technique used by MFC's various CMap classes. Their performance can be very consistent but iteration tends to be rather poor unless table size and hash functions are chosen carefully.
I could see how this would work for simulating an array. Have a linked list with each node containing a linked list. Limit the number of items each list to some arbitrary number like 16. Then if you need to reach the nth item, you can skip over a large number of items at a time. I can see problems with this as items are deleted; you'd wind up with some nodes not having very many items in their list. At any rate, the more I think about this, the more I get the feeling that I'm just reinventing the tree and my brain starts to short circuit.
|
|
|
|
|
Leslie Sanford wrote: But just to be clear, what I meant by not knowing how to access items in a hashtable by index was that I don't know how you could treat a hashtable as an array.
 Of course... i didn't read carefully. 
I suppose you could still manage this with a hash table, provided the data was known ahead of time... but that's hardly a general-purpose solution. Realistically, i'd probably go with an array + some sort of associative container (hashtable or tree) and just rebuild the array after adding or removing items. But it'd depend a lot on the situation; if constant-time lookups weren't absolutely essential, i might just fall back on iterating to the nth item; in the case of a sorted hash table, this could be optimized by storing the number of items in each bucket (or even an index offset), reducing the operation to iterating to the correct bucket then through that list to the correct item. Honestly can't say that this has been a requirement for anything i've actually done though.
----
It appears that everybody is under the impression that I approve of the documentation. You probably also blame Ken Burns for supporting slavery.
--Raymond Chen on MSDN
|
|
|
|
|
Maybe there is scope for improving things with threading, as time goes on we will have more and more parallel processing available. So why not a list type structure with an associated indexing array, simply of pointers, which updates in a secondary thread. This would be completely transparent to the user, allowing indexed access in O(1) time, unless the primary thread blocks when the user tries to access the array using indexing and the indexing array is being updated. There are clearly some threading issues to be resolved, but it should be possible to come up with a simple clean system. There are probably other types of structures that could benefit from some behind the scenes processing, lists that keep themselves sorted comes to mind. Maybe we should patent this - someone probably has aleady.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
I wrote a small class implementing the CollectionBase class that uses a hashtable for the indexes into the list, that are accessed by some key.
The benefit is O(logn) access coupled with an array that can be bound to a combo, list, or grid.
This statement was never false.
|
|
|
|
|
public class HybridList: System.Collections.CollectionBase
{
Hashtable _indicesTable = new Hashtable();
public int IndexOf(object key)
{
if(_indicesTable.ContainsKey(key))
return (int)_indicesTable[key];
else
return -1;
}
public int Add(object key, object val)
{
int index = List.Add(new DictionaryEntry(key, val));
_indicesTable[key] = index;
return index;
}
public void Remove(object key)
{
if(_indicesTable.ContainsKey(key))
{
List.RemoveAt((int)_indicesTable[key]);
_indicesTable.Remove(key);
int i = 0;
foreach(DictionaryEntry entry in List)
_indicesTable[entry.Key] = i++;
}
}
public DictionaryEntry this[int index]
{
get { return ((DictionaryEntry)List[index]); }
}
public object this[object key]
{
get
{
if(_indicesTable.ContainsKey(key))
return ((DictionaryEntry)List[(int)_indicesTable[key]]).Value;
else
return null;
}
}
public ICollection AllKeys
{
get { return _indicesTable.Keys; }
}
protected override void OnClear()
{
base.OnClear();
_indicesTable.Clear();
}
}
This statement was never false.
|
|
|
|
|
Thanks for the source code. The Remove operation makes me a little nervous in that it appears to be an O(n) operation, and that's what I'm trying to get away from. However, if items are rarely removed from the collection, then this looks like an interesting approach.
|
|
|
|
|
Yeah, its definately not perfect. That remove operation was a hasty addition too. But I rarely use it. But having the indices in the table and having them change upon removal of one demands it. It might even be worse than O(n). Maybe even n<super>2. 
This statement was never false.
|
|
|
|
|
Sounds like you're describing the good old hash table.
Steve
|
|
|
|
|
Ternary Search Trees[^] are an interesting solution. Boost's Spirit library uses them in its symbol tables.
Steve
|
|
|
|
|
Someone can indicate an algorithm or example of code to find the point of intersection of 2 lines?
Thanks.
|
|
|
|
|
Can U tell me the equation of the line?
Bcos line can be represented in several ways:
1.y=mx+c
2.(y-y1)/(y2-y1)=(x-x1)/(x2-x1)
3.and so on.
Regards,
Arun Kumar.A
|
|
|
|
|
I am a performance analyst. When profiling performance I usually end up with a bunch of numbers that I average and this gives me a rough idea of how a algorithm performs. I occasionally end up with variations which significantly throw out the average, sometimes unfairly.
1.8925
1.8344
4.0433
1.9026
1.7559
1.7898
3.917
1.8873
2.4083
So lets say I end up the above list of numbers, how do I weight the average so it more fairly reflects that most of the numbers are ~1.8 ?
|
|
|
|
|
Ray Kinsella wrote: I occasionally end up with variations which significantly throw out the average, sometimes unfairly.
Yes, outliers do that when dealing with averages. Use the median instead, or remove the outliers (may not be a good idea). You could also use square roots or logarithms to "smooth" the data.
"A good athlete is the result of a good and worthy opponent." - David Crow
"To have a respect for ourselves guides our morals; to have deference for others governs our manners." - Laurence Sterne
|
|
|
|
|
I was asked to write the multiply table in c, output will be something like :
1 2 3 4 5 6 7
2 4 6 8 ..
....etc
for 12, so I did it like this
for (a=1;a<=12;a++)
{
for (b=1;b<=12;b++)
printf("%d",a*b);
printf("\n");
}
That works, but I was wondering if there exeist another solution to the same problem using only ONE loop ?
|
|
|
|
|
|
Quickly looking at this the closed solution formula is
f(n) = 2^(n-1)
so the loop would be
<br />
for (a=1;a<=12;a++)<br />
{<br />
printf(2^(a-1));<br />
}<br />
F
|
|
|
|
|
Hi,
I have a number of still images containing concentric circles and I would like to be able to detect the centre point of the circles. Are there any algorithms out there that would allow me to do this?
Cheers,
Tony
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
