2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4, 5, 6
 
 Re: Сравнение двух стилей программирования
Сообщение17.12.2012, 01:09 
Мне показалось, что подсказка про Ахила и черепаху была достаточно толстой. Ахил и черепаха на старте. Ахил делает два шага, черепаха один. Если все нормально, Ахил без проблем добежит до финиша, а если нет - Ахил без проблем добежит до...жопу черепахи (окажутся на одном и том же месте). Тоесть, достаточно двух указателей. Более "жесткий" вариант будет: Определит в каком месте список зацикливает. Где это "плохое место".

 
 
 
 Re: Сравнение двух стилей программирования
Сообщение17.12.2012, 01:36 
Аватара пользователя
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)$ ещё подумать надо :-)

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

 
 
 
 Re: Сравнение двух стилей программирования
Сообщение17.12.2012, 02:39 
Аватара пользователя
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}$ шагов и т.д.

 
 
 
 Re: Сравнение двух стилей программирования
Сообщение23.12.2012, 18:49 
Аватара пользователя
Munin в сообщении #659556 писал(а):
Да, не стоит считать очевидным.

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

 
 
 
 Re: Сравнение двух стилей программирования
Сообщение24.12.2012, 03:12 
Аватара пользователя
shau-kote в сообщении #662464 писал(а):
Но тем не менее, получается, вопрос только в документации?

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

shau-kote в сообщении #662464 писал(а):
если я сейчас напишу краткую документацию к данной процедуре (десятое дело, куда я её вставлю потом)

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

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

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

 
 
 
 Re: Сравнение двух стилей программирования
Сообщение24.12.2012, 23:48 
Аватара пользователя
Munin, признаю Вашу правоту по всем пунктам.
Спасибо. (:

 
 
 [ Сообщений: 82 ]  На страницу Пред.  1, 2, 3, 4, 5, 6


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