The Lounge is rated Safe For Work. If you're about to post something inappropriate for a shared office environment, then don't post it. No ads, no abuse, and no programming questions. Trolling, (political, climate, religious or whatever) will result in your account being removed.
I've seen the reference implementations for dictionary and sorted dictionary. I've even fiddled with them in binary form way back when with Reflector. I expect the inserts and removal times to be longer - i'd be surprised if they weren't, but the searches? This is just wrong.
(The AVL tree implementation sucks - it will be improved)
Thank you for the polite tone of your response, Peter.
I am aware of Chris' comment on the prior post, and I do not interpret it as being a "blanket" invitation for posts, like this one, which are nothing but code. There is no "discussion" inherent in this post.
I take the privilege of being a "mentor" on CP seriously, and when I see content like this, which could contribute to the quality of CP in the long run ... if posted on the appropriate technical forum ... I will speak out.
«One day it will have to be officially admitted that what we have christened reality is an even greater illusion than the world of dreams.» Salvador Dali
The .NET BCL code has 2 advantage.
1. it runs in release mode (yours probably run in debug mode)
2. it has been precompiled ahead of time. (i.e. NGEN). NGEN does a better job sometimes.. though not sure it does that much better on library... (as opposed to program)
(bonus point) well you said you check the reference implementation so might not be true. but .NET BCL is heavily optimised (I used reflector sometimes and I was surprised by the length they occasionally go to to make common codepath faster)
Looks like a fun way to improve your coding!
Good luck with that and improvement!
Any chance I can give you some homework?
In AvalonEdit their text model use "Rope" which looks like an IList but has fast insert and delete, i.e. O(1) cost instead of O(n)
In fact their code is probably quite nice.. but after looking at it for only 2 minutes I was confused, it's all mixed up with the text model, if I remember right...
Maybe you could be interested in making standalone Rope class?!
although mine destroys Microsoft's for searching after about 30,000 items.
Exactly this is the reason for using B-trees in a database.
They're not very sensitive to size, which is something you regularly get in a database. While more than 30000 items is something you very seldom need to (or should) handle in memory.
While more than 30000 items is something you very seldom need to (or should) handle in memory.
That's getting less true. What's funny is by my tests, .NET is just fine with 3 million entries spread across 3 different dictionary classes.
The heap isn't as big as you'd expect and the performance is really good for both the base Dictionary class (which is basically unsorted, and uses a hash lookup) and for my class, while not being unsurprising for the other class.
Times are changing. In memory DB is totally doable even in C#, for smaller dbs.
I was thinking of backing JSON with something like this, or implementing a full B+ with backing storage for it.
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.