2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение16.05.2010, 21:47 
Аватара пользователя
Привет всем.

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

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

Код:
/* 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];$

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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение16.05.2010, 21:51 
Аватара пользователя
2-D представление.

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение16.05.2010, 21:53 

(Оффтоп)

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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение16.05.2010, 21:58 
Аватара пользователя
errnough в сообщении #320309 писал(а):
2-D представление.


Это как?

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

(Оффтоп)

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


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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение16.05.2010, 22:07 
Аватара пользователя
2-D это значит пространственное представление, в плоскости листа.

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

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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение16.05.2010, 22:13 
Аватара пользователя
errnough в сообщении #320320 писал(а):
2-D это значит пространственное представление, в плоскости листа.

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

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


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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение16.05.2010, 22:28 
Аватара пользователя
creative в сообщении #320325 писал(а):
Всё же не понимаю.

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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение17.05.2010, 00:30 
Аватара пользователя
errnough в сообщении #320334 писал(а):
creative в сообщении #320325 писал(а):
Всё же не понимаю.

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


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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение17.05.2010, 00:46 
2errnough
Цитата:
а здесь не забанят за отрицание учения Дэкстры?

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

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

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

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

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

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

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

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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение17.05.2010, 01:30 
Аватара пользователя
Circiter в сообщении #320377 писал(а):
..., либо получить путем эмуляции работы программки в уме. Да, именно так. Обычно я просто пытаюсь выполнить цикл также как это бы делал компьютер; после нескольких попыток, как правило, понимание работы алгоритма таки приходит. :)

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


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

 
 
 
 Re: Как Вы понимаете сложные циклы? Пользуетесь инвариантом?
Сообщение17.05.2010, 01:54 
Аватара пользователя
creative в сообщении #320372 писал(а):
"официальное" название этого метода в литературе и в каких книжках он описан?


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

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

Например.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group