|
My code is based on the pg src(Postgres Sql).Do you know well about the pg source?
The child thread serves the client,
it means it has a lot of other works to do and has to response to the client. it is not acceptable when the child thread halt and no response for a long time. And what i try to do is to allocate serval share small buf for all children use. When any child needs to use the buf, it can find one available from buf array and just put the data into it, release the buf quickly and do its other jobs. Master thread can process all msgs in the buf array one by one. It takes very short time for each msg to be handled by master.And buf is large enough for their using. That's the situation.
|
|
|
|
|
Hi,
no I have no experience with Postgres SQL, but that won't matter much I think.
donniehan wrote: It takes very short time for each msg to be handled by master.
That is very good. It will be key to your system working well.
My simple design would consist of:
- a single Message class that will be instantiated a number of times; the instances will be recycled without loading the garbage collector.
- an "emptyCollection" holding a number of empty message objects; think of it as a queue, although other kinds of collections could work too.
- an "emptyLock" object used to guard operations on emptyCollection;
- a "filledCollection" holding a number of filled message objects; again think of it as a queue.
- a "filledLock" object used to guard operations on filledCollection.
- emptyCollection+emptyLock and filledCollection+filledLock could be two instances of a single class MySafeCollection.
The initialization code would create a sufficient number of message instances and put them in the emptyCollection; the filledCollection is still empty.
Then the system really starts and performs these steps:
1. the producers obtain a message object quickly (getting one from emptyCollection, this must be protected by locking on emptyLock, which never will take long);
2. let the producer fill the message object;
3. let the producer put its filled message into the "filledCollection", using the filledLock, which again will not take long.
4. let the consumer obtain a filled message object from the filledCollection(again shortly using the filledLock).
5. let the consumer process the message; as this is a short operation and should never become a bottleneck I would consider doing this on a thread with slightly higher priority.
6. let the consumer return the message to the "emptyCollection" using the emptyLock.
Possible refinements:
A. You still need a signaling mechanism: each time a producer adds something to the filledCollection, it should send a signal to the single consumer, so it goes and fetches one (or more) messages from the filledCollection. This avoids the need for a polling loop in which the consumer would waste CPU cycles when no messages got filles.
B. A producer needing a message object and not finding one in the "emptyCollection" could create a new one; that would make the initialization unnecessary, however when things go terribly wrong, you may end up with a huge number of messages in the filledCollection.
I have implemented the above scheme numerous times inside embedded systems (i.e.using a proprietary operating system, not .NET or Windows). I know it works very well and is very performant.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Hi
thanks for your great idea.
But i still have a few problems:
1st, i can only use pure C to program(Well, it will not be the real problem,i can use structure instead )
2nd, the size of each message is not fixed. a message maybe very small(16B) or very big(>10KB). if i apply your idea to my system, it will make tiny memory pieces in this share memory, so i must implement a function to recycle the memory pieces and it will also cost some time. When the system is very busy and producer create many msgs, the system must call recycle function frequently to avoid memory pieces problem and it will cost much time to do recycle work.---------->That's the big problem for me! 
The Share Memory is a block of contiguous memory allocated at first system startup. The maxsize of this Share Memory is fixed. it is not allowed to allocate another free share memory after system startup.
It is a quite annoying problem, isn't it? 
|
|
|
|
|
Hi,
1.
language does not really matter, I've done what I suggested in C many times.
2.
when message size isn't fixed, I find it easiest to use a few different fixed sizes; i.e. I would define appropriate values size1<size2<size3 (with size3 large enough to hold any message); and preallocate a number of buffers for each of those; then use as many emptyCollections as there are sizes, and use only one filledCollection.
3.
Not sure why you would need contiguous memory, unless some DMA-based peripheral is involved.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
modified on Monday, September 21, 2009 8:06 AM
|
|
|
|
|
hehe~~~
Thanks again for your help!
I almost solve this problem. 
|
|
|
|
|
I fixed a HTML problem in my previous post.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Can anyone guide me how to write the Hough circular transform?
|
|
|
|
|
This is used to recognize a circle in an image with incomplete data and/or noise. Every white pixel (assuming a black background) is evidence for a circle that goes through it. You go through all the white pixels and accumulate evidence for all the possible circles. The circle with the most evidence is the result of the Hough transform.
When you find a white pixel, it could be on many circles of radius r. In fact, every point that's distance r away from the white pixel COULD be the center of the circle. In other words, a white pixel is evidence for the center of the circle at all points r away from the pixel, i.e. a new circle with center at the white pixel and radius r.
So you start with an array with all cells set to zero. For every white pixel, increment all array cells at distance r from the white pixel. When you're done, the cell with the highest score is probably the center of the circle.
|
|
|
|
|
Great explanation. What would you suggest for finding circles of arbitrary size though, so radius r is unknown?
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
In that case, you have a three-dimensional space for the circle parameters: center X, center Y, and r.
So instead of a two-dimensional array, you have a three-dimensional array where the extra dimension is for the radius.
When you hit a white pixel, you increment the cells in a circle at EACH level in the r dimension (with the radius given by the r level). As in the two-dimensional case, the cell with the highest score gives the parameters for the circle with the most evidence. But here the r level also gives you the radius.
|
|
|
|
|
I understand that, however now you are using a lot of memory (it has one more dimension than the original image) and incrementing a huge number of counters. Seems like it will take forever, I would hope there is something with better performance...
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
This is a bit of a hack, but it worked fine for me and was quicker then a hough trans.
I was suppose to detect black framed circles in a microscopy image.
What I did was generatin a circle template, starting with 4 pixel in diameter and increase to the width of the image. At each step I correlated my circle template with the image. The highest scoring correlation output was stored. So in the end you know where and which size the circles are.
I did this in Matlab where it was actually easy to do and it was quicker then the hough trans detection and normally more accurate as well.
Cheers
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
These days memory is cheap, and it's possible to draw a circle quickly using only fast integer operations: http://en.wikipedia.org/wiki/Midpoint_circle_algorithm[^].
If you have bounds on the circle's radius, there are a couple of optimizations:
1. It limits the size of the 3D array in the r dimension, and
2. You can preprocess the image to remove convex blobs with radius greater than the minimum radius. These blobs are just noise, and eliminate lots of white pixels which reduces processing time.
|
|
|
|
|
Yep. Actually we did the circle algorithm once in hardware, eons ago, using simple TTL logic. A priority encoder (74148 IIRC) works wonders here (today I would use FPGAs, not TTL).
And another reply hinted on radius estimation. So things start to look better and better.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Luc,
That was also my immediate question. What might be done is to just scan the image for the white (or black) pixels and set the array values just to a 1 for the pixel position itself. Once done, look for adjacent pixels in the first array (horizontally, vertically, or diagnally), either immediately adjacent or separated by 1 pixel (or two or three or ... if a very sparse image). Once such a pair is found, walk the adjacent pixels at both ends to extend the string, then create the equation of a line through the endpoints (a chord), and more importantly, the equation of the perpendicular bisector of the chord, saving this bisector's equation (y = mx+b, slope intercept form). Watch out for a joined line (a complete circular arc - on a clear disk you can seek forever), if found, take the lowest (or highest) 1/4 of the pixels as one arc, and the leftmost (or rightmost) 1/4 of the pixels as the other arc (saving these two arcs in a special array of pairs). Erase the found points in the array, and look for other arcs (connected or not). Now for the fun. Calculate the intersections of the bisectors, starting with the circular pairs (giving the center of the circle and the distance from the center to all ends, averaged, as the radius), then on to the disjointed arcs. For the disjointed arcs, calculate a possible center for all combinations, and choose the closest groupings as a center, eliminate these arcs and repeat (maybe more than 1 circle in the image). Caution, since this is an image, the image of a circular disk could appear as an ellipse and not a circle.
Think this might work?
Dave.
Edit: all of the other answers came in while I was writing this up!
modified on Wednesday, September 16, 2009 11:29 AM
|
|
|
|
|
For one full or partial circle, lots of schemes would work.
Things become interesting when only some small fractions of a circle are visible, and/or multiple circles are intersecting, making "walk the circle" rather tricky; one would need some restraints to the walk and split the chords when in doubt.
Maybe your walking should be used to put some limits on the radius, before applying Hough transform on those pixels.
Luc Pattyn
Have a look at my entry for the lean-and-mean competition; please provide comments, feedback, discussion, and don’t forget to vote for it! Thank you.
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|
|
Hi,,,Thanks for your reply...I will try as per your suggestion and get back..
|
|
|
|
|
Hi,
I need to count the no of circles in the image...
Can anyone help ne regarding the same...
I am developing the application in .Net...
It is very urgent requirment for me...
|
|
|
|
|
See my reply (above) to your following question. This is how to find the clearest circle in the image.
To count the circles, apply the above algorithm, then increment your counter and delete the clearest circle from the image. Repeat until the circle evidence is too low to indicate any more circles remaining. (Some experimentation will suggest a threshold for this.)
|
|
|
|
|
You can also see mine from above. I don't know if it helps but it worked for me.
Cheers
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
Hello ! I'm making cut optimization software, and have problem with the cut optimization algorithm.
I have one big rectangle, and x smaller rectangles (that may and may not be of the same size). Now I need way to calculate optimum position of these rectangles, so that as many as it is possible can fit into big one ... Also I need to draw that positions somehow ...
Can anybody help ?
Thanks
|
|
|
|
|
It depends. Do you know more about the possible sizes of the small rectangles? For some combinations of sizes a simple greedy approach would be optimal.
Also, are the rectangles allowed to be turned 90 degrees?
|
|
|
|
|
Yes, rectangles are allowed to be turned 90 degrees. I don't know possible sizes, they can be anything.
Is there any way to somehow calculate coordinates of rectangles inside big rectangle?
What do you mean by greedy approach ? Is there any kind of already made algorithm that could help me ?
|
|
|
|
|
Greedy is when a series of optimal local choices will always lead to a global optimum
Which is not the case here. It would have been for some sizes of small rectangles.
But basically, this sucks. Does it absolutely have to be actually optimal?
Also, are the coordinates not-too-big integers?
If they are, what you could try (but I don't guarantee it's the best way) is a limited form of Branch&Bound combined with a heuristic to determine which choice to test first (to test "probable" cases first) and bound the subtree when you can determine that due to earlier choices it would be completely impossible to find a solution in that subtree (such as when the biggest open space is not big enough to place the biggest unplaced small-rectangle in it)
It will still suck for any but tiny instances of the problem. There would be an enormous number of choices at each node - the total number of possible placements of all rectangles that were not yet placed. The heuristic might be something like "try the biggest rectangle first" combined with a sane way to place it (eg near the edge).
I don't even see a way to do real B&B on this..
It's stupid though, there are many overlapping subproblems (you could use memoization but you'd get a Huge lookup table - maybe try something like "memoization only for the first k levels of recursion") and this algorithm would likely take longer than the estimated age of the universe to run on any interesting instance of the problem.
If a non-optimal (but "good") result is also OK, you could use basically the same algorithm but with far less choices (eg use an heuristic to do only the k "probably best" choices at each node) - you can still expect major suckage.
I hope this helped anyway.. though I don't think that's likely.. sorry
Note: I apologize for all errors and falsities in this post, there can't be none but I don't know what they are yet.
|
|
|
|
|
Yeah, you're helping and thanks for that 
Anyway, I don't think that coordinates will be bigger than 32000 (maybe not bigger than 10 000). I've thought of similar approach with recursion and memoization, but I'm not sure how to do it (I think I'll run into memory problems).
And yeah, non-optimal but "good" result should be OK. I'm not familiar with Branch&Bound, but I'll research it and try to learn something 
And one more thought ... Should I try placing every rectangle two times(normal and 90 degrees rotated) in the big rectangle and use memoization? Then I can determine how must small rectangles can there be for that algorithm to be executing in about 10 seconds ?
And I also have one more problem ... What's the best way to remember what parts of big rectangle I've already used ? I don't know how to do it ... Should I try with some custom class or ?? Please tell me if you have any ideas
And one more time, thanks for your big help !
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
