[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: lists.texi

From: Luc Teirlinck
Subject: Re: lists.texi
Date: Tue, 21 Jun 2005 14:45:53 -0500 (CDT)

After thinking a bit more, the algorithm I propose to install (took 23
seconds in the test case) seems clearly superior over the one that
took 20 seconds.  The reason is that my proposed algorithm is linear
in the _length_ of the ring, the 20 second algorithm is linear in the
_size_ of the ring.  The test case involved a ring of size and lenght
1000, but for rings of large size and small lengths, the 20 second
algorithm is completely hopeless.  Running `ring-elements' ten
thousand times on an empty ring of size one thousand, the algorithm a
propose took zero seconds (well, to be precise, an unmeasurable amount
of time), the 20 second algorithm _still_ took 20 seconds.

The original buggy algorithm and my corrections of it that did not get
the order right, were _also_ linear in the _size_ of the ring, so in
that sense the new algorithm does not only produce a more satisfactory
result, but is also more efficient. 



reply via email to

[Prev in Thread] Current Thread [Next in Thread]