From kde-core-devel Thu Aug 30 11:55:12 2001 From: Waldo Bastian Date: Thu, 30 Aug 2001 11:55:12 +0000 To: kde-core-devel Subject: Re: KConfig sucks :-) X-MARC-Message: https://marc.info/?l=kde-core-devel&m=99917263019600 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.