Oberon space
General Category => Общий раздел => Тема начата: valexey от Март 24, 2011, 03:11:57 pm
-
Нашел на просторах интернетов. Собственно очень было бы интересно посмотеть как эта задачка решается на:
1) Oberon-07 (можно даже M)
2) Oberon-2
3) КП в динамической среде исполнения (в ББ например).
Маленький Эксель
----------------
Необходимо реализовать простую электронную таблицу в виде программы, выполняющейся
из командной строки. Она должна уметь обрабатывать ячейки таблицы как и более
продвинутые аналоги, только с упрощенным синтаксисом выражений. Каждая ячейка
может содержать:
- Ничего
- Неотрицательное целое число
- Текстовые строки, которые начинаются с символа '
- Строки-выражения, которые начинаются с символа '=' и могут содержать
неотрицательные целые числа, ссылки на ячейки и простые арифметические
выражения. Скобки запрещены, у всех операций одинаковый приоритет.
Ссылки на ячейки состоят из одной латинской буквы и следующей за ней
цифры.
Эти ограничения введены для упрощения разбора выражений, поскольку разбор
выражений не является основной частью проблемы. Вы можете спокойно
положиться на эти ограничения. Вот грамматика содержимого ячейки:
expression ::= '=' term {operation term}*
term ::= cell_reference | nonnegative_number
cell_reference ::= [A-Za-z][0-9] --
operation ::= '+' | '-' | '*' | '/'
text ::= '\\'' {printable_character}
Процесс обработки:
- Все выражения должны быть заменены на вычисленный результат.
- Все вычисления выполняются с помощью целочисленной арифметики со знаком.
- Ячейки с текстом должны быть вычислены как соответствующий текст без
префикса '.
- Операции над строками текста запрещены.
- В случае любой ошибки вычисления формулы, вычисляемая ячейка должна содержать
слово-сообщение об ошибке, начинающееся с символа '#'. Используйте короткие,
ясные сообщения. Не надо предоставлять подробности об ошибках в выводе.
Программа должна использовать только стандартные библиотеки и классы и не должна
вызывать сторонние программы, библиотеки или системные компоненты.
Ввод и вывод
------------
Программа получает описание таблицы с формулами из стандартного ввода,
вычисляет ее и печатает полученный результат в стандартный вывод. Входные
данные представлены таблицей, элементы строк которой разделены табуляциями.
Первая строка содержит пару чисел, разделенных табуляцией - высоту и
ширину таблицы, соответственно. Затем идут строки с ячейками таблицы,
в грамматике, приведенной выше.
Выход должен содержать только ожидаемую информацию, включая сообщения об
ошибках, и никакой другой информации в выводе не должно быть, включая и
welcome text. Выход должен быть отформатирован в соответствии с приведенным
ниже примером.
Пример данных:
3 4
12 =C2 3 'Sample
=A1+B1*C1/5 =A2*B1 =B3-C3 'Spread
'Test =4-3 5 'Sheet
Ожидаемый вывод:
12 -4 3 Sample
4 -16 -4 Spread
Test 1 5 Sheet
Указания по решению
-------------------
Необходимо промышленное качество кода. Более короткое и читаемое решение
предпочтительней. Решение должно содержать тестовые примеры и код, использованные
в процессе создания решения. Не забудьте откомментировать код в ключевых
местах. Код должен быть устойчив к ошибкам.
Представьте, что это требования к первой фазе проекта. Необходимо реализовать
только то, что нужно на этой фазе. Однако, известно, что планируется вторая
фаза, в которой требования будут расширены следующими:
- Расширить формулы операциями над строками,
- Оптимизировать производительность для громадных таблиц.
Вам необходимо будет указать, какие изменения необходимо сделать для
реализации второй фазы проекта.
С этой задачей в одной конторе не справился ни один из тех, кому ее давали. Точнее, не справился в полном объеме. После более или менее успешного ее решения проводилось интервью. Задача использовалась для выявления потенциальных архитекторов.
-
Да, ТЗ задачки такой какой он есть. Уточняющие вопросы задавать не разрешается. Разрешается только сразу выдать ответ.
-
Да, времени на задачку давалось 2-3 дня (это давалось на дом, до собеседования). Впереди как раз выходные, условия у всех участников сего форума в точности те же (или лучше) нежели у тех кто был пред собеседованием.
-
кстати, вот этот пункт:
Программа должна использовать только стандартные библиотеки и классы и не должна
вызывать сторонние программы, библиотеки или системные компоненты.
Применительно к оберонам можно и обсудить. Потому как если руководствоваться только language report'ами, то там и Hello World не написать.
-
Ну вот моё решение: [тут покопался злобный валексей и скрыл ссылку до понедельника, жалобы принимаются]
Я справился с задачей со сверхсветовой скоростью, за -3.5 года )))
-
Ссылку скрыл, дабы народ не отвлекался на изучение чужих решений (ибо это больно уж затягивающее занятие) а написал что-нибудь своё. Хочется таки хоть одно решение на каком-нибудь Обероне.
Если geniepro возразит супротив такой меры, то моментально все верну взад. Ну, или если народ массово против вдруг будет.
-
В общем, относительно стандартных либ, я считаю так: стандартное все, что идет искаробки с выбранным компиятором/средой. Нестандартные сборки в рассчет не берутся.
То есть, если это BB, то пользоваться можно всем тем, что идет в наборе от Оминков.
Если это XDS, то пользоваться тем, что идет с ним искаропки.
Если это Oberon-07M.. Ну, похоже тут и выбора то не остается :-) Единственное но -- желательно таки в логике программы не использовать что-то WinAPI'шно-привязанное. (кроме всего прочего, решение данной задачки может и должно послужить толчком к созданию на Оберон-07М стандартной библиотеки).
-
Хотя, конечно, Оберон-2 можно было бы ограничить библиотекой из Дубовых Требований.
-
Если geniepro возразит супротив такой меры, то моментально все верну взад. Ну, или если народ массово против вдруг будет.
Да я-то до понедельника потерплю, чо уж там ))
В общем, относительно стандартных либ, я считаю так: стандартное все, что идет искаробки с выбранным компиятором/средой. Нестандартные сборки в рассчет не берутся.
То есть, если это BB, то пользоваться можно всем тем, что идет в наборе от Оминков.
Если это XDS, то пользоваться тем, что идет с ним искаропки.
То есть учебную сборку от инфо21 юзать низзя? ))
А Haskell Platform годится? Ибо он рекомендуемой производителем сборкой является и стандарт де-факто...
-
То есть учебную сборку от инфо21 юзать низзя? ))
Ни в коем ни в случае! :-)
А Haskell Platform годится? Ибо он рекомендуемой производителем сборкой является и стандарт де-факто...
А это надо подумать. Потому как, в отличае от Оберонов, у хаскеля таки есть стандартная библиотека вполне достаточная для данной задачи. Наверно так -- если получилось обойтись тем и только тем, что есть в описании стандарта (haskell 2010, кстати), то отлично. если вылезли во вне и заюзали что-то нестандартное (в плане библиотек) из Haskell Platform, то это не серьезная ошибка дизайна, при условии, что оно реализовано не только в ghc, и серьезная (но не фатальная), если есть только в ghc.
-
А это надо подумать. Потому как, в отличае от Оберонов, у хаскеля таки есть стандартная библиотека вполне достаточная для данной задачи. Наверно так -- если получилось обойтись тем и только тем, что есть в описании стандарта (haskell 2010, кстати), то отлично. если вылезли во вне и заюзали что-то нестандартное (в плане библиотек) из Haskell Platform, то это не серьезная ошибка дизайна, при условии, что оно реализовано не только в ghc, и серьезная (но не фатальная), если есть только в ghc.
Так кроме GHC других промышленных трансляторов у Хаскелла нет, а Haskell Platform -- его рекомендуемая сборка.
-
А это надо подумать. Потому как, в отличае от Оберонов, у хаскеля таки есть стандартная библиотека вполне достаточная для данной задачи. Наверно так -- если получилось обойтись тем и только тем, что есть в описании стандарта (haskell 2010, кстати), то отлично. если вылезли во вне и заюзали что-то нестандартное (в плане библиотек) из Haskell Platform, то это не серьезная ошибка дизайна, при условии, что оно реализовано не только в ghc, и серьезная (но не фатальная), если есть только в ghc.
Так кроме GHC других промышленных трансляторов у Хаскелла нет, а Haskell Platform -- его рекомендуемая сборка.
Ну, про промышленность ghc я бы таки промолчал (ну недотягивает оно до промышенных стандартов в плане стабильности и обратной совместимости, чуточку, но не дотягивает пока). Но вот ведь есть же еще и (Win)Hugs! Вполне популярная реализация haskell'я. Да, в ынтырпрайз оно возможно не пойдет как база, но вот для экспериментов, для разработки, проверки и так далее -- вполне. Оно простое и там цикл разработки быстрее чем на ghci. Оно много более легковесное. Оно дружелюбное. И да, оно умеет часть из того, что умеет и ghc, например монаду ST.
-
Ну, про промышленность ghc я бы таки промолчал (ну недотягивает оно до промышенных стандартов в плане стабильности и обратной совместимости, чуточку, но не дотягивает пока).
Однако GHC используется во вполне серьёзных промышленных проектах. Альтернативы в общме-то ему нет.
Но вот ведь есть же еще и (Win)Hugs! Вполне популярная реализация haskell'я. Да, в ынтырпрайз оно возможно не пойдет как база, но вот для экспериментов, для разработки, проверки и так далее -- вполне. Оно простое и там цикл разработки быстрее чем на ghci. Оно много более легковесное. Оно дружелюбное. И да, оно умеет часть из того, что умеет и ghc, например монаду ST.
Ага, вот только этот самый ST реализован в HUGS по другому, чем в GHC, поэтому библиотека работы с графами не компилируется в HUGS...
Да и как Вы организуете ввод/вывод из консоли в WinHUGS, скажите на милость... ;D
Из нескольких моих решений этой задачи лишь одно запустилось в хугсе, но оно не может правильно обработать циклы в формулах -- выпадает в осадок с переполнением стека...
-
Ну, это я с удовольствием разберу все позжее. Возможно твое решение будет наилучшим просто вследствие отсутствия конкурентов :-)
-
Но вот ведь есть же еще и (Win)Hugs! Вполне популярная реализация haskell'я. Да, в ынтырпрайз оно возможно не пойдет как база, но вот для экспериментов, для разработки, проверки и так далее -- вполне. Оно простое и там цикл разработки быстрее чем на ghci.
Кстати, вот я так до сих пор и не осилил разработку в стиле REPL. С редактором текста и компилятором мне как-то проще. В Хугсе если и запускаю программу, то чисто что бы проверить, есть ли ошибки, и если нет, и алгоритм достаточно быстрый, то что бы тут же протестировать. Но это мало отличается от цикла разработки с компилятором, потому что REPL хугса я очень редко использую.
Да и в GHC есть репл -- GHСi...
-
В качестве теста для программы предложу ещё такой файл:
Input:
[тестовый файл погрыз смусмумрик, благо его все равно никто не обсуждал]
Output
[output загрыз сурок, и инпут и аутпут воскреснут после воскресенья]
-
expression ::= '=' term {operation term}*
cell_reference ::= [A-Za-z][0-9] --
text ::= '\\'' {printable_character}
Что означает звёздочка в конце expression?
Что означают два минуса в конце cell_reference?
-
expression ::= '=' term {operation term}*
cell_reference ::= [A-Za-z][0-9] --
text ::= '\\'' {printable_character}
Что означает звёздочка в конце expression?
* в данной грамматике видимо означает необязательность элемента.
Примеры expression:
=A1
=A1+B1
=A1+B1*C1/5
Что означают два минуса в конце cell_reference?
Непонятно. Видимо, ошибка копипаста. Возможно, там раньше был комментарий.
Валидные примеры cell_reference:
A1
B2
C3
Zz99
и т.д.
PS. Кстати, эта задача была тестом не просто на построение хорошей архитектуры программы, а на её построение в условиях неточностей в ТЗ -- это частая ситуация в промышленности. Типа -- в неясных случаях надо догадаться и действовать сообразно здравому смыслу и принятых практик.
-
PS. Кстати, эта задача была тестом не просто на построение хорошей архитектуры программы, а на её построение в условиях неточностей в ТЗ -- это частая ситуация в промышленности. Типа -- в неясных случаях надо догадаться и действовать сообразно здравому смыслу и принятых практик.
Хотя, возможно, это я уже сейчас нафантазировал... ;D
-
expression ::= '=' term {operation term}*
cell_reference ::= [A-Za-z][0-9] --
text ::= '\\'' {printable_character}
Что означает звёздочка в конце expression?
* в данной грамматике видимо означает необязательность элемента.
Тогда звёздочка должна быть и в text, не так ли?
Валидные примеры cell_reference:
Zz99
Последнее не является валидным. В условиях оговорено, что только одна буква и одна цифра, и cell_reference это отражает (если убрать минусы).
-
expression ::= '=' term {operation term}*
cell_reference ::= [A-Za-z][0-9] --
text ::= '\\'' {printable_character}
Что означает звёздочка в конце expression?
* в данной грамматике видимо означает необязательность элемента.
Тогда звёздочка должна быть и в text, не так ли?
Нет, не так. Элемент в фигурных скобках повторяется 1 или более раз. Текст должен содержать хотя бы один символ.
Всё верно.
Валидные примеры cell_reference:
Zz99
Последнее не является валидным. В условиях оговорено, что только одна буква и одна цифра, и cell_reference это отражает (если убрать минусы).
Да, точно, это уже я нафантазировал. Я давно решал эту задачку, уже подзабыл ))
-
Кстати, Гапертон (автор задачи) вспоминал, что корни этой задачи идут из книги Барбары Лисков про язык CLU "Abstraction and specification in programm development, 1986" ("Использование абстракций и спецификаций при разработке программ", Лисков Б., Гатэг Дж.)
Там была похожая задача, расчитанная на семестр для группы из нескольких студентов. но там требовалось ещё и интерактивный интерфейс пользователя сделать (текстовый, типа как в SuperCalc)...
-
Выходит, что text должен иметь хотя бы один символ, иначе ошибка? Странно.
-
Что означает звёздочка в конце expression?
"Иные" используют собственную нотацию, которая эквивалентна РБНФ.
Описание, если не ошибаюсь, можно посмотреть в Книге Дракона.
(Для них главное, чтобы было не как у Вирта :))
-
Выходит, что text должен иметь хотя бы один символ, иначе ошибка? Странно.
Почему странно? Пустая строка -- это пустая ячейка, значит текстовая строка должна быть непустой, раз её специально помечают кавычкой.
-
Выходит, что text должен иметь хотя бы один символ, иначе ошибка? Странно.
Почему странно? Пустая строка -- это пустая ячейка, значит текстовая строка должна быть непустой, раз её специально помечают кавычкой.
Я бы не стал смешивать пустую строку и пустую ячейку. Если мы потом добавляем выражения со строками, то при ссылке на пустую ячейку лучше получить ошибку "нет значения", чем считать её пустой строкой.
-
Что означает звёздочка в конце expression?
"Иные" используют собственную нотацию, которая эквивалентна РБНФ.
Описание, если не ошибаюсь, можно посмотреть в Книге Дракона.
(Для них главное, чтобы было не как у Вирта :))
Я так понимаю, там зачем-то использованы регулярные выражения вместо обычного РБНФ'а.
-
Я так понимаю, там зачем-то использованы регулярные выражения вместо обычного РБНФ'а.
Да нет же. Описание дадено в обычном виде, в виде описания грамматики для бизона. Оно эквивалентно РБНФ.
-
Хотя я похоже не прав, это не бизоново описание грамматики. Но что-то очень-очень мне знакомое. По моему, Сишная грамматика (и оттуда С++, ява, C#) так же описана. Если мне эклер не изменяет, то оно было эквивалентно БНФ, но судя по звездочкам её таки проапгрейдили до РБНФ.
-
Я бы не стал смешивать пустую строку и пустую ячейку. Если мы потом добавляем выражения со строками, то при ссылке на пустую ячейку лучше получить ошибку "нет значения", чем считать её пустой строкой.
Возьмём "взрослую" электронную таблицу, например Эксель. Он пустые ячейки считает заполненными нулями в арифметических выражениях и пустыми строками в строковых выражениях.
-
Это уже вопрос архитектуры, кстати. По сути имеем дилемму – строгая у нас будет типизация, или же не строгая.
-
Это уже вопрос архитектуры, кстати. По сути имеем дилемму – строгая у нас будет типизация, или же не строгая.
Я решил сделать строгую типизацию (строгость снимается тривиально, а вот добавить туда, где её не было изначально, сложнее). Язык - XDS Oberon-2, используемые модули In и Out - "дубовые" (можно и на WinApi-консоль перейти, это не сложно).
-
Теперь можно и на чужие решения поглядеть. : )
-
Теперь можно и на чужие решения поглядеть. : )
А до понедельника потерпишь? Впрочем, я могу в личку дать ссыль.
-
Ссыль уехала в личку.
Ждем кого-нибудь еще :-) Я кстати, тоже думаю попробовать. В чужие решения я не смотрел, там страшно :-)
-
Не публикуйте пока. Будет ишшо пример, на КП :)
-
Угу. Жду как минимум понедельника (вечера понедельника, утром обычно мне хочется на работу, и я больше ни о чем думать не могу :-) ).
По запросу могу и ещё резину потянуть :-)
-
Добавлены и поправлены комментарии, плюс исправлена константа MaxHeight в процедуре LoadTable.
-
Добавлены и поправлены комментарии, плюс исправлена константа MaxHeight в процедуре LoadTable.
Мда, программа на обероне-2 внушаит -- 383 locs.
Мои два решения имеют 118 locs (первое) и 180 locs (с проверкой циклов в формулах)
-
А если в лексемах подсчитать? :-)
-
Мда, программа на обероне-2 внушаит -- 383 locs.
Я 380 насчитал.
-
В лексемах слабо. Решил сравнить в размере конкретно кода, сжатого zip-ом.
Все комментарии и пустые строки выкинул, естественно. Выравнивание кода сохранил.
Оберон-2 вариант: zip: 2565 байт, распакованный вид: 10362 байт
Haskell, 1-й вариант: zip: 1591 байт, распакованный вид: 4821 байт
Haskell, 2-й вариант: zip: 2189 байт, распакованный вид: 7795 байт
-
Мда, программа на обероне-2 внушаит -- 383 locs.
Я 380 насчитал.
Да, я позже пересчитал строки, тоже 380 вышло, но поправить пост уже не смог. ((
-
В лексемах слабо. Решил сравнить в размере конкретно кода, сжатого zip-ом.
Все комментарии и пустые строки выкинул, естественно. Выравнивание кода сохранил.
Оберон-2 вариант: zip: 2565 байт, распакованный вид: 10362 байт
Haskell, 1-й вариант: zip: 1591 байт, распакованный вид: 4821 байт
Haskell, 2-й вариант: zip: 2189 байт, распакованный вид: 7795 байт
Ну, в общем-то это и на глаз заметно, что строки на хаскелле заметно длиннее, чем на обероне или сях. Это тоже влияет на их количество...
-
Ну, в общем-то это и на глаз заметно, что строки на хаскелле заметно длиннее, чем на обероне или сях. Это тоже влияет на их количество...
Решил уточнить средние длины строк решений (без комментариев и прочего ненужного).
На Хаскелле вышло 39 и 41 символов, на обероне-2 25 символов ;)
-
Угу. Интересны также коэффициенты сжатия:
Oberon-2 10362 2565 4.0397660819
Haskell 1 4821 1591 3.0301697046
Haskell 2 7795 2189 3.5609867519
Отсюда делаем вывод, что программа на хаскеле ближе к белому шуму, ну или к содержимому /dev/random, нежели код на Обероне :-)
-
В лексемах слабо. Решил сравнить в размере конкретно кода, сжатого zip-ом.
Все комментарии и пустые строки выкинул, естественно. Выравнивание кода сохранил.
Оберон-2 вариант: zip: 2565 байт, распакованный вид: 10362 байт
Haskell, 1-й вариант: zip: 1591 байт, распакованный вид: 4821 байт
Haskell, 2-й вариант: zip: 2189 байт, распакованный вид: 7795 байт
Уточнение (три коммента пропустил):
Оберон-2 вариант: zip: 2544 байт, распакованный вид: 10311 байт
-
Самое ТруЪ-решение Задачи-К -- это решение на языке К от самого Трурля:
O:"+-*/"; o:(+;-;*;_%)
split:{(&x _in\\: y)_ x}
mkr:{:[(x<W)&(y<H);"ref[",($y),";",($x),"]";`badref]}
mkv:{x}
mka:{:[x _sm "[a-z][0-9]"; mkr[(_ic*x)-97; (_ic x[1])-49]
x _sm "[A-Z][0-9]"; mkr[(_ic*x)-65; (_ic x[1])-49]
x _sm "[0-9]*"; mkv[x]; `err]}
mkf:{t:split["+",1_ x;O]; `form, +{(o[O?*x]; mka[1_ x])}'t}
parse: {:[x~"";`; *x _sm "[0-9]*"; 0$x;(*x)="'"; 1_ x; (*x)="="; mkf[x]; `err]}
read:{in: {1_'split["\\t",x;,"\\t"]}'0: x; wh:0$*in; W::wh[0]; H::wh[1]; S::parse''1 _ in}
show:{x 0:{x,"\\n",y}/{x,"\\t",y}/'$S}
ref:{if[~4:S[x;y]; force[x;y]]; S[x;y]}
force:{t:S[x;y]; if[`eval~*t; S[x;y]:`cycle]; if[`form~*t; S[x;y;0]:`eval; S[x;y]:eval[t]]}
apply:{y[x;z]}
eval:{a: .:'x[2];:[&/1={4:x}'a; apply/[0;x[1];a]; `err]}
read[`in];(!W)force'\\:!H;show[`out]
Метрика: 16 locs, 47 симв/стр, в сжатом виде 570 байта, в распакованном 782 байт, коэф. сжатия 1.372
-
Самое ТруЪ-решение Задачи-К -- это решение на языке К от самого Трурля:
А что, он - первоначальный автор задания?
Ещё вопрос, в каких отношениях находятся языки K и Q?
-
Самое ТруЪ-решение Задачи-К -- это решение на языке К от самого Трурля:
А что, он - первоначальный автор задания?
Автор задания -- Влад Балин aka Gaperton, который сделал своё решение на Эрланге, обосновав это тем, что все другие языки он давно забыл, а Эрланг настолько прост, что забыть его невозможно.
А ТруЪ-решение -- ну ведь логично, что задача К должна быть решена на языке К. :о)
Ещё вопрос, в каких отношениях находятся языки K и Q?
http://en.wikipedia.org/wiki/Q_(programming_language_from_Kx_Systems)
Как я понял, Q -- более читабельная обёртка над K, используемая для запросов к базе данных KDB...
-
Ещё вопрос, в каких отношениях находятся языки K и Q?
http://en.wikipedia.org/wiki/Q_(programming_language_from_Kx_Systems)
Как я понял, Q -- более читабельная обёртка над K, используемая для запросов к базе данных KDB...
Хотя есть ещё вот такой язык Q -- это совсем уже другое, больше на Хаскелл смахивающее...
http://q-lang.sourceforge.net/
-
Добавлены и поправлены комментарии, плюс исправлена константа MaxHeight в процедуре LoadTable.
оно даже в ББ откомпилялось
-
Как я понял, Q -- более читабельная обёртка над K, используемая для запросов к базе данных KDB...
Моя первая программа на языке q: преобразует положительное целое число в последовательность символов (запись числа).
q)x:18873; L:"012345679"; res:""; while[x>0; res:res,L[x mod 10]; x:x div 10]; reverse res
"18873"Не знаю, как векторизовать без while : (
Подскажите, как улучшить решение!
-
Как я понял, Q -- более читабельная обёртка над K, используемая для запросов к базе данных KDB...
Моя первая программа на языке q: преобразует положительное целое число в последовательность символов (запись числа).
q)x:18873; L:"012345679"; res:""; while[x>0; res:res,L[x mod 10]; x:x div 10]; reverse res
"18873"Не знаю, как векторизовать без while : (
Подскажите, как улучшить решение!
Я не знаток этих брейнфаков, так что я пас... ;D
-
Я не знаток этих брейнфаков, так что я пас... ;D
А можно аналог на Хаскеле?
-
Простейший вариант:
int'to'str :: Integer -> String
int'to'str n = show n
Но это не по-джедайски. Так что вот:
import Char
int'to'str :: Integer -> String
int'to'str 0 = ""
int'to'str n = int'to'str (n `div` 10) ++ [chr $ fromIntegral (n `mod` 10 + fromIntegral(ord '0'))]
Более эффективный на огромных числах вариант:
import Char
int'to'str :: Integer -> String
int'to'str n = i2s n ""
where
i2s 0 ss = ss
i2s n ss = i2s (n `div` 10) ((chr $ fromIntegral (n `mod` 10 + fromIntegral(ord '0'))):ss)
-
Простейший вариант:
int'to'str :: Int -> String
int'to'str n = show n
Но это не по-джедайски.
Да, там тоже есть, я только что дочитал:q)string 18873
"18873"
Так что вот:
import Char
int'to'str :: Int -> String
int'to'str 0 = ""
int'to'str n = int'to'str (n `div` 10) ++ [chr (n `mod` 10 + ord '0')]
Ага, рекурсия. Точно, что это я сразу не подумал?
Спасибо.
-
Ага, рекурсия. Точно, что это я сразу не подумал?
Спасибо.
Императивное мышление вынуждает думать циклами, а не рекурсиями ))
to iterate is human, to recure divine...
;D
-
Практически готовое решение по этой задаче задепонировано Алексею. Опубликую, только когда напишу полную пояснительную статью. Через день-два, думаю.
Объём - 9 модулей, 713 строк (будет под 800, надо думать).
-
Объём - 9 модулей, 713 строк (будет под 800, надо думать).
Чувствуется, что подход очень серьёзный ;D
-
Действительно чувствуется. Серьезно.
Через пару дней сяду, проанализирую. Ну или сразу статью зачту как появится :-)
-
Действительно чувствуется. Серьезно.
Через пару дней сяду, проанализирую. Ну или сразу статью зачту как появится :-)
Будет решение на С++. Минимальное. Попробую выкроить время до вторника.
-
Будет решение на С++. Минимальное. Попробую выкроить время до вторника.
OK. Подождем.
-
Было бы любопытно сделать такую таблицу, расчёт которой занял бы ощутимое время -- интересно было бы сравнить разные варианты решений на скорость вычислений.
Но таблица размером 26*9 не очень способствует таким замерам. Вот если расширить язык этой таблицы, введя возможность вычисления формул -- было бы прикольно...
-
Было бы любопытно сделать такую таблицу, расчёт которой занял бы ощутимое время -- интересно было бы сравнить разные варианты решений на скорость вычислений.
Но таблица размером 26*9 не очень способствует таким замерам. Вот если расширить язык этой таблицы, введя возможность вычисления формул -- было бы прикольно...
Длину формулы, вроде, не ограничивали... : ))
-
Вот если расширить язык этой таблицы, введя возможность вычисления формул -- было бы прикольно...
Хотите сказать, что в вашем решении формулы не вычисляются?
Это заставляет посмотреть на приведённые метрики с новой стороны ; )))
-
Вот если расширить язык этой таблицы, введя возможность вычисления формул -- было бы прикольно...
Хотите сказать, что в вашем решении формулы не вычисляются?
Это заставляет посмотреть на приведённые метрики с новой стороны ; )))
Да описАлся я там -- имел в виду введение пользовательских функций ))
-
Это заставляет посмотреть на приведённые метрики с новой стороны ; )))
Александр, а слабо переделать программу на разумно-модульный вид? Собственно, этого автор задачи и ожидал в качестве хорошего решения -- декомпозиция программы, удобная для развития в будущем.
И вапще прикольная тоже задачка ))
-
Александр, а слабо переделать программу на разумно-модульный вид? Собственно, этого автор задачи и ожидал в качестве хорошего решения -- декомпозиция программы, удобная для развития в будущем.
Слабо, конечно. Я считаю, что процедурная декомпозиция вполне адекватна задаче. Все точки расширения вполне обозримы. Добавить строковые операции? Ищем errStringOp, добавляем нужную константу для operation. Огромные таблицы? Правим загрузку и дереференс ячейки. Избавиться от рекурсии в интерпретации выражений? Поле marked из BOOLEAN превращаем в INTEGER.
Чего тут в модулях прятать-то? Ввод и вывод и так нормально спрятаны в In и Out.
Нет, ну можно, конечно, разбить, чтобы подчеркнуть независимость ввода от расчёта и расчёта от вывода, но надо ли?
Ещё можно уменьшить требования к памяти, вычисляя простые формулы сразу при загрузке, как это сделано для целых чисел и строк. Поможет ли в этом разбиение на модули? Вряд ли.
В общем, на мой взгляд, дополнительные модули не нужны, по крайней мере пока не перевалили за 1000 строк. Посмотрим, что за учебный пример будет у Ильи. Надеюсь, он в моё решение не подглядывал : ))
-
По поводу большой таблицы и вычислений - представьте себе какую-нибудь инкрементальную колоночку в табличке с миллионами строк. Т.е. каждая ячейка ссылается на предыдущую + 1... Хм, только в текущем языке формул нет относительного синтаксиса.
-
По поводу большой таблицы и вычислений - представьте себе какую-нибудь инкрементальную колоночку в табличке с миллионами строк. Т.е. каждая ячейка ссылается на предыдущую + 1... Хм, только в текущем языке формул нет относительного синтаксиса.
Представил и без относительного синтаксиса. Что дальше? В смысле, я не понял, на что намёк?
Если это вы про рекурсивное вычисление, так ведь я решал задачу первого этапа. А про второй этап - подумал и прикинул необходимые изменения: исправить тип поля ExpressionCell.marked и добавить цикл.
Как и было в задании. : )
При таблице 26*9 максимальная глубина рекурсии = 243, а это чуть более 16Кб стэка для моего кода.
Кстати, если кому для тестов надо, вот таблица:9 26
=B1+1 =C1+1 =D1+1 =E1+1 =F1+1 =G1+1 =H1+1 =I1+1 =J1+1 =K1+1 =L1+1 =M1+1 =N1+1 =O1+1 =P1+1 =Q1+1 =R1+1 =S1+1 =T1+1 =U1+1 =V1+1 =W1+1 =X1+1 =Y1+1 =Z1+1 =A2+1
=B2+1 =C2+1 =D2+1 =E2+1 =F2+1 =G2+1 =H2+1 =I2+1 =J2+1 =K2+1 =L2+1 =M2+1 =N2+1 =O2+1 =P2+1 =Q2+1 =R2+1 =S2+1 =T2+1 =U2+1 =V2+1 =W2+1 =X2+1 =Y2+1 =Z2+1 =A3+1
=B3+1 =C3+1 =D3+1 =E3+1 =F3+1 =G3+1 =H3+1 =I3+1 =J3+1 =K3+1 =L3+1 =M3+1 =N3+1 =O3+1 =P3+1 =Q3+1 =R3+1 =S3+1 =T3+1 =U3+1 =V3+1 =W3+1 =X3+1 =Y3+1 =Z3+1 =A4+1
=B4+1 =C4+1 =D4+1 =E4+1 =F4+1 =G4+1 =H4+1 =I4+1 =J4+1 =K4+1 =L4+1 =M4+1 =N4+1 =O4+1 =P4+1 =Q4+1 =R4+1 =S4+1 =T4+1 =U4+1 =V4+1 =W4+1 =X4+1 =Y4+1 =Z4+1 =A5+1
=B5+1 =C5+1 =D5+1 =E5+1 =F5+1 =G5+1 =H5+1 =I5+1 =J5+1 =K5+1 =L5+1 =M5+1 =N5+1 =O5+1 =P5+1 =Q5+1 =R5+1 =S5+1 =T5+1 =U5+1 =V5+1 =W5+1 =X5+1 =Y5+1 =Z5+1 =A6+1
=B6+1 =C6+1 =D6+1 =E6+1 =F6+1 =G6+1 =H6+1 =I6+1 =J6+1 =K6+1 =L6+1 =M6+1 =N6+1 =O6+1 =P6+1 =Q6+1 =R6+1 =S6+1 =T6+1 =U6+1 =V6+1 =W6+1 =X6+1 =Y6+1 =Z6+1 =A7+1
=B7+1 =C7+1 =D7+1 =E7+1 =F7+1 =G7+1 =H7+1 =I7+1 =J7+1 =K7+1 =L7+1 =M7+1 =N7+1 =O7+1 =P7+1 =Q7+1 =R7+1 =S7+1 =T7+1 =U7+1 =V7+1 =W7+1 =X7+1 =Y7+1 =Z7+1 =A8+1
=B8+1 =C8+1 =D8+1 =E8+1 =F8+1 =G8+1 =H8+1 =I8+1 =J8+1 =K8+1 =L8+1 =M8+1 =N8+1 =O8+1 =P8+1 =Q8+1 =R8+1 =S8+1 =T8+1 =U8+1 =V8+1 =W8+1 =X8+1 =Y8+1 =Z8+1 =A9+1
=B9+1 =C9+1 =D9+1 =E9+1 =F9+1 =G9+1 =H9+1 =I9+1 =J9+1 =K9+1 =L9+1 =M9+1 =N9+1 =O9+1 =P9+1 =Q9+1 =R9+1 =S9+1 =T9+1 =U9+1 =V9+1 =W9+1 =X9+1 =Y9+1 =Z9+1 =1
-
Долгожданный С++ вариант :) 530 строк - самый жрный вариант, как я понимаю. Код включает все тесты, которые использовались по ходу.
Комментарии, которые возникли по ходу решения:
1. Стандартной библиотеки явно недостаточно даже для таких простых задач. C boost'ом было бы намного приятнее. Еще приятнее со своими повседневными наработками (ненулевыее указатели, например).
2. Следствие пункта 1 - непривычная головная боль и пляски с динамическими объектами (std::auto_ptr категорически недостаточно).
3. Следствие пукта 1 - пришлось писать циклы и обходится без любимых функциональный штучек (замыканий). Тоже непривычно, неудобно, многословно.
4. Код минималистичный и с минимумом диагностики, но с требуемой возможностью минимального расширения.
5. Никакой оптимизации, дубовое решение, но которое можно точить.
-
Кстати, если кому для тестов надо, вот таблица:
Спасибо, passed :)
-
При таблице 26*9 максимальная глубина рекурсии = 243, а это чуть более 16Кб стэка для моего кода.
Кстати, если кому для тестов надо, вот таблица:
Интересная попытка, но увы! Слишком мало расчётов, пролетает мгновенно, надо что-то покруче...
Да, и 26*9 = 234 всё-таки...
-
Долгожданный С++ вариант :) 530 строк - самый жрный вариант, как я понимаю.
Удалил пустые строки, удалил namespace Test, в объявлении функций тип результата поставил на одну строку с именем функции, и осталось 383 строки. Практически совпадает с моим вариантом на XDS Oberon-2 (380 строк).
Не совсем понятно, правда, почему exe-файл 388Кб. Это с отладочной информацией, наверное?
-
Интересная попытка, но увы! Слишком мало расчётов, пролетает мгновенно, надо что-то покруче...
Да, и 26*9 = 234 всё-таки...
Это я не для расчётов, а для глубины рекурсии. Можно сделать поиск с заменой, исправив "+1" на "*2/2*2/2*2/2*2/2*2/2..." Тогда и рекурсия будет, и расчётов сколько угодно. Впрочем, при моём максимальном числе 255 символов в ячейке всё равно влёт считает.
Почему-то в голове сидело, что в английском алфавите 27 букв. В результате составления таблицы исправил на 26, а результат умножения забыл обновить.
-
Удалил пустые строки, удалил namespace Test, в объявлении функций тип результата поставил на одну строку с именем функции, и осталось 383 строки. Практически совпадает с моим вариантом на XDS Oberon-2 (380 строк).
И в обероне и в C++ можно вообще все в одну строчку налепить :) Тогда уж надо сичтать байты, а не строки :) Тода все упрется еще и в длину иднтификаторов. Дурная характеристика, короче :)
Не совсем понятно, правда, почему exe-файл 388Кб. Это с отладочной информацией, наверное?
Да. 165к без отладочной инфы и без динамических библиотек. Спасибо дурным плюсовым стримам...
-
Влад, в личные сообщения гляньте.
-
Влад, в личные сообщения гляньте.
Деление на ноль поправил.
-
По поводу размера EXE.
У ББ такое бывает для больших статического размера массивов из указателей.
Тогда к дескриптору типов компилятор шьёт огромный список позиций указателей для сборщика.
-
По поводу размера EXE.
У ББ такое бывает для больших статического размера массивов из указателей.
Тогда к дескриптору типов компилятор шьёт огромный список позиций указателей для сборщика.
В данном случае - это просто неудачная (по моему мнению) стандартная библиотека стримов. Которая может делать все и поэтому большая, но при этом все крайне неудобно и непонятно :)
-
Пардон, не понял, что это про размер С++-экземшника, потому что писал Ильин.
-
Произвёл разбиение на модули, получилось аж 6 модулей (против эталонных 4 у Гапертона).
Фактически, 4 из моих модулей содержат всего по нескольку строк кода и расчитаны на возможное развитие проекта в будущем. Два модуля составляют основной объём кода.
Метрика: 214 locs, zip: 2500 байт, распакованный вид: 8815 байт (коэф. сжатия 3.526)
Экзешник пухлый, так уж генерирует код компилятор GHC, сжатием упаковщиком типа NsPack можно уменьшить в несколько раз.
Модуляризация решения увеличила размер исходника (в строках) почти на 20%, за счёт оформления заголовков модулей, импорта и экспорта.
-
Долгожданный С++ вариант :) 530 строк - самый жрный вариант, как я понимаю.
Удалил пустые строки, удалил namespace Test, в объявлении функций тип результата поставил на одну строку с именем функции, и осталось 383 строки. Практически совпадает с моим вариантом на XDS Oberon-2 (380 строк).
Если в программе vlad'а удалить функцию test (и её вызов), то вот ещё -38 строк...
-
Я насчитал целых 4 решения - оберон-2, КП, хаскель, С++. Классно! :) Давайте с ними чего-нибудь сделаем :) Например:
- потестим скорость
- определим недостатки и пределы каждого решения (не кушает формулу больше такой-то длины и т.п.)
- углубим и расширим (как и предполагалось изначально), при этом оценим количество изменений (хотя бы тупой diff).
- еще чего-нибудь - тов. Веселовский должен взять инициативу ;)
P.S. Кстати, неплохо бы иметь exe для всех решений.
-
Какая-то метрия неинтересная началась, коллеги :) Как это бывает с производительностью. Признак нехорошего зуда в одном месте. Какая разница - + 100 строк, - 100 строк?
-
Хорошо, Илья, предложите более годную объективную метрику.
Алексей предлагал считать лексемы, но это из той же оперы.
Как ещё можно "измерить алгеброй гармонию"?
-
Я насчитал целых 4 решения - оберон-2, КП, хаскель, С++. Классно! :)
В джаббере я скидывал Алексею ссылки на кучу ещё решений, там были на яве, вроде, ещё на лиспе, на сях и с++ несколько, несколько вариантов на том же хаскелле, вариант на эрланге...
Давайте с ними чего-нибудь сделаем :) Например:
- потестим скорость
Вот с замером этой самой скорости на текущем размере таблицы 26*9 проблемы -- любая таблица будет расчитана за доли секунды.
Я хотел было попробовать какой-нить фибонначи разложить в таблицу, но понял, что там эти экспоненциальные вычисления будут мемоизированы (или по-русски -- табулированы, в таблице же), и опять же мгновенно рассчитаются...
-
Я насчитал целых 4 решения - оберон-2, КП, хаскель, С++. Классно! :) Давайте с ними чего-нибудь сделаем :) Например:
- потестим скорость
- определим недостатки и пределы каждого решения (не кушает формулу больше такой-то длины и т.п.)
- углубим и расширим (как и предполагалось изначально), при этом оценим количество изменений (хотя бы тупой diff).
- еще чего-нибудь - тов. Веселовский должен взять инициативу ;)
Предлагаю проверить все решения на таком тестовом наборе входных данных:
1 4
=A2+A3 =A1*A3 =A1/A2 'Surprise!
Последнюю ячейку можно исключить :)
PS: Ещё не плохо было бы все решения продублировать в одном сообщении с указанием автора решения и языка реализации.
-
Предлагаю проверить все решения на таком тестовом наборе входных данных:
1 4
=A2+A3 =A1*A3 =A1/A2 'Surprise!
Последнюю ячейку можно исключить :)
Моё решение:
#Expr
Решение Ильина:
#OutOfRange #Reading #Reading #Reading
Решение vlad'а:
<parse error>
Так выглядит таблица:
A B C D ...
1 A1 B1 C1 D1
2 A2 B2 C2 D2
3 A3 B3 C3 D3
4 A4 B4 C4 D4
...
-
Предлагаю проверить все решения на таком тестовом наборе входных данных:
Возможно, Вы имели в виду вот это?
1 4
=B1+C1 =A1*C1 =A1/B1 'Surprise!
Моё решение:
#Cycle #Cycle #Cycle Surprise!
Решение Ильина:
#Cycle #Cycle #Cycle Surprise!
Решение vlad'а:
<cycle error> <cycle error> <cycle error> Surprise!
-
Хорошо, Илья, предложите более годную объективную метрику.
Алексей предлагал считать лексемы, но это из той же оперы.
Как ещё можно "измерить алгеброй гармонию"?
А что Вы вообще собрались мерять? Если решения чисто реализаторские (быстро реализуем как монолитный компонент), то задача достаточно проста, чтобы всё было примерно одинаково. Ну, зафиксировали количество строк, посравнивали, но удалять пробелы всякие, да ещё архиватором жать, как некоторые - маразм какой-то.
Если тренируемся в архитектуре, в декомпозиции на кубики, то критерии совсем не численные... Как это может развиваться дальше, какие схемы, ценные для решения задач данного класса, выявлены.
-
Объективные критерии -- размер и скорость (разработки программы и её выполнения).
Все остальные критерии субъективны, а потому и с их оценкой постоянно будут проблемы.
-
Хехе, господа, не торопитесь, а то, по сути, вы сейчас пытаетесь вычислить скорость зная только одну точку. :-)
PS. А сжатие это хороший метод измерения количества информации в решениях, и хороший критерий позволяющий оценить насколько близок исходник к содержимому /dev/random :-)
-
Сравнивая разные решения обратил внимание, что моя программа выдаёт лишние табуляции в конце каждой строки и лишнюю пустую строку после самой таблицы.
Возможно, это недопустимо, поэтому поправил пару строк в программе.
locs увеличился на одну строку: 215
-
Возможно, Вы имели в виду вот это?
1 4
=B1+C1 =A1*C1 =A1/B1 'Surprise!
Да, конечно. Вы правы :-[
-
Если в программе vlad'а удалить функцию test (и её вызов), то вот ещё -38 строк...
Это я уже сделал и учёл в подсчётах.
-
Предлагаю проверить все решения на таком тестовом наборе входных данных:
1 4
=B1+C1 =A1*C1 =A1/B1 'Surprise!
Моё решение:
#Cycle #Cycle #Cycle Surprise!
Решение Ильина:
#Cycle #Cycle #Cycle Surprise!
Решение vlad'а:
<cycle error> <cycle error> <cycle error> Surprise!
Единодушное решение. :)
Я хотел было "повякать" ( :)) на тему, что необходимость в решении системы из N уравнений с N неизвестными ещё не даёт оснований для того, чтобы объявлять об ошибке во входном наборе данных. Но что-то меня от этого удерживает. Наверное то, что суть задачи всё-таки была не в этом. Но формально я прав. :)
-
Решение vlad'а:
<cycle error> <cycle error> <cycle error> Surprise!
Вообще-то тут видно, что vlad сделай как минимум один fail -- невнимательно прочёл условия задачи:
- В случае любой ошибки вычисления формулы, вычисляемая ячейка должна содержать
слово-сообщение об ошибке, начинающееся с символа '#'. Используйте короткие,
ясные сообщения. Не надо предоставлять подробности об ошибках в выводе.
Сообщения об ошибках нужно помечать решёткой, а не заключаться в треугольные скобки...
-
Я хотел было "повякать" ( :)) на тему, что необходимость в решении системы из N уравнений с N неизвестными ещё не даёт оснований для того, чтобы объявлять об ошибке во входном наборе данных. Но что-то меня от этого удерживает. Наверное то, что суть задачи всё-таки была не в этом. Но формально я прав. :)
Справедливости ради должен заметить, что тот же самый Эксель тоже ругается на циклические ячейки в Вашем тесте.
-
Справедливости ради должен заметить, что тот же самый Эксель тоже ругается на циклические ячейки в Вашем тесте.
Да. И причина этого ясна. В общем случае решение исключительно сложное, если вообще возможно. И это скорее всего не то, что хочет пользователь.
По хорошему, в условии задачи должна быть строчка, что-то типа: "Циклические ссылки считать ошибкой". То есть данное замечание у меня относится не столько к предоставленным решениям, сколько к самой задаче.
-
По хорошему, в условии задачи должна быть строчка, что-то типа: "Циклические ссылки считать ошибкой". То есть данное замечание у меня относится не столько к предоставленным решениям, сколько к самой задаче.
По идее задачи, испытуемый должен был догадаться об этом самостоятельно...
-
По идее задачи, испытуемый должен был догадаться об этом самостоятельно...
Нет. У испытуемого просто не остаётся выбора. Иначе ему пришлось бы "убиться головой об стену". ;D
-
Я насчитал целых 4 решения - оберон-2, КП, хаскель, С++. Классно! :)
В джаббере я скидывал Алексею ссылки на кучу ещё решений, там были на яве, вроде, ещё на лиспе, на сях и с++ несколько, несколько вариантов на том же хаскелле, вариант на эрланге...
Ну так это... сюда их! :)
Вот с замером этой самой скорости на текущем размере таблицы 26*9 проблемы -- любая таблица будет расчитана за доли секунды.
Ограничений на размер формулы нет ;) A1*A2...
-
Какая-то метрия неинтересная началась, коллеги :) Как это бывает с производительностью. Признак нехорошего зуда в одном месте. Какая разница - + 100 строк, - 100 строк?
Согласен. Строки - неинтересно, особенно с учетом произвольного форматирования. Но вот порядок (100 или 10) - таки может быть показателен. Ну, и конечно, какие-нибудь другие метрики.
-
Если тренируемся в архитектуре, в декомпозиции на кубики, то критерии совсем не численные... Как это может развиваться дальше, какие схемы, ценные для решения задач данного класса, выявлены.
Я пытался подытожить в комментариях к моему решению (http://oberon.talk4fun.net/index.php?topic=42.msg1438#msg1438 (http://oberon.talk4fun.net/index.php?topic=42.msg1438#msg1438)), но никто не поддержал и не откомментировал свои. Могу еще дополнить:
- ничего нового лично для себя не встретил, комментарии даже некуда втыкать :)
-- ну разве вот с циклическими ссылками пришлось подумать так, чтобы было минималистично и неинтрузивно
- парсер выражений сделан на коленке, без привлечения какой-то теории на эту тему
-
Сообщения об ошибках нужно помечать решёткой, а не заключаться в треугольные скобки...
Поправил. Причем только в одном месте (форматирование ошибки). Считаю, что это плюс с точки зрения архитектуры и правильной декомпозиции ;)
-
Я насчитал целых 4 решения - оберон-2, КП, хаскель, С++. Классно! :)
В джаббере я скидывал Алексею ссылки на кучу ещё решений, там были на яве, вроде, ещё на лиспе, на сях и с++ несколько, несколько вариантов на том же хаскелле, вариант на эрланге...
Ну так это... сюда их! :)
С++
_winnie: http://www.everfall.com/paste/id.php?c9dn0t8ffx43
Alex Mizrahi: http://thesz.livejournal.com/288662.html
Си
Ivan A. Kosarev: http://unicals.com/download/excel.zip
Java
Anatoli Klassen: http://www.26th.net/public/development/SpreadSheet.java
Хаскелл
thesz: http://thesz.livejournal.com/281937.html
Булата Зиганьшин: http://www.haskell.org/haskellwiki/Ru/Problem_K
NotGonnaGetUs: http://nggu.livejournal.com/663.html
пара старых моих: http://geniepro.livejournal.com/2722.html
Ерланг
Гапертон: http://gaperton.livejournal.com/7229.html
Лисп
Alex Mizrahi: http://thesz.livejournal.com/289017.html
13-49: http://13-49-ru.blogspot.com/2011/03/blog-post_25.html
Nemerle
Kisloid: http://rsdn.ru/forum/decl/2742713.all.aspx
-
Поскольку здесь и на коре периодически наезжают на питон, то на питоне тоже сделаю, как только - так сразу.
-
Питон:
- никаких ужасных проблем с динамичской типизацией не встретилось - заработало как только прошли все юнит тесты из решения на C++
- ничего лишнего в синтаксисе, сахарок, приятно :)
- функциональщина вместо интерфейсов на каждый чих - тоже приятно :)
- скажи нет бесполезным объявлениям типов :)
- все есть в языке - импортировать пришлось только "sys" для stdin/stdout
P.S. Учитесь готовить :)
-
Примерно 230 строк без тестов и без разбиения на модули. Ну и где тут лаконичность? :-)
-
Примерно 230 строк без тестов и без разбиения на модули. Ну и где тут лаконичность? :-)
Можно, конечно, и меньше - но в жертву архитектуре, будущему разбиению на модули и т.д.
-
Ну, то есть получилось жирнее чем на хаскеле разбитом на модули и переписанном в пром. стиле :-) При том, что в хаскеле строгая статическая типизация как бэ.
-
Ну, то есть получилось жирнее чем на хаскеле разбитом на модули и переписанном в пром. стиле :-) При том, что в хаскеле строгая статическая типизация как бэ.
Кто-то обещал, что будет короче, чем на хаскеле? :) Ну а статическая типизация вэтой задаче пока себя никак не показала. Судя по тому, что на питон переписалось без проблем.
-
Кто-то обещал, что будет короче, чем на хаскеле? :) Ну а статическая типизация вэтой задаче пока себя никак не показала. Судя по тому, что на питон переписалось без проблем.
Я думал, что статическая типизация показала бы себя при переписывании С Питона, а не НА него. Или я чего-то не догнал?
Кроме того, где решение Ильи Ермакова? Массы жаждут! (В моём лице.)
-
Ну а статическая типизация вэтой задаче пока себя никак не показала. Судя по тому, что на питон переписалось без проблем.
Когда я рефаткорил свой вариант ( http://geniepro.livejournal.com/2722.html ), я там не просто на модули разбил, но ещё и переделки некоторые сделал:
во-первых, заставил компилятор молчать при опции -Wall, а то он ругался, что некоторые переменные не используются, а некоторые скрывают собой другие с такими же именами из предыдущей области видимости),
выделил в отдельную функцию кусок, проверяющий зацикливания в формулах,
удалил в принципе ненужный в этой задаче самопальный класс типов для расчётов таблицы и её элементов, заменив три её инстанса на три простые функции.
При этом компилятор указывал, где я в этих переделках накосячил, и когда он, компилятор, окончательно всё скомпилировал без сообщений об ошибках, то программа чётко отработала тестовые примеры -- отлаживать не пришлось.
Так что статическая типизация даже на такой задачке вполне себе рулит!
-
Кто-то обещал, что будет короче, чем на хаскеле? :) Ну а статическая типизация вэтой задаче пока себя никак не показала. Судя по тому, что на питон переписалось без проблем.
Я думал, что статическая типизация показала бы себя при переписывании С Питона, а не НА него. Или я чего-то не догнал?
Не показала в том смысле, что решение легко "легло" на динамический язык, без долгого цикла отладки и без написания дополнительных тестов (которые и так были написаны для статической версии). Т.е., решение изначально могло быть сделано на динамическом языке и, скорее всего, быстрее (просто потому, что писанины меньше). Определенно, конечно, нельзя сказать, потому что это было переписывание, а не разработка с нуля.
-
При этом компилятор указывал, где я в этих переделках накосячил, и когда он, компилятор, окончательно всё скомпилировал без сообщений об ошибках, то программа чётко отработала тестовые примеры -- отлаживать не пришлось.
Так что статическая типизация даже на такой задачке вполне себе рулит!
Не, вы не догоняете :) Статика рулит, когда ошибки компиляции исправить быстрее, чем поднять тесты. И если вы думаете, что компилить всегда быстрее - то, возможно, вы просто не умеете писать тесты :)
Нелюбовь оберонщиков к динамическим языкам (и даже противопоставления, как у info21) мне вообще не понятна и объясняется только парадоксом Блаба. Оберон при статической типизации лишен какой либо арифметики типов. Выразить что-то с помощью типов или нельзя или черезчур многословно. Компилятор может проверить крайне мало. Даже при работе с каким-нибудь банальным обобщенным контейнером - сразу скатываешься до уровня динамического языка, ошибки ловятся только в рантайме. При этом куча ненужной писанины в виде приведения типов...
-
Кто-то обещал, что будет короче, чем на хаскеле? :) Ну а статическая типизация вэтой задаче пока себя никак не показала. Судя по тому, что на питон переписалось без проблем.
Я думал, что статическая типизация показала бы себя при переписывании С Питона, а не НА него. Или я чего-то не догнал?
Не показала в том смысле, что решение легко "легло" на динамический язык, без долгого цикла отладки и без написания дополнительных тестов (которые и так были написаны для статической версии). Т.е., решение изначально могло быть сделано на динамическом языке и, скорее всего, быстрее (просто потому, что писанины меньше). Определенно, конечно, нельзя сказать, потому что это было переписывание, а не разработка с нуля.
Реализация чисто алгоритмов (и, тем более, переписывания оных) одинаково просто на динамической и на статической типизации, пожалуй с первой еще проще, ибо никто не мешается под ногами. Статическая (а тем более строгая статическая) типизация же накладывает ограничения на реализацию алгоритма, а не снимает их.
Собственно даже на каком-нибудь языке с нестрогой динамической типизацией (у питона строгая динамическая, кстати) подобная задача была бы написана или переписана также легко. А вот если взять питоноверсию и попробовать её переписать на языке со строгой статической типизацией, тогда вот вылезут грабли. Желающие могут попробовать её переписать на хаскеле, ну, или, хотя бы на Аде.
-
Собственно даже на каком-нибудь языке с нестрогой динамической типизацией (у питона строгая динамическая, кстати) подобная задача была бы написана или переписана также легко. А вот если взять питоноверсию и попробовать её переписать на языке со строгой статической типизацией, тогда вот вылезут грабли. Желающие могут попробовать её переписать на хаскеле, ну, или, хотя бы на Аде.
Согласен. Переписать с динамики на статику будет скорее всего сложнее. И что это доказывает? :) Что статика круче? :) Тогда оберон, конечно, рулит - замахаешься на него переписывать с чего-то уровнем выше сей ;) Впрочем, с труЪ сей тоже замахаешься - сплошной SYSTEM будет.
-
Нелюбовь оберонщиков к динамическим языкам (и даже противопоставления, как у info21) мне вообще не понятна и объясняется только парадоксом Блаба. Оберон при статической типизации лишен какой либо арифметики типов.
Вы можете программировать на Питоне, не составляя тестовые наборы? Т.е. можете получить приемлемое качество компонента, не составив на него тесты?
Я не говорю, что правильно программировать без тестов, неплохо ими подкреплять процесс, но я обычно не прибегаю к модульным тестам вообще (если бы делал вычислительно-алгоритмического характера задачи, то прибегал бы), я и так бываю уверен в качестве компонента. Только интеграционное тестирование. (Разумеется, если бы пришлось решать критичную по надёжности задачу, то нужно было бы перестраховываться любыми доступными способами).
Теперь представьте, перехожу я на динамический язык. (Мне не надо этого представлять, ряд вещей на PHP и JS я совсем недавно писал, но боролся с их закидонами осторожностью и многократными внимательными перепроверками кода, там надо было не очень объёмные, но важные компоненты написать для других разработчиков).
Так вот, перехожу я. Положим первый вариант программы я составлю, и даже забью особо на тесты. Но затем я натолкнусь на дамоклов меч этой динамики - при рефакторинге, при малейшем изменении сигнатур процедур или чего ещё я буду долго биться задницей об стену. А если учесть, что даже при разработке первого варианта я пару раз люблю порефакторить... То биться буду с самого начала.
Те, кто работает в стиле с тестами, те скажут, "а у нас вместо компилятора - тесты". Но у меня-то нет тестовых наборов специальных... Это значит, что я должен буду их завести и привыкнуть к такому стилю. Для меня это будет избыточной работой. Я привык тратить больше времени, чем другие, на написание (чтобы сразу получать правильную программу) и вычитку кода, и ещё буду тратить время на тесты...
-
А вот если взять питоноверсию и попробовать её переписать на языке со строгой статической типизацией, тогда вот вылезут грабли. Желающие могут попробовать её переписать на хаскеле, ну, или, хотя бы на Аде.
В хаскелле ООП-классов же нету, просто так переписать не получится. Код совершенно другим выйдет...
-
Нелюбовь оберонщиков к динамическим языкам (и даже противопоставления, как у info21) мне вообще не понятна и объясняется только парадоксом Блаба. Оберон при статической типизации лишен какой либо арифметики типов.
Вы можете программировать на Питоне, не составляя тестовые наборы? Т.е. можете получить приемлемое качество компонента, не составив на него тесты?
Я вам уже писал как-то... Без тестов приемлемое качество вы никогда не получите. Даже на волшебном обероне (как же к слову не сказать про обилие "дурацкких" ошибок в виртовских книжках). Просто статические языки позволяют вам намного дольше жить "в кредит" с иллюзией, что вам все проверит компилятор, а ошибок в логике вы не делаете. Такой подход даже работает в случае, когда вам удается "спихнуть" проект до наступления часа Х, когда сложность поведения (даже не системы в целом, а отдельных компонент) такова, что компилятор вам уже никак не помогает, а как это должно работать на самом деле никто не знает/не помнит.
Да, на динамическом языке вам придется писать тесты сразу и много. С одной стороны. С другой стороны - писать и споровождать их легче. Плюс - обилие тестов резко повышает качество "компонентности" системы. Да-да, не "правильная модульность" оберона сама по сбе, а юнит тесты реально заставлют правильно декомпозировать.
Я не говорю, что правильно программировать без тестов, неплохо ими подкреплять процесс,
Вот тут принципиальная ошибка. Не подкреплять. Подкреплять вы можете комментариями, документацией и красивыми графиками, если время останется :) Тесты - первичны. Они так же первичны, как дизайн и архитектура.
Теперь представьте, перехожу я на динамический язык. (Мне не надо этого представлять, ряд вещей на PHP и JS я совсем недавно писал, но боролся с их закидонами осторожностью и многократными внимательными перепроверками кода, там надо было не очень объёмные, но важные компоненты написать для других разработчиков).
Так вот, перехожу я. Положим первый вариант программы я составлю, и даже забью особо на тесты.
Дальше можно не читать... понятно чем оно кончится ;)
Но затем я натолкнусь на дамоклов меч этой динамики - при рефакторинге, при малейшем изменении сигнатур процедур или чего ещё я буду долго биться задницей об стену. А если учесть, что даже при разработке первого варианта я пару раз люблю порефакторить... То биться буду с самого начала.
Рефакторинг - это не только изменение сигнатур функций. Вот я работаю с базой кода, которой больше 10 лет. Статический язык. Невозможно ничего отрефакторить, пока досканально не разберешься, что делает компонента и зачем. На эти разбирательства уходят дни без единой строчки нового кода. И не надо мне пытаться рассказать, что если бы это был оберон, а не С++, то было бы быстрее (скорее наоборот). Да, если бы это был динамический язык - то были бы не дни, а недели, тут я согласен :) Но речь не об этом. А о том, что если бы оно было с вменяемыми тестами, то можно было бы просто брать и спокойно кромсать компоненту в свете нового понимания ее правильной работы, без риска, что потом у пользователя отвалится его самый важный юзкейс.
Те, кто работает в стиле с тестами, те скажут, "а у нас вместо компилятора - тесты". Но у меня-то нет тестовых наборов специальных... Это значит, что я должен буду их завести и привыкнуть к такому стилю. Для меня это будет избыточной работой. Я привык тратить больше времени, чем другие, на написание (чтобы сразу получать правильную программу) и вычитку кода, и ещё буду тратить время на тесты...
Ужос. Я вам это процитирую лет так через 5 :)
-
Влад, ну я работаю больше 10 лет, знаешь...
Речь-то идёт об каждом отдельно взятом компоненте. Достаточно обособленно спроектированном и разработанном. Компонент - это 5-10 тыс. строк. Такой компонент можно и нужно разрабатывать надёжно даже в отсутствие тестовых наборов. Остаются небольшие ляпы, но для некритичной системы они сами вылезают и очень быстро (на ассертах тех же) при прогоне на интеграции.
Что изменится за 5, 10 лет? У меня будет 100, 200... компонентов, каждый всё тем же объёмом 5-10 тыс. строк, каждый всё также работает.
А реализовывается тестирование на каждую систему, каждый заказ, идущий в эксплуатацию, разумеется, там это необходимо (без этого можно обходиться только в экстренных случаях, но потом это и правда выходит боком). И такое тестирование - не задача для разработчика компонентов, и не для меня, как архитектора. Есть инженеры по качеству, это их работа. Я эту работу уважаю, но не сильно разбираюсь - не моё :) У меня вот ученик мой бывший и студент, сейчас в Калуге работает на этой должности, над системой для британской биржи какой-то по ценным металлам... Много чего интересного рассказывает :) Ещё одногруппник тоже, тот в Бишкеке по тестированию билинга Мегафона работал два года. Дотошные ребята, молодцы, затестируют вусмерть :)
-
Кстати, вот в этом году много примеров разбираю разных со студентами, на проекторе пишем прямо. Размеры примеров 700-2000 строк, около того (1-4 модуля).
И часто бывает, что всё работает верно сразу после написания. Ну либо мгновенно обнаруживаемые ляпы, на ассертах или NIL (что-то не соединили). Не было случая, чтобы надо было возиться с отладкой, если программа хорошо структурирована (в смысле разбиения на процедурки).
И я стараюсь, чтобы ребята запоминали крепко процесс вот такой работы - когда ты запускаешь программу (= компонент системы), будучи уже уверен в том, что она верна.
-
Возможно, многое решает привычки-настрой. Если человек настроен на отладку, он будет работать в режиме спринтера - составляем, составляем, не думаем об ошибках. Не перечитываем.
Если работать с противоположной привычкой, то больше 2/3 времени сидишь и листаешь свой же код, напишешь - перечитаешь сто раз. Может, у меня характер такой - я люблю неспешно строить, а не бежать за строчками.
-
Влад, ну я работаю больше 10 лет, знаешь...
Извиняюсь за возможно некорректное вмешательство, но, однако, получается что ты работаешь как минимум с 14ти лет программистом и около того.
-
Влад, ну я работаю больше 10 лет, знаешь...
Это не то. Приходилось ли вам рефакторить чужой код, которому 10+ лет? Еще и написанный не в вашем стиле (я не про форматирование)? Код, кторый вы не имеет права "сломать"? Код, у которого не два выхода "сработало/не сработало", а нечто о чем вы имеет общее представление. Код, который вмурован зависимостями в другой код? Не выкидывать и переписывать нафиг, а рефакторить? Еще раз замечу, что это был не плохой код (10 лет назад) и писан не идиотами. И с зависимостями у него 10 лет назад было все относительно хорошо. Просто за 10 лет он был столько раз "захэкан", что превратился в полное говно. А захэкан он был из самых добрых побуждений - чтобы с меньшей вероятностью что-то сломать. Потому что сделать "смелый" рефакторинг слишком дорого - тестов нет, фиг знает какие сценарии использования будут упущены.
Речь-то идёт об каждом отдельно взятом компоненте. Достаточно обособленно спроектированном и разработанном. Компонент - это 5-10 тыс. строк. Такой компонент можно и нужно разрабатывать надёжно даже в отсутствие тестовых наборов. Остаются небольшие ляпы, но для некритичной системы они сами вылезают и очень быстро (на ассертах тех же) при прогоне на интеграции.
Блин. Да не можете вы его взять и прогнать. Потому что там мильён сценариев. Потому что, например, вам среду окружения надо будет сетапить целый день (специфика работы с каким-нибудь файловым сервером под Mac OSX). Или потому что у вас просто нет железки, с которой он работает.
-
Кстати, вот в этом году много примеров разбираю разных со студентами, на проекторе пишем прямо. Размеры примеров 700-2000 строк, около того (1-4 модуля).
И часто бывает, что всё работает верно сразу после написания.
И чего? В момент написания - ну вообще не парит. Можно писать на питоне и без тестов. Быстро. Парит потом, когда уже поздно что-то делать, можно только плакать и грызть кактус.
-
Возможно, многое решает привычки-настрой. Если человек настроен на отладку, он будет работать в режиме спринтера - составляем, составляем, не думаем об ошибках. Не перечитываем.
ешно строить, а не бежать за строчками.
Да, да. Я вот пишу и не не знаю - заработает или нет и какие будут ошибки. Поэтому приходится писать тесты. А вам это не грозит, потому что вы думаете. Смешно...
-
Влад, ну ёханый бабай, если компонент ПРАВИЛЕН, если он вычитан перекрёстно несколькими людьми и не раз (потому что написан настолько структурированно, чтобы это можно было делать), то какие с этим компонентом будут проблемы? Рефакторить "хаками" реализацию отдельного модуля у нас тоже не принято, отдельная реализация какого-нибудь ABSTRACT-типа на пару тыщ строк просто переписывается с нуля, так, как нужно под новые требования...
Это не самоуверенность, это просто наблюдения из практики - если поставить целью выверять код аудитом до тестирования и заточить весь стиль работы группы разработчиков под это, то результаты удивляют. Даже нас самих.
-
Хотя, впрочем, я выше подчёркивал, что я не обобщаю подход на какие-то вычислительного характера задачи, и, кстати, на бизнес-логику (где идёт действительно взрыв сценариев). Я говорю о кубиках-компонентах (по стилю разработки это - системное программирование, в общем). А бизнес-логика как раз возникает поверх кубиков, на верхнем уровне, как интегрирующий слой. "Оркестровка", как принято это называть. Вот ей инженеры по качеству и должны заниматься, разрабатывать тесты, как положено.
-
На самом деле, характер кода неплохо характеризуется критерием разветвлённости (числом путей, за счёт IF-ов).
Кстати, эта мера чётко растёт от системного уровня к прикладному. И подходы, соответственно, тоже должны различаться.
С другой стороны, правильно организовывать систему надо так, чтобы все сценарии, вот это принятие решений уходило наверх, на интегрирующий уровень. Каждый компонент должен включать в себя как можно меньше принятий решений, вот этих сценариев работы. Вместо параметризации компонентное программирование предполагает вариативность реализации.
Возникает желание сделать компонент X с кучей конфигурационных параметров? Делаем одну абстракцию и несколько разных её реализаций. Вместо одной настраиваемой. (Правда, код в реализациях будет процентов на 30 повторяться, ну и что? Это же сокрытое внутреннее устройство, оно один раз написано (по аналогии или частично даже копипастом) и годами потом используется...)
Года два назад сформулировал для себя принцип: кубики тупые и делают конкретную работу, принимает решение надсистема.
-
На самом деле, характер кода неплохо характеризуется критерием разветвлённости (числом путей, за счёт IF-ов).
Кстати, эта мера чётко растёт от системного уровня к прикладному. И подходы, соответственно, тоже должны различаться.
С другой стороны, правильно организовывать систему надо так, чтобы все сценарии, вот это принятие решений уходило наверх, на интегрирующий уровень. Каждый компонент должен включать в себя как можно меньше принятий решений, вот этих сценариев работы. Вместо параметризации компонентное программирование предполагает вариативность реализации.
Возникает желание сделать компонент X с кучей конфигурационных параметров? Делаем одну абстракцию и несколько разных её реализаций. Вместо одной настраиваемой. (Правда, код в реализациях будет процентов на 30 повторяться, ну и что? Это же сокрытое внутреннее устройство, оно один раз написано (по аналогии или частично даже копипастом) и годами потом используется...)
Года два назад сформулировал для себя принцип: кубики тупые и делают конкретную работу, принимает решение надсистема.
Вы описываете в точности мое представление о правильной разработке. Как это не странно :) Тем не менее. Такой подход не исключает тестов. Тесты - его обеспечивают. Как соблюдать такой "кубиковый" подход без написания тестов - я не представляю. Одного желания мало, особенно для больших объемов и многих участников. Нужно конкретное техническое контролирующее средство. Пока кроме тестов на эту роль никого не видно.
-
Я не против тестов, поймите меня правильно. Я за них. Добавить ещё и тесты. Особенно в большом коллективе, это наверняка будет просто необходимо.
Опять же, есть абстракция и много реализаций. Приложением к спецификации как раз и должен быть, по-хорошему, набор тестов, который позволяет проверить любую реализацию на соответствие спецификации.
Я говорю о том, что надо иметь процесс, который и без систематического тестирования компонентов даёт в небольшом коллективе их высокое качество, а если к нему добавить ещё и тесты, то это вообще будет экстра-класс :)
-
А увидим ли мы обещанное решение на КП/ББ в открытом доступе с описаловом?
-
А увидим ли мы решение на 07 (можно без описалова) :)
-
А увидим ли мы решение на 07 (можно без описалова) :)
Решение на 07 осложняется отсутствием элементарной стандартной библиотеки. Вот сейчас пишу как раз неё :-)
-
Пока занят сделать описалово, 12-го пройдут у нас в институте Поликарповские чтения, тогда займусь. Помню, в плане стоит.
-
Пока занят сделать описалово
Бог с ним, с описанием. Исходников было бы достаточно. Они уже опубликованы или нет?
-
Пока занят сделать описалово
Бог с ним, с описанием. Исходников было бы достаточно. Они уже опубликованы или нет?
Они у меня в загашнике в формате PDF :-)
-
На этом форуме плохо видно пришедшие личные сообщения. valexey, я вам уже несколько дней как написал.
-
Ой, да, действительно.
-
Ещё одно решение (на хаскелле) от ЖЖ-юзера Yan Tayga
http://yantayga.livejournal.com/28097.html
PS. Де обещанные решения на КП и О7??? :P
-
<Истерично> НУ И ДЕ???? </Истерично>
-
ну так и де?
;D ;D ;D
-
ну так и де?
;D ;D ;D
У кого надо (с) :)
-
Откопал решение Ильи Ермакова (оно вроде бы не законченое/не допиленное, но тем не менее пусть будет, для коллекции).
-
Крошечный Excel на чистом JavaScript (30 строк кода) (http://habrahabr.ru/post/202304/)