|
I have a Red Black Tree in which is stored some 'sparse' keys. I might have e.g. {1, 11, 22, 31, 47, 63, 71} etc. The pattern is not important just the sparseness of keys.
What I would like to do is look up the 'closest without going over' key from my BST, which is in-fact the index into a very large array (>10M elements).
So for example if I'm looking for entry 55 using the above index, I would like to return the data stored at the node for 47, which is the best guess index for me to start searching my array for entry 55.
It sounds simple enough but I can't find code or even an algorithm outline anywhere. The closest thing I've seen involves searching for a range of values, but if I knew the range I'd need, I wouldn't need this index in the first place... more behind the scenes, know what I mean?
Couple of things:
* I don't know the indexes or the gaps between keys beforehand.
* This index is rebuilt very often (after array cut-paste operations).
In other words any 'workaround' solutions that don't directly answer my question need to be general enough and fast enough to deal with the problem. The index actually loses information as the array shrinks but the original indexes must be kept.
Hope I've made the problem simple and clear enough. Any help will be very much appreciated!
|
|
|
|
|
To find the closest without going over, look for the key until you get down to a leaf node.
If the leaf contains your key you're done. If the leaf is less than your key, you're done in this case too. If the leaf is over your key, go to the next lowest node. (There's a simple algorithm for doing this in a binary tree, that you can find in an algorithms book. I don't recall it off the top of my head.)
BTW, I used to use red-black trees too to keep them balanced. Then I found out about Scapegoat Trees (http://en.wikipedia.org/wiki/Scapegoat_tree[^]) which stay balanced WITHOUT the overhead of a red/black bit in each node.
|
|
|
|
|
Have you considered using a b+ tree instead of a red black tree for the base indexing. Whenever you find a leaf key that is too big, the next smaller key is immediately before it, or else is the last key of the preceding block, both of which are easily, quickly accessed without traversing tree nodes. I specifically refer to the B++ tree implementation of CBTREE from Mix Software in its C Database Toolchest.
Dave.
|
|
|
|
|
Molecular Mechanics?
in C# just use a Dictionary with key/location as your lookup method.. simple...
It would be something like see this see also
new Dictionary< int Value,int Location>
then when you move something you can (i don't remember specifics) eitheer change the dictionary value or add/remove.. etc..
|
|
|
|
|
Thanks for all the suggestions. I'll look at these over the weekend and decide which ones I can implement easily and which of those performs as required.
Have a great weekend and thanks again.
|
|
|
|
|
On Pixar's How We Do It[^] page (slide 13), they talk about what goes into each frame of a movie. Maybe I'm just being dense, but...
Let's assume the average movie is 90 minutes, or 5,400 seconds, long.
Each frame is 1/24 of a second, so there are 129,600 frames.
If each frame takes about 6 hours to render, that would be 777,600 hours.
They undoubtedly have some serious horsepower doing this rendering, so is that 777,600 computer hours?
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
I am sure that are CPU time measurements.
Calculate it into years, then you will see.
However they must have amazing Pcs.
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)
|
|
|
|
|
Fatbuddha 1 wrote: Calculate it into years, then you will see.
I did, hence the confusion.
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
I suspect a large degree of parallelism in use.
|
|
|
|
|
A very very very big cluster .
And then several of them .
Have a nice weekend
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)
|
|
|
|
|
Or it could be "actual time"; they didn't say much about the granularity of their parallelism, maybe they render multiple frames in parallel, instead of multiple pixels?
I didn't read the whole "How We Do It" though
|
|
|
|
|
My guess is that you would find they are rendering in layers and then integrating the layers. This would allow them to render smaller areas of a frame in less time.
For example, you can render a background once and then render foreground characters that are smaller sections of a frame and thus render in less time, and then integrate them together.
I don't think you could do it all this way simply because of how the various parts of a frame may interact, but I think this could get you a better (smaller) time.
|
|
|
|
|
That's only 89 CPU years. Even with 180 computers, that's 6 months of rendering and they have much larger rendering farms.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
They Have "LARGE" render farms... LARGE.
they can "cut corners" in some aspects of the Render procedurally.
they can layer and post process.. usually this is what they do however this causes the large "finish rendering" time because someone goes in and digitally touches up the shadow, or adjusts the intensity of the red in the fire in the background etc...
all the photo-realistic portraits that i've seen can usually be rendered in under a couple of hours(very detailed) but being the perfectionists that they are the artists like to go back in and tweek the resulting image, make the gem more sparkely, the drool wetter.. etc.
|
|
|
|
|
Yeah, that sounds right - even if a little on the 'light' side by today's standards.
Apparently, Pixar used about 1000 Sun UltraSPARC servers to do the original ToyStory. When they did the movie CARS, they used about 300 times the processing power.
Tom Duff tells us that they're looking at around 1.2 million cpu hours for a 1.5 hour movie.....
Here's where you can find some more facts and figures: real-time-toy-story-3d[^]
|
|
|
|
|
Thanks for that link.
"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
|
|
|
|
|
Anyone know about travel or comparison algorithm for n-ary tree.please help me..
|
|
|
|
|
If by 'travel' you mean traversal you might find this[^] useful.
Henry Minute
Do not read medical books! You could die of a misprint. - Mark Twain
Girl: (staring) "Why do you need an icy cucumber?"
“I want to report a fraud. The government is lying to us all.”
|
|
|
|
|
public void convertDoubleToDecimal(double value)
{
long num = Double.doubleToLongBits(value);
byte sign = (byte)((num & 0x8000000000000000L) >> 63);
long exp = (num & 0x7ff0000000000000L) >> 52;
int e = (int)exp - 1023;
long fraction = num & 0x000fffffffffffffL;
long valueBin = fraction | (1L << 52);
int[] valueBinArray = new int[53];
for (int i = 0; i < valueBinArray.length; i++)
valueBinArray[i] = (int)((valueBin & (long)Math.pow(2, i)) >> i);
long intPart = 0;
double fractionPart = 0;
if (e <= 0)
{
for (int i = e; i >= 0; i--)
intPart += valueBinArray[52 - (e - i)] * (int)Math.pow(2, i);
for (int i = -1; i >= -(52-e); i--)
fractionPart += valueBinArray[52 - (e - i)] * Math.pow(2, i);
}
else
{
for (int i = 0; i > -53; i--)
fractionPart += valueBinArray[i + 52] * Math.pow(2, i + e);
}
int decimalPlaces = 4;
long number = (long)(intPart * Math.pow(10, decimalPlaces));
number += (long)(fractionPart * Math.pow(10, decimalPlaces));
byte[] buffer = new byte[16];
buffer[0] = (byte)(number & 0x00000000000000ffL);
buffer[1] = (byte)((number & 0x000000000000ff00L) >> 8);
buffer[2] = (byte)((number & 0x0000000000ff0000L) >> 16);
buffer[3] = (byte)((number & 0x00000000ff000000L) >> 24);
buffer[4] = (byte)((number & 0x000000ff00000000L) >> 32);
buffer[5] = (byte)((number & 0x0000ff0000000000L) >> 40);
buffer[6] = (byte)((number & 0x00ff000000000000L) >> 48);
buffer[7] = (byte)((number & 0xff00000000000000L) >> 56);
buffer[8] = (byte)0;
buffer[9] = (byte)0;
buffer[10] = (byte)0;
buffer[11] = (byte)0;
buffer[12] = (byte)0;
buffer[13] = (byte)0;
buffer[14] = (byte)decimalPlaces;
buffer[15] = sign;
}
modified on Monday, October 12, 2009 2:29 PM
|
|
|
|
|
Is there a question associated with this post?
BTW please put your code within a code block (<pre></pre> tags) to improve readability.
|
|
|
|
|
There is no question. I just didn't know where to put my code.
modified on Monday, October 12, 2009 2:52 PM
|
|
|
|
|
If you want to share code or a technique, you write an article. These forums are for questions and discussion.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
I Want Detect A Circle In A Image(this image is a form that contain marks (optical mark recognition or OMR )) Using c#
is exists any source code for it.
thanks if help me
best regards
mohammad reza
|
|
|
|
|
I suspect it's readily available as a commercial library or application if you search for it.
You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.
|
|
|
|
|
Hi,
this[^] seems to explain it pretty well.
Luc Pattyn
I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages
Local announcement (Antwerp region): Lange Wapper? Neen!
|
|
|
|