On Sunday 16 Nov 2003 3:06 am, Ronnie Sahlberg wrote: > Hmm. reflecting over my idea. > Thats suboptimal and possibly harmful for performance. > > New attempt. > Searching a binary tree is constant time Ordo(log2(n)). > Searching sequentially is worst case Ordo(n), average case would be > Ordo(n/2) and best case would be Ordo(1) > (for teh case when the item we search for happens to be the first one in > the list). > > By blindly using a tree here we could actually degrade performance. > > > One way to do it properly would be : > Document that the 8 first entries in a value_string as the fast entries. > Make sure that when using value_strings the most common ones are > stored in the first 8 items. The first value is the fastest one of them > all.
I don't agree with your reasoning. A tree search can be Ordo(1) if the node at the root holds the value you are looking for. Ordo(n/2) is a lot bigger than Ordo(log2(n)). Doing a linear search of 8 items is equivilant to searching a tree of 256 items. The disadvantage of a balanced tree is that the root node is a median value, not something you have chosen. You could have a "last search result" saved somewhere, that should save time with a very frequent target such as "no error" (giving you Ordo(1+log2(n)) for the rest.) But providing 8 would (IMHO) degrade performance. It should be possible to modify the AVR balancing algorithm to mark certain nodes as fixed. So you could build your tree using data with the most frequent items first and lock those nodes before adding the rest of the data. That way you get Ordo(log2(nfreq)) for frequent searches and a slightly degraded Ordo(log2(nfreq)+log2(n-nfreq)) or better for the rest. I'd go with the first option until it proved too slow. I'd also consider doing a binary chop of the value_string array rather than actually building a tree. -- Richard Urwin Officially, the only industrial accident I have had was due to working out the AVR algorithm. Elastic bands and map pins don't mix.
