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

[Mark Summerfield]

Hi,

Attached is:

- complete file of kaccelgen.h.
  The only difference is that the quality() function now produces much
  better results than before.

I've also been thinking about the O(n^3) algorithm:

Although mine is O(n!), in practice it mostly only computes O(m!) where
usually m < n since it first looks at the best possible part of the
search space and if that doesn't deliver, gradually widens the search.
So mostly I search a smaller search space.

I also talked it over with my friend Ben Thompson who's much more
mathematically sophisticated than I am, and he reminded me that O(f(n))
is a pretty coarse measure and that you have to consider the practical
implementation details. In particular he pointed out that: "f(n) =
O(g(n)) iff there is a constant k and an n0 such that for all n >= n0,
f(n) <= k.g(n). It's the k that is important here."

So even if there is an O(n^3) algorithm, what that really means is that
it has a time complexity of:

T(n) < k.n^3

for some constant k and only when n > some n0. k may be huge and n0 may
be more than 26 or 36, so an algorithm with complexity S(n) = n! (note
that's equal to n! not O(n!)) will be better.

He also said:

"Or you can put it like this:

1. T1(n) = O(n!)
2. T2(n) = O(n^3)

means T2(n) = O(T1(n)) but that's all you can say.

In particular, they do not imply

T2(n) < T1(n)

for *any* n, let alone for all n.

So it is all in the constants and the "n0". NB Theoretical
transformations from one problem to another often involve increasing the
constants and what (little) I read in the references suggested there
were quite a few transformations from the general Kuhn-Munkres algorithm
to the specific example of a keyboard accelerator algorithm, so it is
likely the constants will be massive if you implement the transformation
naively. And even if you do it carefully and end up with an O(n^3)
algorithm, it may still end up being slower than an O(n!) algorithm for
n < 26 because of the constant overhead."

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 Summerfield, Qtrac Ltd., www.qtrac.eu

-------------- next part --------------
A non-text attachment was scrubbed...
Name: kaccelgen.h
Type: text/x-c++hdr
Size: 19178 bytes
Desc: not available
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080610/24af6592/attachment.h>