Prev: Naked Netbook
Next: Finding the common elements in two strings .
From: mohangupta13 on 29 Apr 2010 09:52
Hello all , I tried to analyse the (fast/slow ) pointer method of
detecting loops in a linked list..

Here we have two pointers one S growing one at a time (by s=s->next)
and the other F growing 2 at a time(by F=F->next->next),,,,
both start at the head of the list and the procedure returns true when
a loop is detected (i.e S==F).

Analysis:
Now suppose we have a list with m1 elements preceding the loop and m2
elements in the loop (a total of m1+m2)..
now considering elements in the loop say a->b->c->d->e->a , and say
both s==a at the start and f=a+2 (say) which in the present example is
'c' , now to find the minimum number of iterations after which
s==f ,we number each element in the loop from 0,1,2....m2-1,
so say after x iterations we have s==f then,

(2x+2)=xmod m2
i.e (2x+2 -x) is divisible by m2, i.e minimum value of x= (m2-2)...

now if we started from the head of the list s takes m1 iterations to
reach the first element of the loop and by this time f moves 2*m1
steps of which m1 are to cover the prefix of the list before the loop
and the rest m1 steps inside the loop , halting at m1%m2 element in
the list ....so now the loop process begins and from above it takes
(m2- m1%m2) iterations (substitution m1%m2 for 2)

so total iterations to detect the loop is == (m1+ m2 - m1%m2)..

Is the above analysis correct ???? Is there a more simpler and
intuitive proof ( should not have to be mathematically valid..just
intuitive)???

Thanks
Mohan
From: Pascal J. Bourguignon on 29 Apr 2010 13:51
mohangupta13 <mohangupta13(a)gmail.com> writes:

> Hello all , I tried to analyse the (fast/slow ) pointer method of
> detecting loops in a linked list..
>
> Here we have two pointers one S growing one at a time (by s=s->next)
> and the other F growing 2 at a time(by F=F->next->next),,,,
> both start at the head of the list and the procedure returns true when
> a loop is detected (i.e S==F).
>
> Analysis:
> Now suppose we have a list with m1 elements preceding the loop and m2
> elements in the loop (a total of m1+m2)..
> now considering elements in the loop say a->b->c->d->e->a , and say
> both s==a at the start and f=a+2 (say) which in the present example is
> 'c' , now to find the minimum number of iterations after which
> s==f ,we number each element in the loop from 0,1,2....m2-1,
> so say after x iterations we have s==f then,
>
> (2x+2)=xmod m2
> i.e (2x+2 -x) is divisible by m2, i.e minimum value of x= (m2-2)...
>
> now if we started from the head of the list s takes m1 iterations to
> reach the first element of the loop and by this time f moves 2*m1
> steps of which m1 are to cover the prefix of the list before the loop
> and the rest m1 steps inside the loop , halting at m1%m2 element in
> the list ....so now the loop process begins and from above it takes
> (m2- m1%m2) iterations (substitution m1%m2 for 2)
>
> so total iterations to detect the loop is == (m1+ m2 - m1%m2)..
>
> Is the above analysis correct ????

It's hard to understand, so it's probably wrong.

> Is there a more simpler and
> intuitive proof ( should not have to be mathematically valid..just
> intuitive)???

Let me try.


A circular chained list is compounded of a handle of length h (there are
h pointers, from n0 to nh), and a loop of length l (there are l pointers
from nh to nh). h∈ℕ, l∈ℕ, l>0.

The nodes are n0, n1, ... nh, n(h+1), ... n(h+l-1)
^ |
| |
+------------------+


If l=1, then slow and fast will meet after h steps.

When l>1, when slow arrives on nh, fast will have already done some
steps in the loop.

If h is odd, then fast will be in n(h-1+(h+1)[l]).
(fast enters the loop starting with the n(h+1)).
slow and fast will meet on nk with
μk, h+(k[l]) = h-1+((h+1+2k)[l]) (1)
(μk = the smallest k such as,
k[l] = k modulo l).

If h is even, then fast will be in n(h+(h[l])).
(fast enters the loop starting with the nh).
slow and fast will meet on nk with
μk, h+(k[l]) = h+((h+2k)[l]) (2)

So you just have to solve these two equations, (1) and (2).

--
__Pascal Bourguignon__
From: Willem on 29 Apr 2010 14:28
Pascal J. Bourguignon wrote:
) Let me try.
)
)
) A circular chained list is compounded of a handle of length h (there are
) h pointers, from n0 to nh), and a loop of length l (there are l pointers
) from nh to nh). h??????, l??????, l>0.
)
) The nodes are n0, n1, ... nh, n(h+1), ... n(h+l-1)
) ^ |
) | |
) +------------------+
)
)
) If l=1, then slow and fast will meet after h steps.
)
) When l>1, when slow arrives on nh, fast will have already done some
) steps in the loop.
)
) If h is odd, then fast will be in n(h-1+(h+1)[l]).
) (fast enters the loop starting with the n(h+1)).
) slow and fast will meet on nk with
) ??k, h+(k[l]) = h-1+((h+1+2k)[l]) (1)
) (??k = the smallest k such as,
) k[l] = k modulo l).
)
) If h is even, then fast will be in n(h+(h[l])).
) (fast enters the loop starting with the nh).
) slow and fast will meet on nk with
) ??k, h+(k[l]) = h+((h+2k)[l]) (2)
)
) So you just have to solve these two equations, (1) and (2).

Still seems complicated.

How about this:

After h steps, the slow pointer will have entered the loop.
The fast pointer is already inside the loop. It will be
ahead of the slow pointer by h steps. In other words, it
is behind by -h steps.

However, because they are both in a loop of size l, being
ahead or behind is always modulo l, so the fast pointer
is *actually* behind by -h mod l. It will then take
that many more steps for it to catch up.

So that's h steps, plus -h mod l steps.

-h mod l is equal to: l * ((-h/l) - floor(-h/l))
So it's in the range [0 .. l)

This also proves the intuitive result that the number
of steps is in the range [h .. h+l)


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: mohangupta13 on 30 Apr 2010 10:38
On 29 Apr, 20:28, Willem <wil...(a)turtle.stack.nl> wrote:
> Pascal J. Bourguignon wrote:
>
> ) Let me try.
> )
> )
> ) A circular chained list is compounded of a handle of length h (there are
> ) h pointers, from n0 to nh), and a loop of length l (there are l pointers
> ) from nh to nh).  h??????, l??????, l>0.
> )
> ) The nodes are n0, n1, ... nh, n(h+1), ... n(h+l-1)
> )                           ^                  |
> )                           |                  |
> )                           +------------------+
> )
> )
> ) If l=1, then slow and fast will meet after h steps.
> )
> ) When l>1, when slow arrives on nh, fast will have already done some
> ) steps in the loop.  
> )
> ) If h is odd,  then fast will be in n(h-1+(h+1)[l]).
> )                    (fast enters the loop starting with the n(h+1)).
> )                    slow and fast will meet on nk with
> )                       ??k,  h+(k[l]) = h-1+((h+1+2k)[l])     (1)
> )                    (??k = the smallest k such as,
> )                     k[l] = k modulo l).
> )
> ) If h is even, then fast will be in n(h+(h[l])).
> )                    (fast enters the loop starting with the nh).
> )                    slow and fast will meet on nk with
> )                       ??k,  h+(k[l]) = h+((h+2k)[l])         (2)
> )
> ) So you just have to solve these two equations, (1) and (2).
>
> Still seems complicated.
>
> How about this:
>
> After h steps, the slow pointer will have entered the loop.
> The fast pointer is already inside the loop.  It will be
> ahead of the slow pointer by h steps.  In other words, it
> is behind by -h steps.
>
> However, because they are both in a loop of size l, being
> ahead or behind is always modulo l, so the fast pointer
> is *actually* behind by -h mod l.  It will then take
> that many more steps for it to catch up.
>
> So that's h steps, plus -h mod l steps.
>
> -h mod l is equal to: l * ((-h/l) - floor(-h/l))

i.e -hmod l =( l- hmod l)
so in total = h+ (l -hmod l)= h+l -hmodl = (m1+m2 - m1mod m2) (= what
i said , so my analysis seems correct )????

> So it's in the range [0 .. l)
>
> This also proves the intuitive result that the number
> of steps is in the range [h .. h+l)
>
> SaSW, Willem
> --
> Disclaimer: I am in no way responsible for any of the statements
>             made in the above text. For all I know I might be
>             drugged or something..
>             No I'm not paranoid. You all think I'm paranoid, don't you !
> #EOT

From: Pascal J. Bourguignon on 1 May 2010 16:43
mohangupta13 <mohangupta13(a)gmail.com> writes:

> i.e -hmod l =( l- hmod l)
> so in total = h+ (l -hmod l)= h+l -hmodl = (m1+m2 - m1mod m2) (= what
> i said , so my analysis seems correct )????

Sorry, I forgot a ":-)" after "it's probably wrong".

--
__Pascal Bourguignon__
 |  Next  |  Last
Pages: 1 2
Prev: Naked Netbook
Next: Finding the common elements in two strings .