Automatically Generated Keyboard Accelerators (replacing kaccelgen.h)

[Ingo Klöcker]

On Monday 09 June 2008, Mark Summerfield wrote:
> Hi,
>
> At present KDE uses kaccelgen.h to automatically generate keyboard
> accelerators.
>
> The algorithm used is very easy to understand, but produces poor
> results---for example, in many real use cases it can only generate
> accelerators for half or fewer of the strings it is given.
>
> I have created a completely different algorithm that is more
> sophisticated (but still perfectly understandable) and that can
> produce optimal results every time. One theoretical drawback is that
> my algorithm can take a lot longer to run than the current
> one---O(n!) vs. O(n). But by tuning my algorithm for speed it still
> equals or betters the existing algorithm in all the cases I've tested
> and has a runtime performance of single or double figure
> milliseconds---so it is fast enough to generate menu accelerators
> dynamically.

I don't want to spoil the fun, but this problem is usually known as 
assignment problem [1] and it is solvable in O(n^3) by the Hungarian 
algorithm (aka Munkres assignment algorithm aka Kuhn-Munkres algorithm) 
[2]. Moreover, there exists a C++ implementation of this algorithm [3] 
(which I didn't even have a quick look at). The only "problem" is that 
this implementation is GPLv2+ so it cannot be used in kdelibs.

This is JFYI. Until there is a better implementation than the one 
proposed by Mark we should probably use Mark's implementation.

Last but not least, an advise to all (KDE) developers (Please don't get 
this wrong, Mark!):
Before you try to invent an algorithm to solve some problem please 
invest some time to check whether there is already an algorithm solving 
this exact problem. More often than not this will save you a lot of 
time.


Regards,
Ingo

[1] http://en.wikipedia.org/wiki/Assignment_problem
[2] http://en.wikipedia.org/wiki/Hungarian_algorithm
[3] http://johnweaver.zxdevelopment.com/2007/05/22/munkres-code-v2/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 194 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080610/7482e0db/attachment.sig>