On Sun, Feb 24, 2008 at 12:56:40PM +0100, Stefan Schimanski wrote:
Random access is linear with sets. QCompleter needs this, and even
in the
case of sorted completions (where a binary search is possible) it
will
search the first element matching a prefix which is O(log n)*O(n)
operation
then.
Rather O(n) as set traversal is usually O(1) accumulated per element.
Depending on which operation is more often needed, either a sorted
vector or a set, or even a combination of 'set plus recently added
stuff
in an unordered vector' might be more efficient.
This is just to find the first element in the popup. Then following
lookups can be accelerated by caching the iterator. But still, O(n)
would
be already quite a lot IMO.
But get real numbers, I will implement this version now. Let's see...
Instead of a single cached iterator I now use a iterator position
cache. Everytime some element if (random-) accessed I store its value
in a position cache. This reduces the amount of lookup to exactly
10000 for 10000 words on the first access. Every following access is
constant time. I guess this is more or less optimal for this kind of
simple minded approach.
Stefan
