1
\$\begingroup\$

Reading the article in Wikipedia about cycle detection I came across a relatively small code snipped of Floyd's cycle-finding algorithm. I'll put it here to keep everything in one place:

def floyd(f, x0):
    # The main phase of the algorithm, finding a repetition x_mu = x_2mu
    # The hare moves twice as quickly as the tortoise
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))

    # at this point the start of the loop is equi-distant from current tortoise
    # position and x0, so hare moving in circle and tortoise (set to x0 )
    # moving towards circle, will intersect at the beginning of the circle.

    # Find the position of the first repetition of length mu
    # The hare and tortoise move at the same speeds
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1

    # Find the length of the shortest cycle starting from x_mu
    # The hare moves while the tortoise stays still
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1

    return lam, mu

But then I decided, why not rewrite this algorithm using iterators.

The result wasn't as good as I had hoped it to be.

In some parts of the code I needed the values that the iterators have already returned. So I had keep the values apart from iterators themselves. And I introduced the class animal to keep them in one place.

To my mind, the code got very hefty and ugly. Here it is:

# -*- coding: utf-8 -*-

from __future__ import print_function
from itertools import islice,cycle,chain


def detect_cycle(iterable):

    class animal(object):
        '''Holds the iterator and keeps the last value returned by the iterator'''
        def __init__(self,iterable):          
            self.it = iter(iterable)
            self.value = next(self.it) #get the first value

        def next(self):
            self.value = next(self.it)
            return self.value

        def __iter__(self):
            return self


    tortoise = animal(iterable)
    hare = animal(islice(iter(iterable),None,None,2))  #two steps at a time

    while True:
        if next(tortoise) == next(hare):
            break

    hare = tortoise #put hare in the place of tortoise
    tortoise = animal(iterable) #start tortoise from the very beginning
    mu = 0
    while True:
        if hare.value == tortoise.value:
            break
        next(hare)
        next(tortoise)
        mu += 1


    lamb = 0
    tortoise_val = tortoise.value #save the value of tortoise as the object is reassigned to hare
    hare = tortoise
    while True:
        next(hare)
        lamb += 1
        if hare.value == tortoise_val: #check AFTER the first step by hare
            break

    print('mu: {}'.format(mu))
    print('lamb: {}'.format(lamb))


if __name__ == '__main__':

    class iterable(object):
        '''Emulate the object returning iterators having cycles'''
        def __init__(self,beginning,cycling):
            '''
beginning: the beginning part with no cycles (its length corresponds to mu)
cycling: the part which will be cycling (its length corresponds to lamb)
'''
            self.beginning = beginning
            self.cycling = cycling

        def __iter__(self):
            return chain(iter(self.beginning),cycle(iter(self.cycling)))

    detect_cycle(iterable('1234','678'))

Is there anything that can be done to improve the code? Is it the best that can be done using iterators?

\$\endgroup\$
3
\$\begingroup\$
# -*- coding: utf-8 -*-

from __future__ import print_function
from itertools import islice,cycle,chain


def detect_cycle(iterable):

    class animal(object):

Putting classes inside function is usually not all that helpful. Also, the name doesn't really suggest what this class does.

        '''Holds the iterator and keeps the last value returned by the iterator'''
        def __init__(self,iterable):          
            self.it = iter(iterable)

I'd do something like iter, just because it isn't a really obvious abbreviation

            self.value = next(self.it) #get the first value

        def next(self):
            self.value = next(self.it)
            return self.value

        def __iter__(self):
            return self


    tortoise = animal(iterable)
    hare = animal(islice(iter(iterable),None,None,2))  #two steps at a time

You end up create two iterators from the same iterable. That might be problematic as you can't be sure those two iterators are independent.

    while True:
        if next(tortoise) == next(hare):
            break

You get most of the benefit of iterators when you can use for loops. In this case, I might use a for loop with itertools.izip.

    hare = tortoise #put hare in the place of tortoise
    tortoise = animal(iterable) #start tortoise from the very beginning
    mu = 0
    while True:
        if hare.value == tortoise.value:
            break
        next(hare)
        next(tortoise)
        mu += 1

You do this basic thing three times. You loop through both iterators, until they match. Write a function that takes the two iterators, does that and then returns the count of them.

    lamb = 0
    tortoise_val = tortoise.value #save the value of tortoise as the object is reassigned to hare
    hare = tortoise
    while True:
        next(hare)
        lamb += 1
        if hare.value == tortoise_val: #check AFTER the first step by hare
            break

    print('mu: {}'.format(mu))
    print('lamb: {}'.format(lamb))
\$\endgroup\$
  • \$\begingroup\$ Thank you for suggestions. I have updated the code. Here it is: ideone.com/fYZ35. About the independence of iterators. I think it's very important. But I only came up with adding a warning in the description. Because I can't use itertools.tee since it'll defeat all the benefits of using this algorithm (since it'll be storing all the intermediary values). Also the usage of chain(repeat((tortoise.val, hare.val),1)... looks particularly ugly for me. But I haven't found any other way to add a single value to the chain. \$\endgroup\$ – ovgolovin Jan 16 '12 at 13:22
  • \$\begingroup\$ I've made another version of the code which uses no class: ideone.com/fAlML All the logic which used to be covered in the code is no scattered around the code (the calculation of the first value follows a new iterator initialization always). Still, I don't like the code. The only conclusion I can draw from the experiment is that the original version of the code operating with indexes is more clear, short and straightforward. \$\endgroup\$ – ovgolovin Jan 16 '12 at 13:31
  • \$\begingroup\$ Update 1: ideone.com/vJKiv Still curious, if it's the best way to add a single value before the main iterator: chain(repeat(hare_val,1),hare) (here hare_val is added befor all the other values returned by hare iterator). \$\endgroup\$ – ovgolovin Jan 16 '12 at 13:40
  • \$\begingroup\$ Update 2: ideone.com/fgrwM Put all while True: code fragments into the function. Had to bring back the holding iterator class since otherwise I would have to return the current values of the iterator from that function somehow which will make the code completely cumbersome. \$\endgroup\$ – ovgolovin Jan 16 '12 at 14:15
  • \$\begingroup\$ @ovgolovin, instead of repeat(hare_val, 1) just use [hare_val]. What if consume_iterator... returned the matching value as well as the count? I think then you can get rid of keeping iterator. \$\endgroup\$ – Winston Ewert Jan 17 '12 at 5:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.