Возврат значения из замыкания

Но параллельно тому месту в котором Флойд завершится (и + 1). То есть всё равно эта точка нужна.

Зачем нужна? Стартуем с самого начала и получаем точку (первое совпадение значений).

Зачем нужна?

1. Посмотри код anonymousа. Если есть идея как сделать лучше - код в студию. Я просто посчитал количество итераций для такого подхода, ты можешь опровергнуть мой результат и привести правильный, и/или показать другой подход и посчитать количество итераций для него.

Стартуем с самого начала и получаем точку (первое совпадение значений).

2. Какую точку и каких значений? Ну и опять - см. 1.

Не понял, какого значения? Флойд нашел не точку зацикливания. Он нашел точку, просто находящуюся в цикле. Далее нам нужно идти «одновременно»(черепахами) с начала списка и с точки, найденной флойдом, передвинув ее на один узел вперед(иначе ее никогда не догонит вторая черепаха). Это если без циферок - с циферками было выше. И без кода - код тоже был выше. Я, кстати, такие задачки до сих пор решаю на бумаге, рисуя квадратики и стрелочки=)

2. Какую точку и каких значений? Ну и опять - см. 1.

Точку начала цикла. Значение функции (ну в данном случае - проверяем на равенство указатели).

Флойд нашел не точку зацикливания. Он нашел точку, просто находящуюся в цикле.

Да. И длину цикла.

Далее нам нужно идти «одновременно»(черепахами) с начала списка и с точки, найденной флойдом

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

Ну а почему бы не подтвердить «очевидное» математически?

Так оно подтверждается простой формулой: (n * k) mod k = 0. Зачем там наворачивать то, что навернул quasimoto мне неясно.

очевидно же

Ну так где выражение для общего количества итераций?

Имхо, к ошибке приводит

(cdr x)

Вот улучшенная версия кода anonymousа:

#include <stdio.h>

struct list { int x; struct list *xs; };

struct list *find_col(struct list *z)
{
    if (!(z && z->xs)) return NULL;
    struct list *x = z->xs, *y = z->xs->xs;
    for (; x && y && y->xs && x != y; x = x->xs, y = y->xs->xs);
    return y ? y->xs ? x : NULL : NULL;
}

// requires: x == find_col(z)
struct list *find_cyc(struct list *z, struct list *x)
{
    for (; z != x; z = z->xs, x = x->xs);
    return z;
}

void print_list(struct list *z)
{
    struct list *x = find_col(z);
    if (x) {
        x = find_cyc(z, x);
        for(; z != x; z = z->xs) printf("%d[%p] ", z->x, z);
        z = x; printf("%d[%p] ", z->x, z);
        for(z = x->xs; z != x; z = z->xs) printf("%d[%p] ", z->x, z);
        z = x; printf("-> %d[%p]", z->x, z);
    } else {
        for(; z; z = z->xs) printf("%d[%p] ", z->x, z);
    }
    puts("");
}

int main()
{
    struct list z1 = { 1, NULL }, z2 = { 2, NULL }, z3 = { 3, NULL }, z4 = { 4, NULL };
    z1.xs = &z2;
    z2.xs = &z3;
    z3.xs = &z4;
    print_list(&z1);
    z4.xs = &z1;
    print_list(&z1);
    z4.xs = &z2;
    print_list(&z1);
    z4.xs = &z3;
    print_list(&z1);
    z4.xs = &z4;
    print_list(&z1);
}

Количество итераций:

n = i + k (i ─ начало цикла, j ─ его длина)

    , i                  if i ≡ 0 (mod k)         T ≤ n
T = | 
    ` n + i - i % k      otherwise                n ≤ T < 2 × n

Рассуждаем так ─ пускаем два итератора ─ быстрый и медленный, ─ из начала списка, медленный пройдёт до начала цикла за i, быстрый при этом окажется в точке 2 × i (это всё в арифметике ручки, она отличается от обычной арифметики по модулю тем, что в ней счёт идёт как 0, 1, 2, ..., i, i + 1, i + 2, ... k - 1, i, i + 1, i + 2, ... вместо 0, 1, 2, ..., k - 1, 0, 1, ...), переводим в арифметику петли (просто по модулю k) и получаем 0 и i % k, если при этом i ≡ 0 (mod k), то сразу находим цикл и его точку за i итераций, если нет, то допустим, что за p шагов быстрый итератор догонит медленный, для этого p будем иметь 0 + p ≡ i + p (mod k), такое p всегда существует, его минимальным значением будет p = k - i % k < k, то есть видим, что быстрый итератор догонит медленный за неполный проход по петле. В этой точке p (в арифметике петли, p + i ─ в арифметике ручки) мы уже детектировали цикл, но ещё не нашли его точку, эту точку можно найти за i шагов, так как p + i ≡ 0 (mod k). Итого, у нас либо i, либо i + k - i % k + i = n + i - i % k итераций.

Твою энергию, да в мирных бы целях ;)

пусть l - длина ручки, k - длина цикла, n - некоторое целое, тогда минимальное 3nk>l <= 3l+3k - итерации, которые нужны на вход в цикл, 2l+k - итерации на поиск входа. 5l+4k итераций максимум, и это неулучшаемая оценка (под «итерацией» понимается смещение либо зайца либо черепахи на 1 позицию).

если при этом i ≡ 0 (mod k), то сразу находим цикл и его точку за i итераций

Не за i. За i+k, как минимум (если длина ручки равна нулю, то черепаха должна пройти весь цикл).

5l+4k итераций максимум, и это неулучшаемая оценка

2 * l + k - l % k лучше, причём это не оценка а точное количество итераций:

#include <cassert>
#include <cstdio>
#include <cstdlib>

struct list {
    int value;
    list *next;
};

struct list_builder {

    list *first, *cycle, *last;

    list_builder(size_t i, size_t k) : first(0), cycle(0), last(0)
    {
        if (i == 0 && k == 0) return;

        first = (list*)malloc(sizeof(list));
        list *cur = first;
        cur->value = 1;
        for (size_t p = 2; p <= i + k; ++p) {
            cur = cur->next = (list*)malloc(sizeof(list));
            cur->value = p;
            if (p == i + 1) cycle = cur;
        }

        last = cur;

        cur->next = k ? cycle : 0;
    }

    ~list_builder()
    {
        list *prev = first, *cur = first ? first->next : 0;
        for (; cur && cur != last; prev = cur, cur = cur->next)
            free(prev);
        free(prev);
        free(cur);
    }

};

class cycle_finder {

    list *l, *col, *cyc;
    size_t iters;

    list *iter(list *z)
    {
        ++iters;
        return z->next;
    }

    list *find_col_impl(list *z)
    {
        if (!(z && z->next)) return 0;
        list *x = iter(z), *y = z->next->next;
        for (; x && y && y->next && x != y; x = iter(x), y = y->next->next);
        return y ? y->next ? x : 0 : 0;
    }

    list *find_cyc_impl(list *z, list *x)
    {
        for (; z != x; z = iter(z), x = x->next);
        return z;
    }

  public:

    explicit cycle_finder(list *l) : l(l), col(0), cyc(0), iters(0) {}

    list *find_col()
    {
        if (!col) col = find_col_impl(l);
        return col;
    }

    list *find_cyc()
    {
        if (!col) col = find_col_impl(l);
        if (col && !cyc) cyc = find_cyc_impl(l, col);
        return cyc;
    }

    size_t get_iters()
    {
        return iters;
    }

};

void print_list(struct list *z)
{
    cycle_finder cf(z);
    list *x = cf.find_col();
    if (x) {
        x = cf.find_cyc();
        for(; z != x; z = z->next) printf("%d[%p] ", z->value, z);
        printf("%d[%p] ", z->value, z);
        for(z = x->next; z != x; z = z->next) printf("%d[%p] ", z->value, z);
        printf("-> %d[%p]", z->value, z);
    } else {
        for(; z; z = z->next) printf("%d[%p] ", z->value, z);
    }
    puts("");
}

size_t my_guess(size_t i, size_t k)
{
    return i ? k ? i % k ? 2 * i + k - i % k : 2 * i : i / 2 : k / 2;
}

size_t your_guess(size_t i, size_t k)
{
    return 5 * i + 4 * k;
}

int main()
{
    for (size_t i = 0; i <= 10; ++i) {
        for (size_t k = 0; k <= 10; ++k) {
            list_builder lb(i, k);
            cycle_finder cf(lb.first);
            assert(cf.find_cyc() == lb.cycle);
            puts  ("------------------");
            printf("         i = %lu\n", i);
            printf("         k = %lu\n", k);
            printf("real iters = %lu\n", cf.get_iters());
            printf("  my guess = %lu\n", my_guess(i, k));
            assert(cf.get_iters() == my_guess(i, k));
            printf("your guess = %lu\n", your_guess(i, k));
            // assert(cf.get_iters() == your_guess(i, k));
            print_list(lb.first);
        }
    }
}

2 * l + k - l % k лучше

Ты итерации не так считаешь. Если мою оценку на твои итерации перевести, то получится l+k на поиск цикла и l на определение точки входа, то есть то, что у тебя. Только у тебя k - l % k, а я взял просто k, т.к. k - l % k = k при длине ручки кратной длине цикла, то есть на точность оценки твой «хвостик» (-l%k) никак не влияет.

Небольшой фикс:

29c29
<         cur->next = k ? cycle ? cycle : cycle = first : 0;
---
>         cur->next = k ? cycle : 0;
35,38d34
<         if (prev == cur) {
<             free(cur);
<             return;
<         }
114c110
<     return i ? k ? i % k ? 2 * i + k - i % k : 2 * i : i / 2 : k;
---
>     return i ? k ? i % k ? 2 * i + k - i % k : 2 * i : i / 2 : k / 2;

теперь для списков без циклов, с полными циклами или с ручками :)

Не за i. За i+k, как минимум

Да, не за i. За 2 * i. Я забыл, что хотя мы и оказываемся сразу в точке цикла, всё равно этого не знаем и должны пройтись ещё i раз.

Ты итерации не так считаешь.

Ты сказал «пусть l - длина ручки, k - длина цикла» и «под „итерацией“ понимается смещение либо зайца либо черепахи на 1 позицию», вот я так и считаю.

то есть на точность оценки

Так я не про оценку говорю, а про точное выражение. То что оно O(n) и так «очевидно».

Я забыл, что хотя мы и оказываемся сразу в точке цикла, всё равно этого не знаем и должны пройтись ещё i раз.

i это же длина ручки. Длину ручки мы второй раз проходить не должны, максимум мы должны пройти весь цикл, то есть i+k.

Ты сказал «пусть l - длина ручки, k - длина цикла» и «под „итерацией“ понимается смещение либо зайца либо черепахи на 1 позицию», вот я так и считаю.

Нет, ты считаешь за цикл смещение черепахи на 1 шаг, а смещение зайца вообще не считаешь. Если считать как я, то только чтобы пройти всю ручку (то есть дойти до цикла черепахе) черепахе надо пройти l шагов, а зайцу - 2l. то есть 3l шагов.

Длину ручки мы второй раз проходить не должны, максимум мы должны пройти весь цикл, то есть i+k.

i ? k ? i % k ? 2 * i + k - i % k : 2 * i : i / 2 : k;

Если i = 0, то видим k шагов (k = 2 * k (mod k) и точка столкновения совпадает с началом списка), если i > 0 и i кратно k - видим 2 * i. Так алгоритм устроен - именно на том чтобы пройти ручку второй раз (это всегда возможно и имеет основной смысл в нахождении точки цикла после точки столкновения).

черепахе надо пройти l шагов, а зайцу - 2l. то есть 3l шагов.

Даже если так - всё равно получается неточная (раза в два) оценка которую можно улучшить.

Ты тявкнул, что message passing на Си красиво сделать невозможно. Тебя рыльцем ткнули в факт, что возможно. Признавай, что обосрался, чмо уродливое.

Даже если так - всё равно получается неточная (раза в два) оценка которую можно улучшить.

Вообще-то получается в точности твое выражение, только у тебя k-l%k, а у меня просто k. Но в худшем случае k-l%k=k, так что твоя оценка ничем не лучше.

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

Так это при чем? Речь же шла не поиске точки цикла, а о первом вхождении в цикл.

Вообще-то получается в точности твое выражение

Мы считаем за итерацию каждое взятие next у списка (которое f на википедии)? Если i - длина ручки, k - длина цикла, то там будет i ? k ? i % k ? 5 * i + 3 * k - 3 * (i % k) : 5 * i : 3 * (i / 2) : 3 * k. Это всяко меньше чем 5 * i + 4 * k.

Так это при чем?

Я везде про полное количество итераций говорил (там где ты поправил про «не i» - в том предельном случае полное не i, да, но и не i + k).

Мы считаем за итерацию каждое взятие next у списка (которое f на википедии)?

Да.

Это всяко меньше чем 5 * i + 4 * k.

Нет, это не меньше. Я же указал - оценка неулучшаема.

но и не i + k

i+k - это максимум.

Нет, это не меньше

В моём представлении 76 = 5 * 8 + 3 * 20 - 3 * (8 % 20) таки меньше чем 120 = 5 * 8 + 4 * 20.

i+k - это максимум.

Реальное количество итераций (3 * i при i = 0 или 5 * i при i кратном k) может быть больше чем i+k - это не максимум.

может быть больше чем i+k

Нет, не может.

(3 * i при i = 0 или 5 * i при i кратном k)

при i=0 будет k (3k если считать мои итерации) итераций. при i кратном k будет i итераций.

В моём представлении 76 = 5 * 8 + 3 * 20 - 3 * (8 % 20) таки меньше чем 120 = 5 * 8 + 4 * 20.

Давайте по порядку. Алгоритм Флойда в худшем случае работает ровно 3i+3(k-1) итераций, с этим вы согласны, так?

Нет, не может.

i = 4
k = 2
n = i + k = 4 + 2 = 6

1 2 3 4 5 6 -> 5

считаем, получаем 5 * i = 20 > n. Можно даже тупо на бумажке проверить как происходит обход списка. И даже до входа в цикл 3 * i = 12 > n.

при i=0 будет k (3k если считать мои итерации) итераций.

Да. Это полное количество итераций для нахождения точки цикла в данном случае.

при i кратном k будет i итераций.

Противоречит даже примеру выше для n = 4 + 2. Ну и вообще - это подразумевается мой способ счёта? Фишка же в том, что мы не знаем кратно ли i к k, не знаем их самих и нам даже n не нужно, мы ищем i, в данном случае это потребует 5 * i итераций. Ты просто не сможешь написать код который сделает всё за i итераций при i кратном k - программно никак нельзя сразу сказать «вот мы прошли i шагов», можно только сравнить указатели и найти точку столкновения (i и k пока неизвестны - нельзя сразу сказать, является ли эта точка точкой начала цикла), после чего можно опять пойти черепахой из начала ручки и черепахой из точки столкновения, тогда равенство указателей уже найдёт нам i.

Алгоритм Флойда в худшем случае работает ровно 3i+3(k-1) итераций, с этим вы согласны, так?

Не знаю. Мне проще было посчитать точное количество итераций два раза (для кода anonymousа и для моего слегка изменённого). Оно не худшее и не лучше - просто всегда точно такое. Также я вижу, что оно O(n) и коэффициент меньше пяти (то есть < 5 * n). Для твоего соотношения тоже O(n) и < 5 * n, но оно неточное. Наверно, нужно было подчеркнуть этот момент когда я просил выражение для итераций - имелась ввиду не оценка, а точное выражение. Впрочем, оценка с тем же коэффициентом это тоже хорошо.

ИМХО на сишечку смысла нет - передача сообщений ИМХО в C это изначально быдлокод.

Ты тявкнул, что message passing на Си красиво сделать невозможно. Тебя рыльцем ткнули в факт, что возможно. Признавай, что обосрался, чмо уродливое.

не вижу опровержения здесь: http://en.wikipedia.org/wiki/Linda_(coordination_language) или я не туда смотрю?

считаем, получаем 5 * i = 20 > n. Можно даже тупо на бумажке проверить как происходит обход списка. И даже до входа в цикл 3 * i = 12 > n.

Так речь же и идет о входе в цикл.

Ну и вообще - это подразумевается мой способ счёта?

Да.

Так речь же и идет о входе в цикл.

А вход всегда происходит ровно за i (или 3 * i если всё считать) по определению.

Да.

Ну вот с моим способом счёта для n = i + k = 4 + 2 полное количество итераций будет 2 * i = 8 > i + k. Если там вдруг будет ровно i, то это уже обсчёт алгоритма который нигде в треде не был представлен = нужно написать код который будет _так_ работать и его уже считать. То что было представлено так не работает, соответственно, так считать нельзя.

Опровержения чего, мразь? Что это не уродство? Ну так покажи, чмо, где именно в Линде уродство.

Опровержения чего, мразь?

вот этого, если ты забыл:

ИМХО на сишечку смысла нет - передача сообщений ИМХО в C это изначально быдлокод.

Ну так покажи, чмо, где именно в Линде уродство.

идея хорошая, но инструмент выбран неправильно.

PS: нервные летки таки восстанавливаются. Но очень медленно. Если ты так и дальше будешь злится, то возможно ты не доживёшь до их восстановления, и к старости будешь страдать слабоумием (если доживёшь). Спокойнее надо быть.