Am 24.02.2008 um 13:18 schrieb Andre Poenitz:
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.
Right, O(n) of course with the iterator caching.
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.
A vector is unsorted because you cannot easily insert an element in
the middle. Hence you have to add it add the end. Then every operation
like filtering by completion prefix is linear.
I don't think any of those "tricks" will help very much :-/
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...
Indeed.
So the version with a set and caching of the iterator gives (for 10000
words)
* 80000 it++/-- calls if QCompleter assumes an unsorted model
* 120000 it++/-- calls if QCompleter assumes a sorted model
I am optimistic that one might optimise these numbers a bit by
reducing the number of accesses to the QCompleter. But even on my
quite fast machine this gives quarter of a second delay (with stdlib-
debug though).
Stefan
