[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-core-devel
Subject:    Re: KConfig sucks :-)
From:       Waldo Bastian <bastian () kde ! org>
Date:       2001-08-30 11:55:12
[Download RAW message or body]

On Wednesday 29 August 2001 11:27 pm, Michael Matz wrote:
> Hi,
>
> On Wed, 29 Aug 2001, Waldo Bastian wrote:
> > While I was debugging the mysterious non-working localisation I noticed
> > that we use a QMap to store all entries (no surprise there) but since we
> > write out the entries in order, most of the time we read the entries back
> > in order as well, which means that effectively our QMap becomes a linked
> > list and we get O(N) behaviour instead of O(log N).
>
> Although I'm not exactly sure, what operation should be O(N):
> What makes you think, that filling a QMap in a sorted manner makes
> operations on that QMap be O(N) (compared to filling it randomly).

Yeah, I'm smoking crack... I saw insert operations taking about 60 
comparisons so I figured that can't be O(log N) but on closer inspection I 
noticed that it was effectively doing 4 lookups, so each lookup took about 15 
comparisons instead of 60. I probably also underestimated the actual number 
of entries that were in the map, I would have guessed about 70, but a 
linecount on my kdeglobals file shows more than 300 lines already. 
(2^15 is still a lot more than 300 though)

Running kconfigtest I got a total of about 35000 comparisons most of them due 
to reading share/config/kdeglobals and share/config/charsets.

Cheers,
Waldo
-- 
KDE 2.2: We deliver.

[prev in list] [next in list] [prev in thread] [next in thread]