Ответ на »сообщение 3323« (slava)
___________________________

Перефразирую: можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?
Насколько я знаком со Scheme - это не возможно.

Вас дезинформировали :))
Прежде всего скорость того или иного алгоритма зависит не от того функциональный или императивный язык, а от того статический он или динамический. Естественно динамические языки, будт то функциональный лисп, scheme или императивные питон, руби, javascript будут медленнее нежели статические языки будь то императивные паскаль, си или функциональные хаскель, clean

Поэтому например в лиспе, когда нужна скорость в программу вставляются описания типов, что кстати приводит скорость программы как раз на уровень си.

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

Далее, Слава, хотите получить осмысленный ответ, задавайте осмысленный вопрос.
А то как в книге Дугласа "Автостопом по галактике", на вопрос в чем смысл жизни получите ответ "42" :))

Серьезно, ну что это за вопрос "можно ли". Отвечаю - можно. Вам стало легче ?
Вы узнали из этого ответа КАК и ПОЧЕМУ ?

Ответ на »сообщение 3333«

Как там поют Братья Гримм? "Нам это пофигу, пофигу..." :о))

Класная песенка.

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

В том то и проблемка, сортировка взята как пример, а не как цель. Ну не все функции реализованы в библиотеках. Да и вообще если сравнивать библиотеки - наверняка Java всех "побьет". :)))

Короче, хотелось бы понять как именно реализовывать алгоритмы на самом чистом ФЯ.

А для списков лучшим алгоритмом является merge-sort.

Да уж догодался. Т.е. merge-sort удается реализовать достойно, но если некий алгоритм не списко- (последовательно-) подобный, то придется над ним долго "извращаться", что бы получить нужную асимптотику. Например, над QuickSort - чуть-чуть, а над HeapSort наверняка побольше. Интересно, останется чего-то от оригинального алгоритма после таких преобразований?

Сортировки взяты для примера, а не как цель.

Знаете, функциональных программистов на этом форуме довольно мало - по пальцам одной руки пересчитать можно...

Ха, я вначале задал этот вопрос в соседнем форуме...

Непонятно, с чего бы это? Scheme - гибридный язык, и в нём-то как раз легко делать "грязные" деструктивные процедуры сортировки массивов/списков... Попробуйте процедуру mergesort из библиотеки, стандартной для PLT Scheme.

Меня интересует чистые функциональные свойства. От "грязи" потом долго "отмываться". Библиотеки уже коментировал.

Ответ на »сообщение 3326« (Руслан Богатырев)
___________________________

В этом существенный плюс ФП, который, как и любой плюс, в другом аспекте становится минусом.

Ну что тут скажешь? У каждой медали есть обратная сторона, и даже на Солнце есть пятна...

Ответ на »сообщение 3323« (slava)
___________________________

Не хочу быть назойливым, возвращаясь к моему первому вопросу о производительности. Но "гармоничность" ФЯ построена в ущерб производительности.

Как там поют Братья Гримм?

"Нам это пофигу, пофигу..." :о))
(Ну вот, щас опять окажется, что и эту песенку я переврал... :о)))


Перефразирую: можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?

Что касается сортировки. В худшем случае этот вопрос будет обойдён, и Вам не придётся её делать самому - просто возьмите готовую функцию из стандартной библиотеки. Неважно, как она реализована на нижнем уровне - главное, что бы она обеспечивала чистый интерфейс...
Сортировка массивов в Clean при использовании "уникальных" классов типов работает так же быстро, как и в императивных языках.
А для списков лучшим алгоритмом является merge-sort.

Мне странно, что вместо ответа, я получаю игнорирование или якобы непонимание.

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

Насколько я знаком со Scheme - это не возможно.

Непонятно, с чего бы это? Scheme - гибридный язык, и в нём-то как раз легко делать "грязные" деструктивные процедуры сортировки массивов/списков... Попробуйте процедуру mergesort из библиотеки, стандартной для PLT Scheme.

Ответ на »сообщение 3329« (Сергей Перовский)

Конечно можно. Дело не в скорости. Есть другая характеристика - количество требуемой памяти... Будет ли сборка мусора достаточно "умной", чтобы освобождать память по мере работы функции мне не понятно.

Т.е. иногда можно реализовать алгоритм на ФЯ, оставаясь в тех же границах (асимптотически) по времени, что и на ИЯ, но для этого нужно алгоритм преобразовать. Например дополнительные пробежки по списку. И если повезло и удалось отстоять асимптотику для конктретной задачи (например MergeSort), то это вообщем это совсем не очевидно (например в HeapSort).

Складывается впечатление что, что бы чего-то запрограммировать на ФЯ, необходимо изменить известный алгоритм до неузнаваемости. Т.е. да - многие простые вещи пишутся просто, но большенство других более сложных вещей...

»сообщение 3330«

Автоматическая сборка мусора.

Ответ на »сообщение 3328« (Руслан Богатырев)
___________________________

Это легко проверяется. Берется набор олимпиадных задач. Даются решения на КП. Смотрим, что конкретно там пользуется. Затем выясняем, насколько обоснованно.

Можно, кстати, пойти и по другому пути. Модификаторы ООП и связанные процедуры не имеют преимуществ перед классическим Обероном на задачах:
1. Где нет повышенной нагрузки на software engineering
2. Где на все решение (от прочтения постановки задачи до конечного текста на языке) отводится не более часа.

Из обсуждаемой тройки остается расширение типа. Расширение типа было инициировано:
1. Желанием заменить "нехорошие" вариантные записи (предложенные Хоаром и включенные Виртом в Паскаль, а затем и в Модулу-2). Но они в олимпиадных задачах не имеют места быть.
2. Желанием обеспечить простое средство развития (построения иерархии комбинированных типов). Чтобы строить иерархию, надо успеть получить конкретику и потом ее успеть обобщить. И все это за считанные минуты?

Для олимпиадных задач из пост-паскалевских языков требуется только подмножество классической Модулы-2 (причем без локальных модулей, без средств низкоуровневого программирования, без механизма сопрограмм). Даже модульное программирование здесь работать практически не будет (нечего декомпозировать за такое время и для задач такого масштаба).

Что еще? Открытые массивы Оберона? Готов согласиться, что это может быть задействовано. Хотя открытые массивы Модулы-2 (как формальные параметры) вполне достаточны.

Ответ на »сообщение 3323« (slava)
___________________________
>>>Можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?
Конечно можно. Дело не в скорости. Есть другая характеристика - количество требуемой памяти.
Сортировка пузырьком имеет сложность О(N^2) и умещается в N+1 памяти.
Сортировка слиянием имеет сложность О(N log N) и требует 1,5*N памяти.
А вот его реализация в ФЯ по моим оценкам потребует N^2 log N памяти, что может оказаться критичным. Будет ли сборка мусора достаточно "умной", чтобы освобождать память по мере работы функции мне не понятно.

Ответ на »сообщение 3327« (info21)
___________________________

Успевают.
Традиция программирования, представленная в типичных учебниках, идет еще от фортрана-алгола...

Это легко проверяется. Берется набор олимпиадных задач. Даются решения на КП. Смотрим, что конкретно там пользуется. Затем выясняем, насколько обоснованно.

Ответ на »сообщение 3318« (Руслан Богатырев)
___________________________

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

Успевают.

Традиция программирования, представленная в типичных учебниках, идет еще от фортрана-алгола...