This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Question on tree-walking and mutually-recursive types
On Tue, 29 Jun 2004, Michael Matz wrote:
> Hi,
>
> On Tue, 29 Jun 2004, Joseph S. Myers wrote:
>
> > On Tue, 29 Jun 2004, Michael Matz wrote:
> >
> > > ??? This tests if list_{2j+1} or list_{2j+2} equals list_j. Hence it
> > > doesn't detect cycles. Cf list == {1,2,3,1}
> >
> > Take j=n-1 for for a cycle of period n.
>
> Either I'm dense or your and mine definition of cycles differ quite a bit.
>
> My list is actually the shortest counter-example. Zack's code would have
> q on '1' and p on '2' then '3', then it advances q to '2' and p to '1'
> which is the last step. Never is '1' and '1' compared.
It isn't the "last step" without some other magical means of stopping on a
cycle. The cycle is effectively {1,2,3,1,2,3,1,2,3,...} (infinite), so 1
is compared to 2 and 3; then 2 to 1 and 2, and the cycle detected, so it
isn't then necessary to do the next steps that would be comparing 3 to 3
and 1, 1 to 2 and 3, ....
> I don't see how this loop will work, except when heavily changed to
> basically do the O(n*2) every-element to every-element test (for instance
Worst case would be O(n^2). This is O(n) (= O(2n)).
> breaking the loop on q being at end; some optimizations possible). For
> instance q stops after half of lists elements, so if the cycle is in the
> second half it also never sees it.
There is no "half of lists elements", because without being given a priori
knowledge of the length of the cycle (or whether there is one) you are
just following a possibly infinite chain and don't stop unless either it
is in fact finite (some element has no successor) or two identical
elements have been located.
--
Joseph S. Myers http://www.srcf.ucam.org/~jsm28/gcc/
jsm@polyomino.org.uk (personal mail)
jsm28@gcc.gnu.org (Bugzilla assignments and CCs)