|
first of all, it's a collection class, not a DBMS. Yes, B-trees can be used for DBMS systems but if I was going to go through all the trouble of optimizing my algorithm doing batch inserts and what have you, then I'd be doing it on a B Plus tree instead
At least if my goal was to make a dbms.
My concern in my OP was not about the performance of my class(es)
It was about the performance of Microsoft's classes.
Namely, a SortedDictionary (red-black tree) beating out a B-tree after 10,000 entries.
But then i think i already explained that. Maybe i didn't. i don't remember and don't much care.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
Apparently I implemented a B+ tree for no reason because it gives you zero benefit unless you're accessing slow I/O like a disk, and it's tied to your nodes, which means implementing some kind of file driver and a file format for storing nodes at the very least.
So basically, a database.
I mean, it's cool code, but it's useless byself. On the shelf it goes.
*headdesk*
At least my regular B Tree works. That's kinda cool.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
Make it 2D, you got the fabled QuadTrees!
Although, most (in memory) implementation (including mine ) seems to be simple (2D) binary tree instead of being B+Tree
Could be useful for making graphics application (and doing in memory hit test), like the one I have in limbo for the last 2 years!
|
|
|
|
|
interesting. right now i don't know much about graphics as far as the maths go.
but i can do some basic trig and compute the distance between points, that kind of thing.
i've never much needed to do polygon hit testing though i do know that btrees or b+trees are used in them. I'm not sure how.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
Simple, when you do an hit test you don't want to hit test all the polygon in your application, since it's gonna be a computationally expensive operation.
So all your polygons are in a Quad Tree and with their bounding rectangle.
And the QuadTree has a very fast hit test implementation that would return the list of polygon worth checking in more details!
|
|
|
|
|
I get the gist at least.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
|
As for hit test, there some simple well know implementation that works well for polygon. (the winding number one being my favourite)
My grief is that I work with shape, i.e. unlike polygon which have straight lines between vertices for boundary, shape have Bezier curves, much harder
|
|
|
|
|
also i remember it being more complicated for polys that have concave bits to them.
I could be wrong. It has been years since i read the black book.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
winding method work for all polygons!
the only "downside" is that self intersecting polygon would have holes.. where they self intersect and odd number of times... Which is more or less what people have come to expect....
|
|
|
|
|
Make it 3D, you get OctTrees!
Make it 4D you get HoneyWitchTrees!
|
|
|
|
|
Now go implement an AVL Tree.
#SupportHeForShe
Government can give you nothing but what it takes from somebody else. A government big enough to give you everything you want is big enough to take everything you've got, including your freedom.-Ezra Taft Benson
You must accept 1 of 2 basic premises: Either we are alone in the universe or we are not alone. Either way, the implications are staggering!-Wernher von Braun
|
|
|
|
|
i just did
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
Now make a visual representation of that AVL tree that shows it rebalancing in realtime.
#SupportHeForShe
Government can give you nothing but what it takes from somebody else. A government big enough to give you everything you want is big enough to take everything you've got, including your freedom.-Ezra Taft Benson
You must accept 1 of 2 basic premises: Either we are alone in the universe or we are not alone. Either way, the implications are staggering!-Wernher von Braun
|
|
|
|
|
i might scrap my AVL tree as my B-tree implementation seems to outperform it, which kind of surprised me.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
It's probably the rebalancing code that makes it slower on insert. But should be faster on lookup.
#SupportHeForShe
Government can give you nothing but what it takes from somebody else. A government big enough to give you everything you want is big enough to take everything you've got, including your freedom.-Ezra Taft Benson
You must accept 1 of 2 basic premises: Either we are alone in the universe or we are not alone. Either way, the implications are staggering!-Wernher von Braun
|
|
|
|
|
Yep. I think it's a good rule of thumb that the more optimized your search algo is, the faster it's search is relative to its inserts (and especially removes!)
What surprised me some about my results is again after 30,000 rows or so if memory serves, the SortedBTreeDictionary was beating out SortedDictionary on inserts AND deletes, not just searches. I was impressed.
Having a much harder time getting my AVL tree working despite the algorithm being simpler. The problem is I was recomputing the heights all the time which made it atrociously slow and the code just didn't want to accept my optimizations. Problems kept coming up. I've finally got it inserting and deleting 10,000,000 rows without much complaint which means I can throw it back into my cheesy little test harness and beat it up. woo.
When I was growin' up, I was the smartest kid I knew. Maybe that was just because I didn't know that many kids. All I know is now I feel the opposite.
|
|
|
|
|
Good times! I look forward to hearing about your results!
#SupportHeForShe
Government can give you nothing but what it takes from somebody else. A government big enough to give you everything you want is big enough to take everything you've got, including your freedom.-Ezra Taft Benson
You must accept 1 of 2 basic premises: Either we are alone in the universe or we are not alone. Either way, the implications are staggering!-Wernher von Braun
|
|
|
|
|
I needed to download JDK 1.8 so I googled for it. Google takes me to Oracle download site. After clicking the download link I have to create an Oracle account which wants Company name and work phone and address, etc.
You suck Oracle!
Social Media - A platform that makes it easier for the crazies to find each other.
Everyone is born right handed. Only the strongest overcome it.
Fight for left-handed rights and hand equality.
|
|
|
|
|
That's what I use my spam magnet account for and that is the actual user name of it.
"They have a consciousness, they have a life, they have a soul! Damn you! Let the rabbits wear glasses! Save our brothers! Can I get an amen?"
|
|
|
|
|
I have one of those: "DontSendMeAnyCrap@..."
It's an auto-delete everything account.
Or there is Mailinator if they want a confirmation email.
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
|
That actually is where I downloaded it from. Once you check to accept the terms and then click the Hyperlink it then takes you to a login page where you have to login to the Oracle site.
Social Media - A platform that makes it easier for the crazies to find each other.
Everyone is born right handed. Only the strongest overcome it.
Fight for left-handed rights and hand equality.
|
|
|
|
|
How odd, they must have introduced that recently as I cannot recall having an account, and my updates all happen automatically. I will check more carefully next time I need a later version.
|
|
|
|
|
Could Zulu OpenJDK[^] be of any use?
Michael Martin
Australia
"I controlled my laughter and simple said "No,I am very busy,so I can't write any code for you". The moment they heard this all the smiling face turned into a sad looking face and one of them farted. So I had to leave the place as soon as possible."
- Mr.Prakash One Fine Saturday. 24/04/2004
|
|
|
|