Ethereal-dev: Re: [Ethereal-dev] Performance. Ethereal is slow whenusinglargecaptures.
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.
