Automatically Generated Keyboard Accelerators (replacing kaccelgen.h)
Ingo KlĂ¶cker
kloecker at kde.org
Mon Jun 9 23:29:52 BST 2008
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>
More information about the kde-core-devel
mailing list