Как Вы понимаете сложные циклы? Пользуетесь инвариантом?

[creative]

Привет всем.

Предположим перед Вами сложный цикл, нужно понять что он делает, находите ли Вы инвариантные отношения, которые выполняются в каждой интерации цикла, с целью применить эти инвариантные отношения ко всей области значений, которые принимают переменные в результате полного выполнения цикла?

Объясню описанный выше вопрос на примере:

/* example from "The Practice of Programming" * 
 * by Brian W. Kernighan and Rob Pike           */

void swap(int v[], int i, int j)
{
    int tmp;
    tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
}

void quicksort(int v[], int n)
{
    int i, last;
    if ( n <= 1 )
        return;
    swap(v, 0, rand() % n);
    last = 0;
    for ( i = 1; i < n; i++ )
        if (v[i] < v[0])
            swap(v, ++last, i);
    swap(v, 0, last);
    quicksort(v, last);
    quicksort(v + last + 1, n - last - 1);
}

У меня всегда были проблемы в понимании работы подобных циклов, когда описывают последовательным образом (шаг за шагом), что они делают.

Единственное понимание которое я нашёл адекватным это не представление в динамике, того что происходит при выполнении цикла, а статичная картина, то есть следующие инвариантные отношения при выполнении цикла:

$last \leq i;$
$1 \leq x \leq last \to v[x] < v[0];$
$last \leq x < n \to v[x] \geq v[0];$

И принимая во внимание строчку

swap(v, 0, last);

получаем:

$last \leq i;$
$0 \leq x \leq last - 1 \to v[x] < v[last];$
$last \leq x < n \to v[x] \geq v[last];$

Вопрос в том, используете ли Вы на практике такой метод понимания того, что делает сложный цикл?
Если нет (хотя я пока не вижу других альтернатив понимания), то какими методами Вы понимаете что делает сложный цикл?

[errnough]

2-D представление.

[lel0lel]

(Оффтоп)

Это разве сложный цикл?)) Видимо вы ещё не пуганы совсем!

[creative]

errnough в сообщении #320309 писал(а):

2-D представление.

Это как?

lel0lel в сообщении #320310 писал(а):

(Оффтоп)

Это разве сложный цикл?)) Видимо вы ещё не пуганы совсем!

Это объяснение на примере.

[errnough]

2-D это значит пространственное представление, в плоскости листа.

1. Всё должно поместится в поле зрения сразу.
2. Никаких пересечений линий.

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

[creative]

errnough в сообщении #320320 писал(а):

2-D это значит пространственное представление, в плоскости листа.

1. Всё должно поместится в поле зрения сразу.
2. Никаких пересечений линий.

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

Всё же не понимаю. Можно на моём примере? Или литературу, где подобный метод описывается.

[errnough]

creative в сообщении #320325 писал(а):

Всё же не понимаю.

Дизассемблируйте свой пример и посмотрите сколько там джампов. Они в Си есть, только мы их глазами совершаем. (а здесь не забанят за отрицание учения Дэкстры?). Каждый джамп открывает свою петлю. Эту петлю выносите из пересечения на свободное пространство листа. И так распутываете логику. Узлы рыболовной сети распутывали?

[creative]

errnough в сообщении #320334 писал(а):

creative в сообщении #320325 писал(а):

Всё же не понимаю.

Дизассемблируйте свой пример и посмотрите сколько там джампов. Они в Си есть, только мы их глазами совершаем. (а здесь не забанят за отрицание учения Дэкстры?). Каждый джамп открывает свою петлю. Эту петлю выносите из пересечения на свободное пространство листа. И так распутываете логику. Узлы рыболовной сети распутывали?

Примерно понял суть твоего метода, но только примерно. Достаточно интересно, какое "официальное" название этого метода в литературе и в каких книжках он описан?

[Circiter]

2errnough

Цитата:

а здесь не забанят за отрицание учения Дэкстры?

Вы про goto? Нет, не забанят. :) Этот оператор может быть полезен, например, при эффективной реализации конечных автоматов (а то некоторые их через "тормознутый" switch пишут).

-- Пн май 17, 2010 03:57:12 --

2creative

Цитата:

какими методами Вы понимаете что делает сложный цикл?

Честно говоря, никогда не задумывался над этим... :) Я просто пытаюсь видеть смысл написанного кода, так, как если бы передо мной была логическая формула c кванторами типа $\forall i\in X$...

То есть мне важна лишь структура цикла и объяснение его работы. Объяснение это можно либо вычитать из документации или комментариев, либо получить путем эмуляции работы программки в уме. Да, именно так. Обычно я просто пытаюсь выполнить цикл также как это бы делал компьютер; после нескольких попыток, как правило, понимание работы алгоритма таки приходит. :)

-- Пн май 17, 2010 04:06:50 --

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

P.S.: О как хороши чистые функциональные языки в которых вообще нет циклов. :)

[creative]

Circiter в сообщении #320377 писал(а):

..., либо получить путем эмуляции работы программки в уме. Да, именно так. Обычно я просто пытаюсь выполнить цикл также как это бы делал компьютер; после нескольких попыток, как правило, понимание работы алгоритма таки приходит. :)

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

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

[errnough]

creative в сообщении #320372 писал(а):

"официальное" название этого метода в литературе и в каких книжках он описан?

Учтите, Вы спросили про восстановление алгоритма, а не про написание кода. Пишем мы либо для компилятора, либо для процессора,— код, а вот восстанавливаем для той машинки, что у нас в голове,— алгоритм. А она, голова, построчные записи алгоритма с трудом воспринимает, сами убедились, наверное.

Самое близкое пожалуй, здесь. Книга Паронджанова там же. Те же принципы: непересечение связей, однозначность, строгое направление движения по графу и т.д. Но практически, там не хватает почти половины до действительно рабочего инструмента. Поэтому, дальше кто во что горазд :)

Например.