Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Базарная площадь
  
О разделе

Основная страница

Группы обсуждений


Тематический каталог обсуждений

Архив

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  07:40[Войти] | [Зарегистрироваться]
Обсуждение темы:
Оберон-технология: особенности и перспективы


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

Количество сообщений на странице

Порядок сортировки сообщений
Новое сообщение вверху списка (сетевая хронология)
Первое сообщение вверху списка (обычная хронология)

Перейти на конкретную страницу по номеру


Всего в теме 6256 сообщений

Добавить свое сообщение

Отслеживать это обсуждение

Обсуждение из раздела
Школа ОБЕРОНА

<<<... | 3346—3337 | 3336—3327 | 3326—3317 | ...>>>
Всего сообщений в теме: 6256; страниц: 626; текущая страница: 293


№ 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«

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


№ 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« (Руслан Богатырев)
___________________________

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

Успевают.

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


<<<... | 3346—3337 | 3336—3327 | 3326—3317 | ...>>>
Всего сообщений в теме: 6256; страниц: 626; текущая страница: 293


Добавить свое сообщение

Отслеживать это обсуждение

Дополнительная навигация:
Количество сообщений на странице

Порядок сортировки сообщений
Новое сообщение вверху списка (сетевая хронология)
Первое сообщение вверху списка (обычная хронология)

Перейти на конкретную страницу по номеру
  
Время на сайте: GMT минус 5 часов

Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
Функция может не работать в некоторых версиях броузеров.

Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

 
© При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
Все используемые на сайте торговые марки являются собственностью их производителей.

Яндекс цитирования