Алгоритм определения наличия рекурсии в односвязанном списке. Есть идеи лучше?

Код не читал. В питоне не самый большой специалист. Имхо, самый простой способ определения в закольцованности в связанном списке - проход по связям и маркировка элементов.

def recur_detect(first, n=10, s=5): # False - no recurence # True - recurence found a=first b=a.next if not a : return False c=0 while b: c+=1 if b is a: return True if c==n: n+=s s*=2 c=0 a=b

b=b.next return False

вот эта функция все делает - остальное просто тесты и реализация списка. есть только указатель на первый элемент в котором есть next - указатель на сл. и.т.д.

на c++ будет что-то типа такого
bool recur_detect2(item * head) {
   item * cur  = head;
   std::set<item *> m;
   while (cur) {
      m.insert(cur);
      cur = cur->next;
      if (m.find(cur) != m.end()) {
          return true;
      }
   }
   return false;
}

в общем смысл ясен - по мере прохождения списка ставим метки, если нашли уже помеченный узел то зациклились

вот точный эквивалент того что я написал на C

typedef struct _Node Node;

struct _Node
{
	Node *next;
};

bool detect_recur(Node *first, unsigned int n=10, unsigned int s=5)
{
	if (!first) return false;
	Node *a=first;
	Node *b=a->next;
	unsigned int c=0;
	while (b)
	{
		c++;
		if (b==a) return true;
		if (c==n)
		{
			n+=s;
			s*=2;
			c=0;
			a=b;
		}
		b=b->next;
	}
	return false;
}

>в общем смысл ясен - по мере прохождения списка ставим метки, если нашли уже помеченный узел то зациклились

а если в списке 1000000 элементов? А sizeof(item*) == 4 ? это ты 4 гига заалокируешь? И сколько будет идти m.find(cur)? если m.count() == 1000000?

Сравни с моей реализацией - аллокируем только 1 указатель и 3 инта И на каждом ходу только 1 сравнение.

Непосредственно метить элементы с точки зрения алгоритмической сложности все-таки выгоднее. Ну это так ... чистоплюйство.

Я не понял, что такое n и s ? Может я угадал твою мысль, а может и 
нет, но если ты жмешь память, и несколько плюешь на скорость + если 
есть возможность подсчитать число элементов списка, то можно замутить 
такой алгоритм: 

n - число элементов списка

i=0

while (a) 
{
   a = a->next  

   i = i+1   
   
   if (i >= n) return true 
 
} 

return false

с точностью до ошибки :) Правда точный элемент на котором будет 
"кольцеваться" так не определишь 

n и s - это просто параметры влияющие только на скорость можно выбрать любые целые >1 - влияют только на скорость - алгоритм правильно отработает при любых значениях во всех случаях

А память - просто аллокация это медленная операция, и вообще я забыл сказать что исходный список модифицировать нельзя, а метить - это модификация. Тем более если список не имел места для меток изначально то добавить их сложно, тем более не будучи уверенным в нерекурсивности...

Точный элемент на который зацикленно узнавать и не надо...

Я бы описал как работает мой алгоритм но ИМХО это лучше понять из кода...

Кстати реализация на питоне работает более чем хорошо так, как я ее написал, просто интересно можно ли лучше...

Кстати в питонском варианте я написал unittest'ы для того, чтобы можно было представить граничные значения...

Два указателя. Последовательно увеличиваем. Первый идет i++ второй j+=2. Если указатели стали ровны - значит список зациклен.

set хранит информацию в сбалансированном дереве. в худшем случае он будет работать как log(n).

>это ты 4 гига заалокируешь?

это при том, что если в списке лежат данные, а он не сам по себе, то он у тебя будет занимать >> 4 гигов.

>Два указателя. Последовательно увеличиваем. Первый идет i++ второй j+=2. Если указатели стали ровны - значит список зациклен.

идея интересная, но если петля большая то будет медленно... Но все равно респект :)

Попробуй использовать prefetch, чтоб было быстрее.

>>Два указателя. Последовательно увеличиваем. Первый идет i++ второй j+=2. Если указатели стали ровны - значит список зациклен.

А еще может случится такая редкая ситуация когда второй будет постоянно перескакивать через 1й. Т.е. для точного обнаружения надо чтобы 1 шел i++ а второй тоже j++ Но на каждые 2 движения первого надо 1 второго.

У меня похожий алгоритм но все таки у него есть отличия и я все таки думаю что он в среднем эффективнее, особенно в экстремально граничных случаях. Например когда одна большая петля или много элементов в начале а в конце маленькая пеиля.

>Два указателя. Последовательно увеличиваем. Первый идет i++ второй j+=2. Если указатели стали ровны - значит список зациклен.

Совершенно правильный алгоритм. Такой в умных книжках чаще всего и предлагают. Один указатель -- быстрый, а другой -- медленный. Все верно. Если сравнялись, то цикл.

>идея интересная, но если петля большая то будет медленно... Но все равно респект :)

А быстрее все равно никак - тебе по-любому надо хотя бы разок по циклу пробежаться. А этот алгоритм как раз после одного пробега (медленным указателем, который по 1 идет) цикл и поймает.

> А еще может случится такая редкая ситуация когда второй будет постоянно перескакивать через 1й.

Не может. В цикле второй за один ход сокращает расстояние до первого на единицу и в любом случае его догонит.

>Не может. В цикле второй за один ход сокращает расстояние до первого на единицу и в любом случае его догонит.

Да действительно...