Fwd: Re: Automatically Generated Keyboard Accelerators (replacing kaccelgen.h)

[Michael Pyne]

On Tuesday 10 June 2008, Mark Summerfield wrote:
> I certainly know that my algorithm outperforms the existing one in all
> the tests I've done (and uses an algorithm that is intrinsically
> better), so I'm inclined to hope you'll use the one I've done, at least
> for now?

Mark,

Most of the kdelibs guys understand what O(n) notation entails, including the 
fact that there are constants involved.

Please understand though, just how astronomically bad O(n!) can be for code 
which always executes.

O(120!)    -> C * 6.689 e +198
O(120 ^ 3) -> C * 1.728 e +006

That's 192 orders of magnitude slower.  It would never finish, and the 
application would never start up.

*Now*, you've tested this code yourself, so perhaps you either got the 
algorithmic complexity wrong (i.e. it's really not that bad) or what you 
mentioned about m typically being much less than n holds true.  But if we're 
going to be putting this into kdelibs we owe it to ourselves to figure out 
what the worst plausible case is, and what the effect would be.

I guess the question is, what is "n" in this discussion?  The number of 
actions?  If so you should probably either refine the algorithm or at the very 
least fallback to the O(n) version with a threshold value of n (say 50 or so, 
or whatever your testing shows to be possible).

Thanks for the patch, I haven't had time to test it yet but I'm looking 
forward to better default accelerators in KDE!

Regards,
 - Michael Pyne
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080610/378c9a79/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080610/378c9a79/attachment.sig>