Сравнение двух стилей программирования

[Shadow]

Мне показалось, что подсказка про Ахила и черепаху была достаточно толстой. Ахил и черепаха на старте. Ахил делает два шага, черепаха один. Если все нормально, Ахил без проблем добежит до финиша, а если нет - Ахил без проблем добежит до...жопу черепахи (окажутся на одном и том же месте). Тоесть, достаточно двух указателей. Более "жесткий" вариант будет: Определит в каком месте список зацикливает. Где это "плохое место".

[Munin]

shau-kote в сообщении #659294 писал(а):

Вы хотите сказать, что это не очевидно (не стоит считать очевидным)?

Да, не стоит считать очевидным.

-- 17.12.2012 02:41:15 --

rockclimber в сообщении #659522 писал(а):

Я слышал эту задачу в более жесткой формулировке. Когда нельзя использовать для хранения промежуточных данных структуры, сравнимые по размером со списком. Например, у вас список из 1000 элементов, а вам разрешается использовать 2 - 3 переменные.

Это плохое ужесточение формулировки. В современных условиях обычно как раз наоборот: затраты памяти менее важны, чем затраты времени, так что выбирать следует более быстрые, а не более компактные алгоритмы. А такое ограничение приводит к увеличению времени с $O(N\log N)$ до $O(N^2).$ И ещё штришок: алгоритм со временем $O(N\log N)$ (но и с затратами памяти дополнительными $O(N)$) делается просто, "неизящно" и с использованием стандартных компонент, а для алгоритма $O(N^2)$ ещё подумать надо :-)

[Shadow]

Хранить в массив (в худшем случае) всю динамичную память...дa еще проверять на каждом шагу было ли такое или не было. Даже не представляю что это за "О" будет.

[Xaositect]

Munin в сообщении #659556 писал(а):

rockclimber в сообщении #659522 писал(а):

Я слышал эту задачу в более жесткой формулировке. Когда нельзя использовать для хранения промежуточных данных структуры, сравнимые по размером со списком. Например, у вас список из 1000 элементов, а вам разрешается использовать 2 - 3 переменные.

Это плохое ужесточение формулировки. В современных условиях обычно как раз наоборот: затраты памяти менее важны, чем затраты времени, так что выбирать следует более быстрые, а не более компактные алгоритмы. А такое ограничение приводит к увеличению времени с $O(N\log N)$ до $O(N^2).$ И ещё штришок: алгоритм со временем $O(N\log N)$ (но и с затратами памяти дополнительными $O(N)$) делается просто, "неизящно" и с использованием стандартных компонент, а для алгоритма $O(N^2)$ ещё подумать надо

Munin, Вы что-то путаете. Алгоритм "черепахи и зайца", до которого тут уже догадались, использует $O(N)$ элементарных операций (переход к следующему элементу и сравнение указателей) и использует константную память - 2 указателя. Здесь $N$ - это количество различных элементов списка.
Есть еще алгоритм Брента, который еще проще и быстрее - запоминаем $2^k$ позицию списка и идем от нее $2^k$ шагов, проверяя равенство, доходим до $2^{k+1}$ - запоминаем ее и идем еще $2^{k+1}$ шагов и т.д.

[shau-kote]

Munin в сообщении #659556 писал(а):

Да, не стоит считать очевидным.

Хорошо, соглашусь.
Но тем не менее, получается, вопрос только в документации?
Т.е. если я сейчас напишу краткую документацию к данной процедуре (десятое дело, куда я её вставлю потом), в которой напишу, что необходимыми условиями для корректной работы процедуры является то-то и то-то, то проблема будет решена?
Просто если добавить обработку ошибок, то она может также быть не очевидной. Зато возрастёт объём документации.
То есть обращение с процедурой мы не упростим, зато усложним документацию к ней.

[Munin]

shau-kote в сообщении #662464 писал(а):

Но тем не менее, получается, вопрос только в документации?

Нет. Вопрос в обращении внимания на те вещи, от которых наивные первокурсники привыкли отмахиваться (и некоторые так и продолжают отмахиваться вплоть до своей профессиональной деятельности, которая именно поэтому оборачивается низкокачественной). А уж что делать с этими вещами: реализовывать их в коде, указывать в документации, или вообще перепроектировать всё заново - это вопрос отдельный, после того, как вы на эти вещи внимание обратили. Единого рецепта тут нет, а надо исходить из ситуации.

shau-kote в сообщении #662464 писал(а):

если я сейчас напишу краткую документацию к данной процедуре (десятое дело, куда я её вставлю потом)

Ха, отнюдь не десятое. Это вопрос примерно того же уровня, что и куда вставить саму процедуру.

shau-kote в сообщении #662464 писал(а):

Просто если добавить обработку ошибок, то она может также быть не очевидной. Зато возрастёт объём документации.
То есть обращение с процедурой мы не упростим, зато усложним документацию к ней.

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

[shau-kote]

Munin, признаю Вашу правоту по всем пунктам.
Спасибо. (: