|
Build a linked list (or tree, but for 1001 elements it would be overkill), visit the array one time for each element (or at least until you find the matching elements), build an entry containing the index of the value and the value at that index, link it in the linked list at the tail of the list (because you need to traverse the entire existing list checking for a match) and stop when you find a match. You then have the index of both values (one in the list and the last entry built) and the value, and have only accessed the list one time for each element.
|
|
|
|
|
Hi.
suppose I have center cordinates of 2 circles and their radiuses.
Now how can I calculate the overlapped area of these 2 circles? (suppose certainly have overlap)
Best wishes
|
|
|
|
|
One way:
if one circle has radius 'r' and the other 'R' and the distance between the centres is 'D' then:
- draw the radii from the centres C,D to the points of intersection 'A' and 'B'
- use Heron's Formula[^] to compute the area of the triangle with sides r,R,D - this is the area of triangle CAD and of CBD
- use the cosine rule to compute the size of angles ACB and ADB
- use these angles to work out the areas of the segments ACB and ADB
- the overlap area is the sum of the two segment areas minus twice the triangle area you calculated
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 need to take an existing populations of items (say for example, light bulbs, each bulb having a different number of existing hours already on it) and randomly assign an "expected life" to each item. This assumes I already have a valid PDF (Probability Density Function) from which to assign expected lives for NEW items. The problem is that the items in my population are not new. If I randomly generate a life from the PDF expecting to assign that life to an existing item, and that life happens to be less than the current ACTUAL life of the item, I'm hosed! I can't just ignore that life because then I'm skewing the PDF used to assign the lives.
I'm sure this is probably a no-brainer to a skilled statistician, but I don't recall anything like this in school, and haven't been able to find anything in books or in the limited Google'ing I've done.
Following is an algorithm I came up with while pondering the problem. Any thoughts?
-----------------------------------------
Here is a procedure for assigning "expected lives" to an existing population,
given the PDF parameters for lives of "new" parts.
Here's the scenario. We have a (assumed or tested) PDF for how long NEW parts
last. We have an existing population of parts that have accrued a given number
of hours. We want to use the PDF parameters to randomly assign expected lives
to all the items in the existing population.
Given the existing population's age, we should be able to "overlay" this with
the "known" PDF and determine how many of the initial population have already
failed. Here's an example:
Suppose we have a light bulb that has made it to the 99'th percentile of life.
Since only 1% of bulbs make it to this point, and we've got that bulb in our
hands, clearly 99 other bulbs have already failed, or, there must have been
an initial population of 100 light bulbs. Thus, by having one light bulb at
the 99'th percentile, we can infer that our initial population must have been
100. Now suppose that we have two bulbs, both at the 99'th percentile of
life. Obviously our initial population was 200 bulbs. 200 * (1-0.99) = 2.
Or, 200 = 2/(1.0 - 0.99)
Or, 200 = 1/(1.0 - 0.99) + 1/(1.0 - 0.99)
Basically, each non-failed part infers its own initial population of parts
that must have existed in order to produce this single non-failed part.
Tn = Total of all initial populations =
sum over all parts 'i'( 1/(1 - probability of past failure(age of part 'i')))
Based on the population PDF parameters, we now generate Tn random "lives" and
put them into a blind pot.
Beginning with the oldest item in the existing population (this assures we
don't end up with an item older than any values in the pot, and are thus
"stuck"), we randomly grab an age 'PA' from the pot. If the item's current
age exceeds PA, we put PA back into the pot, and try randomly picking another
age from the pot. Otherwise, we remove PA from the pot and assign it to the
item's "expected life". Then we move on to the next item. When we are done,
the lives left in the pot are the lives of the items that have failed before
this point in time. They get ignored.
David
---------
Empirical studies indicate that 20% of the people drink 80% of the beer. With C++ developers, the rule is that 80% of the developers understand at most 20% of the language. It is not the same 20% for different people, so don't count on them to understand each other's code.
http://yosefk.com/c++fqa/picture.html#fqa-6.6
---------
|
|
|
|
|
"I need to take an existing populations of items (say for example, light bulbs, each bulb having a different number of existing hours already on it) and randomly assign an "expected life" to each item."
For an existing item that has lived n time units, its remaining life is described by a SUBSET of the original PDF. I.e., by living n time units, it's eliminated all the cases from the original PDF that are shorter than n time units.
So, to get an expected life, you take the average of this subset of the original PDF. I.e. you average all the lifespans of the PDF that are at least n time units. (This is a calculated expectation -- not a randomly-assigned expected life.)
|
|
|
|
|
Thanks!
I still need to put a random spin on it though, since I'm doing a Monte Carlo simulation. That is, using the "calculated expectation" life from the algorithm you describe above would in-fact give the "expected" life (just like using the mean life is the best expectation for the life of a light-bulb), but it doesn't capture the "spread"ness of what is actually going to happen. If I was dealing exclusively with new parts, I still wouldn't merely assign the mean life to the anticipated part-life. I would use the PDF and randomly assign the lives (remember, this is a Monte Carlo simulation). It's clear enough how to do it for NEW parts, I'm just not clear on how to do it for USED parts; although I THINK my algorithm may capture it.
By the way; would your answer be covered in an "Elements of Statistics" book? I have a "Statistics for Engineering and the Sciences" book, and either it's not in there, or I just don't know what I'm looking for and am simply overlooking it.
Thanks again for the help.
David
David
---------
Empirical studies indicate that 20% of the people drink 80% of the beer. With C++ developers, the rule is that 80% of the developers understand at most 20% of the language. It is not the same 20% for different people, so don't count on them to understand each other's code.
http://yosefk.com/c++fqa/picture.html#fqa-6.6
---------
|
|
|
|
|
For a used part you just do the same thing with a subset of the PDF. (Just like you use the whole PDF for a new part.)
So, for example, if you have bell-shaped PDF with mean n, and your item has existed for n time units, you would make a random selection from the upper half of the bell-shaped curve.
Although this has elements of both probability and statistics, I would consider this slightly more probability than statistics.
|
|
|
|
|
Right!
Now I just have to figure how to do that.
David
---------
Empirical studies indicate that 20% of the people drink 80% of the beer. With C++ developers, the rule is that 80% of the developers understand at most 20% of the language. It is not the same 20% for different people, so don't count on them to understand each other's code.
http://yosefk.com/c++fqa/picture.html#fqa-6.6
---------
|
|
|
|
|
Do you know the algorithm for using the rand() function (which generates a uniform PDF) to generate values within a specified PDF? I've thought thru it before, but didn't write it down.
Also, without having a parameterized function for the PDF (I doubt it's even possible to come up with a formula for a left-truncated PDF like we're talking about -- plus, it would change for each item) this seems hard.
UNLESS! I don't model the PDF with a parameterized function, and instead model it via a table of values obtained from the original PDF formula. That should be easy enough to normalize by just numerically integrating the remainder of the curve.
Well, maybe this won't be so hard. (Famous last words...)
David
---------
Empirical studies indicate that 20% of the people drink 80% of the beer. With C++ developers, the rule is that 80% of the developers understand at most 20% of the language. It is not the same 20% for different people, so don't count on them to understand each other's code.
http://yosefk.com/c++fqa/picture.html#fqa-6.6
---------
|
|
|
|
|
DQNOK wrote: Do you know the algorithm for using the rand() function (which generates a uniform PDF) to generate values within a specified PDF?
I answered my own question.
For a PDF called 'y(x)' (where x is the random varaible), and a computer library function rand() that returns a random value in the range [0, 1) from a uniform PDF, we seek to map rand's return value (call it rx) to the correct x.
Effectively, we are looking for x such that the area under the curve y(x) LEFT OF x is equal to the area under the uniform PDF left of rx. But since rand produces values within the unit interval [0,1), rx IS the area under the curve left of rx. So, we seek x such that:
rx = integral from -infinity to x of y(x)
Exactly HOW we evaluate the integral (i.e. solve for x) is an implementation detail that depends on how y(x) is defined. If the integral is already given via a formula, we just use a standard non-linear scalar solver, like a Newton-Raphson. It not, then perhaps I would just use a stepping approach, something like:
ndx = getBestStartingIndex(rx);
x = X_STARTS[ndx];
area = AREAS[ndx];
old_y = y(x);
while( area < rx )
{
x += dx;
new_y = y(x);
area += dx * (old_y + new_y)/2 ;
old_y = new_y;
}
return x;
Which can be polished for better precision, time-performance etc.
David
---------
Empirical studies indicate that 20% of the people drink 80% of the beer. With C++ developers, the rule is that 80% of the developers understand at most 20% of the language. It is not the same 20% for different people, so don't count on them to understand each other's code.
http://yosefk.com/c++fqa/picture.html#fqa-6.6
---------
modified on Thursday, April 17, 2008 9:28 AM
|
|
|
|
|
OK, you've got me thinking...
The PDF appropriate for a given used part is the subset of the original PDF that is (thinking graphically) "to the right" of that part's age. BUT, this part of the graph doesn't have unit area (the area under this part of the curve is no longer unity). But even that doesn't seem such a large handicap; just normalize it by the area that IS there.
If I could somehow mathematically model this "left-truncated" PDF, I could -- as you alluded to in your response, use it to assign a random life. As you pointed out, taking the mean of the remainder of the original PDF gives the best EXPECTED life; I just need to figure out how to use that remainder to assign a random life.
Hmmmmm... Maybe it's not so hard. I'll have to think about it a while.
David
---------
Empirical studies indicate that 20% of the people drink 80% of the beer. With C++ developers, the rule is that 80% of the developers understand at most 20% of the language. It is not the same 20% for different people, so don't count on them to understand each other's code.
http://yosefk.com/c++fqa/picture.html#fqa-6.6
---------
|
|
|
|
|
I have a problem about hamilton algorithm .I don,t know how do I write it ? Please send me a document which discuss about it .Thanks
|
|
|
|
|
You're going to have to be more specific...
What has the future in store for this strange being, born of a breath, of perishable tissue, yet Immortal, with his powers fearful and Divine?
What magic will be wrought by him in the end?
What is to be his greatest deed, his crowning achievement?
|
|
|
|
|
What is Hamilton algorithm?
(just curious).
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
I'm assuming he means one of these.[^]
What has the future in store for this strange being, born of a breath, of perishable tissue, yet Immortal, with his powers fearful and Divine?
What magic will be wrought by him in the end?
What is to be his greatest deed, his crowning achievement?
|
|
|
|
|
Thanks .Hamilton algorithm : what do I want to say that the method to
find cycle hamilton .This is a algorithm in graph theory subject .
- algorithm which find cycle hamilton
|
|
|
|
|
Source code is available from this page[^].
Paul Marfleet
"No, his mind is not for rent
To any God or government"
Tom Sawyer - Rush
|
|
|
|
|
I think he's referring to this[^]. The physics references refer to Hamiltonian mechanics which is a way of constructing a set of differential equations to describe a physical system.
And when the sunlight hits the olive oil, don't hesitate.
|
|
|
|
|
I see.
Vaguely.
Drawing on my fine command of language, I said nothing.
|
|
|
|
|
I know - the distinction isn't clear. If you think of the Hamiltonian in physics (loosely) as the path/configuration of minimum energy, then you can see why Hamilton's algorithm for vertex paths is related.
Yes/no? It has to do with each vertex (in the case of the Hamiltonian algorithm for graph theory) being touched only once...
And when the sunlight hits the olive oil, don't hesitate.
|
|
|
|
|
I get what you're saying, but I was trying to read up on Hamiltonian mechanics, and it was WAY complicated. I was getting it, and then it completely lost me. I'm too dumb, sorry.
Drawing on my fine command of language, I said nothing.
|
|
|
|
|
Ravel H. Joyce wrote: I get what you're saying, but I was trying to read up on Hamiltonian mechanics, and it was WAY complicated. I was getting it, and then it completely lost me. I'm too dumb, sorry.
No, you're not dumb. Your mind is still pure and clean. Your innocence hasn't been taken from you; you haven't been touched by the horrors of Jackson[^] yet.
Also, to understand Hamiltonian mechanics, you have to understand the mathematical language it's formalized in. You are too young to have been exposed to calculus yet let alone generalized position and momentum equations or the principle of minimum variation. Let's just say that Hamiltonian mechanics is a grand generalization of classical mechanics (physics). In it's most easily understood terms, the Hamiltonian of a system represents the minimum energy configuration. It allows you, for example, to derive a set of equations of, say, a particle in a field - a set of equations that will describe the evolution of i.e. position and momentum over time.
And when the sunlight hits the olive oil, don't hesitate.
|
|
|
|
|
73Zeppelin wrote: Your mind is still pure and clean.
...oh...
That was serious...
But I have a basic understanding of calculus. I have a very patchy knowledge of mathematics, actually, now that I think about it. I know that eip + 1 = 0  ! ...except that I don't really know how it's derived or anything. Well, I very vaguely do, a very superficial knowledge. I know what a complex number is, despite my probable lack of being able to do much with it. I know that 5 is bigger than 4. I guess that's what you get from reading random Wikipedia articles and being stopped from being accelerated!
So wait, the Hamiltonian of a system represents the minimum energy configuration...so, a particle moving in a straight line (well, no acceleration) is the lowest energy configuration?
I dunno where I'm going with this. Hopefully to a little more understanding, but that's not overly likely. 
Drawing on my fine command of language, I said nothing.
|
|
|
|
|
Ravel H. Joyce wrote: So wait, the Hamiltonian of a system represents the minimum energy configuration...so, a particle moving in a straight line (well, no acceleration) is the lowest energy configuration?
I dunno where I'm going with this. Hopefully to a little more understanding, but that's not overly likely.
Well, that depends: a particle moving in a straight line being acted upon by what forces?
A hydrogen atom (in the ground state) can be described by a quantum mechanical Hamiltonian that gives the equations for the description of the hydrogen atom (ground state). In fact, the Hamiltonian in quantum mechanics leads to the Schrödinger equation - one of the fundamental equations of quantum theory. And since we are talking about the ground state of an atom, we are really considering its lowest energy configuration.
Ravel H. Joyce wrote: a particle moving in a straight line (well, no acceleration) is the lowest energy configuration
No! A particle at rest is! A particle moving in a straight line with no acceleration still has kinetic energy!
And when the sunlight hits the olive oil, don't hesitate.
|
|
|
|
|
73Zeppelin wrote: Well, that depends: a particle moving in a straight line being acted upon by what forces?
No acceleration = no forces?
73Zeppelin wrote: No! A particle at rest is! A particle moving in a straight line with no acceleration still has kinetic energy!
Moving in a straight line relative to what? At rest relative to what?
I didn't think that there was a difference...
[Edit #1] Wait...I'm confused about kinetic energy. So...accelerating something gives it kinetic energy? What is kinetic energy? Is it an increase in mass because of an increase of energy? (E=mc2)? Or am I just completely missing the point?
Maybe I'm just making this unnecessarily complicated...
[Edit #3] I don't think I really get the concept of 'at rest'.
Just a thought - would the act of dropping a nuclear bomb (and having it accelerate towards the ground) increase the energy of the explosion a tiny bit? Rather than having it sit motionless? Ignoring, of course, the ground absorbing heaps of the energy of the explosion.
73Zeppelin wrote:
A hydrogen atom (in the ground state) can be described by a quantum mechanical Hamiltonian that gives the equations for the description of the hydrogen atom (ground state). In fact, the Hamiltonian in quantum mechanics leads to the Schrödinger equation - one of the fundamental equations of quantum theory. And since we are talking about the ground state of an atom, we are really considering its lowest energy configuration.
Ground state.
Lowest energy configuration.
What does that entail? Absolute zero? 
[Edit #2] Question: if you accelerate an atom to a high enough speed can it cause an electron to jump to a higher orbital?
Ground state incorporates both being at rest and having minimum level energy electrons, doesn't it?
[Edit #4] No, AHHH!!! I don't get it.  My thoughts are racing too fast. I'm gonna go, I dunno, eat a cookie or something... 
[Edit #5] Kinetic energy is a relative measure, isn't it? Ek = 1/2*m*v2, and velocity is relative, so kinetic energy is too?
Drawing on my fine command of language, I said nothing.
modified on Wednesday, April 23, 2008 2:19 AM
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
