Оберон-технология: особенности и перспективы |
Тематика обсуждения: Оберон-технология. Особенности, перспективы, практическое применение.
Всего в теме 6256 сообщений
Добавить свое сообщение
Отслеживать это обсуждение Обсуждение из раздела Школа ОБЕРОНА
№ 3336 19-03-2007 12:53 | |
Ответ на »сообщение 3323« (slava)
___________________________
Перефразирую: можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?
Насколько я знаком со Scheme - это не возможно.
Вас дезинформировали :))
Прежде всего скорость того или иного алгоритма зависит не от того функциональный или императивный язык, а от того статический он или динамический. Естественно динамические языки, будт то функциональный лисп, scheme или императивные питон, руби, javascript будут медленнее нежели статические языки будь то императивные паскаль, си или функциональные хаскель, clean
Поэтому например в лиспе, когда нужна скорость в программу вставляются описания типов, что кстати приводит скорость программы как раз на уровень си.
Далее, Сергей Перовский совершенно верно заметил что функциональные языки не медленнее, они больше памяти могут жрать, это да. Но по скорости примерно в тех же пределах что и императивные. Различные флуктуации в результатах уже зависят от конкретной реализации компилятора-среды, а не от того функциональный язык или императивный. В самом семействе императивных языков, вы можете видеть довольно большой разброс по скоростям.
Далее, Слава, хотите получить осмысленный ответ, задавайте осмысленный вопрос.
А то как в книге Дугласа "Автостопом по галактике", на вопрос в чем смысл жизни получите ответ "42" :))
Серьезно, ну что это за вопрос "можно ли". Отвечаю - можно. Вам стало легче ?
Вы узнали из этого ответа КАК и ПОЧЕМУ ?
№ 3335 19-03-2007 12:52 | |
Ответ на »сообщение 3333«
Как там поют Братья Гримм? "Нам это пофигу, пофигу..." :о))
Класная песенка.
Что касается сортировки. В худшем случае этот вопрос будет обойдён, и Вам не придётся её делать самому - просто возьмите готовую функцию из стандартной библиотеки. Неважно, как она реализована на нижнем уровне - главное, что бы она обеспечивала чистый интерфейс...
В том то и проблемка, сортировка взята как пример, а не как цель. Ну не все функции реализованы в библиотеках. Да и вообще если сравнивать библиотеки - наверняка Java всех "побьет". :)))
Короче, хотелось бы понять как именно реализовывать алгоритмы на самом чистом ФЯ.
А для списков лучшим алгоритмом является merge-sort.
Да уж догодался. Т.е. merge-sort удается реализовать достойно, но если некий алгоритм не списко- (последовательно-) подобный, то придется над ним долго "извращаться", что бы получить нужную асимптотику. Например, над QuickSort - чуть-чуть, а над HeapSort наверняка побольше. Интересно, останется чего-то от оригинального алгоритма после таких преобразований?
Сортировки взяты для примера, а не как цель.
Знаете, функциональных программистов на этом форуме довольно мало - по пальцам одной руки пересчитать можно...
Ха, я вначале задал этот вопрос в соседнем форуме...
Непонятно, с чего бы это? Scheme - гибридный язык, и в нём-то как раз легко делать "грязные" деструктивные процедуры сортировки массивов/списков... Попробуйте процедуру mergesort из библиотеки, стандартной для PLT Scheme.
Меня интересует чистые функциональные свойства. От "грязи" потом долго "отмываться". Библиотеки уже коментировал.
№ 3334 19-03-2007 12:28 | |
Ответ на »сообщение 3326« (Руслан Богатырев)
___________________________
В этом существенный плюс ФП, который, как и любой плюс, в другом аспекте становится минусом.
Ну что тут скажешь? У каждой медали есть обратная сторона, и даже на Солнце есть пятна...
№ 3333 19-03-2007 12:28 | |
Ответ на »сообщение 3323« (slava)
___________________________
Не хочу быть назойливым, возвращаясь к моему первому вопросу о производительности. Но "гармоничность" ФЯ построена в ущерб производительности.
Как там поют Братья Гримм?
"Нам это пофигу, пофигу..." :о))
(Ну вот, щас опять окажется, что и эту песенку я переврал... :о)))
Перефразирую: можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?
Что касается сортировки. В худшем случае этот вопрос будет обойдён, и Вам не придётся её делать самому - просто возьмите готовую функцию из стандартной библиотеки. Неважно, как она реализована на нижнем уровне - главное, что бы она обеспечивала чистый интерфейс...
Сортировка массивов в Clean при использовании "уникальных" классов типов работает так же быстро, как и в императивных языках.
А для списков лучшим алгоритмом является merge-sort.
Мне странно, что вместо ответа, я получаю игнорирование или якобы непонимание.
Знаете, функциональных программистов на этом форуме довольно мало - по пальцам одной руки пересчитать можно. Поэтому они (мы) и не успевают ответить на Ваш вопрос - до предыдущих вопросов никак добраться не можем... :о(
Насколько я знаком со Scheme - это не возможно.
Непонятно, с чего бы это? Scheme - гибридный язык, и в нём-то как раз легко делать "грязные" деструктивные процедуры сортировки массивов/списков... Попробуйте процедуру mergesort из библиотеки, стандартной для PLT Scheme.
№ 3332 19-03-2007 12:15 | |
Ответ на »сообщение 3329« (Сергей Перовский)
Конечно можно. Дело не в скорости. Есть другая характеристика - количество требуемой памяти... Будет ли сборка мусора достаточно "умной", чтобы освобождать память по мере работы функции мне не понятно.
Т.е. иногда можно реализовать алгоритм на ФЯ, оставаясь в тех же границах (асимптотически) по времени, что и на ИЯ, но для этого нужно алгоритм преобразовать. Например дополнительные пробежки по списку. И если повезло и удалось отстоять асимптотику для конктретной задачи (например MergeSort), то это вообщем это совсем не очевидно (например в HeapSort).
Складывается впечатление что, что бы чего-то запрограммировать на ФЯ, необходимо изменить известный алгоритм до неузнаваемости. Т.е. да - многие простые вещи пишутся просто, но большенство других более сложных вещей...
№ 3331 19-03-2007 11:59 | |
№ 3330 19-03-2007 09:09 | |
Ответ на »сообщение 3328« (Руслан Богатырев)
___________________________
Это легко проверяется. Берется набор олимпиадных задач. Даются решения на КП. Смотрим, что конкретно там пользуется. Затем выясняем, насколько обоснованно.
Можно, кстати, пойти и по другому пути. Модификаторы ООП и связанные процедуры не имеют преимуществ перед классическим Обероном на задачах:
1. Где нет повышенной нагрузки на software engineering
2. Где на все решение (от прочтения постановки задачи до конечного текста на языке) отводится не более часа.
Из обсуждаемой тройки остается расширение типа. Расширение типа было инициировано:
1. Желанием заменить "нехорошие" вариантные записи (предложенные Хоаром и включенные Виртом в Паскаль, а затем и в Модулу-2). Но они в олимпиадных задачах не имеют места быть.
2. Желанием обеспечить простое средство развития (построения иерархии комбинированных типов). Чтобы строить иерархию, надо успеть получить конкретику и потом ее успеть обобщить. И все это за считанные минуты?
Для олимпиадных задач из пост-паскалевских языков требуется только подмножество классической Модулы-2 (причем без локальных модулей, без средств низкоуровневого программирования, без механизма сопрограмм). Даже модульное программирование здесь работать практически не будет (нечего декомпозировать за такое время и для задач такого масштаба).
Что еще? Открытые массивы Оберона? Готов согласиться, что это может быть задействовано. Хотя открытые массивы Модулы-2 (как формальные параметры) вполне достаточны.
№ 3329 19-03-2007 08:55 | |
Ответ на »сообщение 3323« (slava)
___________________________
>>>Можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?
Конечно можно. Дело не в скорости. Есть другая характеристика - количество требуемой памяти.
Сортировка пузырьком имеет сложность О(N^2) и умещается в N+1 памяти.
Сортировка слиянием имеет сложность О(N log N) и требует 1,5*N памяти.
А вот его реализация в ФЯ по моим оценкам потребует N^2 log N памяти, что может оказаться критичным. Будет ли сборка мусора достаточно "умной", чтобы освобождать память по мере работы функции мне не понятно.
№ 3328 19-03-2007 08:54 | |
Ответ на »сообщение 3327« (info21)
___________________________
Успевают.
Традиция программирования, представленная в типичных учебниках, идет еще от фортрана-алгола...
Это легко проверяется. Берется набор олимпиадных задач. Даются решения на КП. Смотрим, что конкретно там пользуется. Затем выясняем, насколько обоснованно.
№ 3327 19-03-2007 08:34 | |
Ответ на »сообщение 3318« (Руслан Богатырев)
___________________________
Если Вы хотите сказать, что на задачах мелкого масштаба (каковыми являются агоритмические олимпиадные задачи) существенную роль играет расширение типа, связанные процедуры или модификаторы ООП, то позвольте не поверить. Они там просто не успевают "раскочегариться".
Успевают.
Традиция программирования, представленная в типичных учебниках, идет еще от фортрана-алгола...
Добавить свое сообщение
Отслеживать это обсуждение
Дополнительная навигация: |
|