Hi Nathan, I don't consider this implemenetation as something different. Really, there is well know tree-optimization as clustering. Clustering can be done for each kind of binary tree, and clustering saves all properties of underlined tree. If we make clustering on AVL-tree or on RB-tree all complexity properties will be saved. Moreover, how will you check that this Tree is contradict with requirement to be RB-tree. Looking into source is a slippery way. Having some test for it? I am absolutetly sure that this tree will pass such kind of test.
On 3/19/08, Nathan Beyer <[EMAIL PROTECTED]> wrote: > > On Tue, Mar 18, 2008 at 7:35 PM, Alexei Fedotov > <[EMAIL PROTECTED]> wrote: > > Jimmy, Nathan, all, > > Do you know real applications which suffer from Sergey's > > implementation? Are there any broken use cases or failed tests? > > > > I don't think that's relevant to my argument, so I'm willing to make > the assumption that the code is functional and fine. In the case of > TreeMap and other implementation classes (HashMap, etc), I don't think > that being functional according to the interfaces that are > implemented is enough. In other words; it's not TreeMap because it > correctly implements SortedMap, NavigableMap, Map, Cloneable and > Serizable, it's TreeMap because it implements all of those and does it > with a red-black tree. > > I think the real question is can TreeMap still say it's implemented > using a red-black tree and all of the other comments mentioned in the > javadoc? > > -Nathan > > > Thanks. > > > > > > > > On Wed, Mar 19, 2008 at 3:17 AM, Nathan Beyer <[EMAIL PROTECTED]> wrote: > > > On Tue, Mar 18, 2008 at 4:18 AM, Sergey Kuksenko > > > <[EMAIL PROTECTED]> wrote: > > > > Hi Jimmy, > > > > > > > > I am really sorry for my long silence. > > > > > > > > > > > > > Does this cause a little confliction with spec, which annouced > the TreeMap > > > > is Red-Black tree based? > > > > How it can be checked? There are no way to check if three is RB > tree > > > > outside. > > > > What we have it is TreeMap interface which completely satisfied > to > > > > specification. > > > > RB-tree of not RB-tree can't be checked with public interface. > > > > > > True, but in this case, TreeMap isn't conceptually an interface, > it's > > > an implementation and users are going to expect performance and > > > behavior that's consistent with the javadoc [1] and RI. If that's in > > > question in anyway, then we should avoid it. Optimizations on > > > implementation classes that declare their algorithms shouldn't > change > > > the underlying algorithms; they should stick to things like reducing > > > memory overhead, reducing class complexity, reducing stack depth and > > > the like. > > > > > > In my opinion, a Map implementation that doesn't use an RB tree > isn't > > > java.util.TreeMap and is the realm of projects like > > > commons-collections. > > > > > > -Nathan > > > > > > [1] http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html > > > > > > > > > > > > > > > > > > > > > > This algorithm works very well on small number of pairs (as we > see, 4%-10% > > > > improvement ), but will it pause huge regression if the number of > pairs > > > > grows to a great number? > > > > > > > > I've based my implementation on the following steps: > > > > 1. small array is always faster then tree on all operations. > > > > 2. If we create Tree of small arrays we will get benifits on tree > sizes. > > > > > > > > And the latest fact is proved by my measurements. > > > > I am really want to collect all my data and share it here. But, > please, > > > > expect some delay in this. > > > > > > > > > > > > > > > > > I have a simple idea here, is it possible to just to apply only > binary > > > > search array when total size of the tree is small (e.g, small > than 64) and > > > > change it to RB-tree aglorithm(rebuild a RB-Tree) when the size > exceed the > > > > bar? > > > > > > > > If you check history of TreeMap you can find that this first > (initial) idea > > > > was implemented (probably somewhere in August/September 2007 I > don't > > > > remember exactly when). > > > > After that I was woking on expanding thiso idea to all tree > sizes. > > > > > > > > -- > > > > Best regards, > > > > --- > > > > Sergey Kuksenko. > > > > > > > > > > > > > > > -- > > With best regards, > > Alexei > > > -- Best regards, --- Sergey Kuksenko. Intel Enterprise Solutions Software Division.
