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

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

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


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

Архив

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


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

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

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

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

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

 
   
С Л С

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

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

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

Квинтана

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

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

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

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

 
  
АРХИВЫ

 
 

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


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

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

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

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


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

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

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

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

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


№ 3326   19-03-2007 07:48 Ответить на это сообщение Ответить на это сообщение с цитированием
Ответ на »сообщение 3324« (Руслан Богатырев)
___________________________

Насчет состояний в ФП. Они, конечно, есть. Только в отличие от ИП носят скрытый (подпольный, косвенный) характер, что позволяет отдалить программиста от соблазна прямого вмешательства и, тем самым, содействовать повышению надежности. В этом существенный плюс ФП, который, как и любой плюс, в другом аспекте становится минусом. Считайте, что это автопилот. Но когда нужно ручное пилотирование, приходится стоять на ушах, чтобы отключить автопилот и получить доступ к штурвалу.


№ 3325   19-03-2007 07:45 Ответить на это сообщение Ответить на это сообщение с цитированием
Ответ на »сообщение 3322« (Jean)
___________________________
>>>Странный вопрос. Базовые характеристики алгоритма, такие, как,
O(f(N)), прежде всего, зависят от самого алгоритма
Вопрос не странный. Все алгоритмы сортировки, более быстрые, чем O(N^2) используют дополнительную память и различные хитрые манипуляции с ней. Естественно возникает вопрос, как реализовать эти алгоритмы в языке без операции присваивания не увеличивая многократно объем необходимой памяти.


№ 3324   19-03-2007 07:25 Ответить на это сообщение Ответить на это сообщение с цитированием
Ответ на »сообщение 3305« (Сергей Перовский)
___________________________

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

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

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

Извиняюсь за небольшой экскурс, но он требуется для пояснения идей. Возьмем такие хорошо известные формализмы, как конечные автоматы и сети Петри. Как известно, сети Петри эквивалентны машине Тьюринга, а конечные автоматы эквивалентны ограниченным сетям Петри -- автоматным сетям.

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

Сети Петри -- представитель асинхронного мира. Оперирует повязанными в сеть (граф) переходами и позициями (с находящимися в них фишками). Есть набор позиций (вместителей фишек) и набор переходов. Переходы связаны друг с другом только через позиции (и наоборот), т.е. их отношение определяется двудольным графом (в одной доле позиции, в другой -- переходы). Принято смотреть с точки зрения перехода: у каждого из них может быть несколько входов (ориентированных дуг, ведущих из позиции в переход) и несколько выходов (ор.дуг из перехода в позицию). На вместительность позиции (ее емкость) в общем случае ограничений не накладывается (потому и позволяет добиваться эквивалентности по мощности с машиной Тьюринга). Количество дуг из перехода в ту же позицию может быть более 1 (определяет "ширину" канала, т.е. сколько фишек может пропустить за такт).

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

Как известно, чем мощнее модель, тем сложнее она поддается анализу. Поэтому так распространены различные варианты ограничений сетей Петри. Наиболее активно применяются так называемые сети "условия-события" (event-condition nets), когда переход (transition) мыслится как событие (действие), а позиция (position) -- как индикатор условия. В них емкость позиции не может превышать 1 (условие либо выполняется, либо нет), число односторонних дуг между любой конкретной позицией и переходом не может быть больше 1.

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

В реальной практике используют группы автоматов (ансамбли), равно как и иерархические сети. Очевидно, это нивелирует некоторые неудобства моделей, но их сути принципиально не меняет. Чисто математически легко доказывается эквивалентность построения КА из автоматной сети Петри и наоборот.

В принципе можно говорить об автоматном (КА) и асинхронном (СП) программировании как о двух взаимодополняющих мирах. Здесь есть достаточно очевидно прослеживаемая связь с мирами императивного и функционального программирования.

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

К чему это я? Взаимосвязь ИП и ФП носит глубинный характер.


№ 3323   19-03-2007 07:05 Ответить на это сообщение Ответить на это сообщение с цитированием
Перефразирую: можно ли написать быструю сортировку на ФЯ, что бы время её работы осталось О(N log N) в "среднем" ?

Тот же вопрос об HeapSort и времени работы в "худшем" ?

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

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


№ 3322   19-03-2007 06:55 Ответить на это сообщение Ответить на это сообщение с цитированием
>>>Мой вопрос "можно ли реализовать сортировку за O(N log N) на ФЯ?" в
>>>соседней ветке проигнорировали.
Странный вопрос. Базовые характеристики алгоритма, такие, как,
O(f(N)), прежде всего, зависят от самого алгоритма, а не от того, на каком языке он написан и на какой аппаратуре выполняется. Быстрая сортировка Хоара всегда будет быстрее "пузырька" - и на си, и на паскале, и на хаскеле.
Вопрос лучше поставить таким образом: "Существуют ли алгоритмы сортировки, которые дают время решения задачи O(N log N)?"
Если да, то достаточно написать эти алгоритмы на ФЯ и Вы получите решение задачи за время O(N log N). Если это будет не так, значит транслятор ФЯ заменяет Ваш алгоритм каким-то другим :). Но это уже вопрос к разработчикам транслятора.


№ 3321   19-03-2007 05:48 Ответить на это сообщение Ответить на это сообщение с цитированием
Ответ на »сообщение 3320« (slava)
___________________________

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

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


№ 3320   19-03-2007 05:28 Ответить на это сообщение Ответить на это сообщение с цитированием
Если Вы хотите сказать, что на задачах мелкого масштаба (каковыми являются агоритмические олимпиадные задачи) существенную роль играет расширение типа, связанные процедуры или модификаторы ООП, то позвольте не поверить. Они там просто не успевают "раскочегариться".

Разумеется нет.

В остальном -- нужно смотреть на удобство программирования алгоритмической части в условиях жесткого лимита времени...

Именно об этом. Несмотря на кажущуюся схожесть (Борланд) Паскаля, Модула-2 и Оберонов, тем не менее даже для маленьких программ, где не требуются несколько модулей или расширение записей, есть разница. простой пример - открытые массивы как параметры в функциях. Работа со строками. Или выделение динамической памяти. Да и просто чистота и простота синтаксиса. Надёжность :).

Но мы-то сравнение по олимпиадным задачам проводим с "инопланетянами", братьями по разуму с далекой планеты ФП. :) Которых дискриминируют в высшем обществе спортивного программирования.

Мы хотим понять их цивилизацию и чисто прагматически прикарманить ценные идеи. Вот такие мы нехорошие люди.


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


№ 3319   19-03-2007 04:50 Ответить на это сообщение Ответить на это сообщение с цитированием
Ответ на »сообщение 3318« (Руслан Богатырев)
___________________________

Да, забыл сказать, в прошлом году я зондировал почву в среде организаторов наших соревнований по спортивному программированию в отношении Оберонов. Они готовы посодействовать преодолению барьеров на участие Оберонов там, где это в их компетенции. Но ACM ICPC -- это компетенция других. Поэтому ежели будут желающие, кто захочет проверить свои силы в жерновах внутренних личных и командных соревнований (а у нас лучшая в мире их инфраструктура), то милости просим. Готов посодействовать в меру возможностей.


№ 3318   19-03-2007 04:40 Ответить на это сообщение Ответить на это сообщение с цитированием
Ответ на »сообщение 3317« (slava)
___________________________

ИМХО, КП даже в олимпиадах имеет преимущество по сравнению с Паскалем.

Конечно, имеет. Кто же с этим спорит? Хотя Вы наверняка не о классическом Паскале, а о Turbo/Borland/Object Pascal/Delphi?

Давайте попробуем провести разграничительную линию между Паскалем (классическим), Модулой-2 (классической, не ISO), Обероном (классическим) и Компонентным Паскалем. Опять-таки, будем иметь в виду, что есть три ключевые области (о которых упоминал): алгоритмическая, интерфейс (UI, ввод-вывод), инфраструктура.

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

Если грубо "округлять", то разница между Модулой-2 и Обероном -- расширяемые RECORD-типы. Разница между Обероном и КП -- связанные процедуры и модификаторы ООП.

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

В остальном -- нужно смотреть на удобство программирования алгоритмической части в условиях жесткого лимита времени. Здесь будет играть роль даже все тот же пресловутый регистр идентификаторов (начавшийся в пост-паскалкевских языках с Модулы-2). Это относительное неудобство нивелируется известными средствами, о которых много уже говорили, поэтому в принципе нельзя считать изъяном. В остальном даже отсутствие бесконечных избыточных begin-end уже дает преимущество пост-паскалевским языкам, равно как и общая наглядность синтаксиса в алгоритмической части.

Но мы-то сравнение по олимпиадным задачам проводим с "инопланетянами", братьями по разуму с далекой планеты ФП. :) Которых дискриминируют в высшем обществе спортивного программирования.

Мы хотим понять их цивилизацию и чисто прагматически прикарманить ценные идеи. Вот такие мы нехорошие люди.


№ 3317   19-03-2007 04:07 Ответить на это сообщение Ответить на это сообщение с цитированием
ИМХО, КП даже в олимпиадах имеет преимущество по сравнению с Паскалем. У меня был переход с Модула-2 на Паскаль. Даже после месяца интенсивного "знакомства" с этим чудо языком, у меня осталось ощущение, что "плаваю в галошах". Даже с точки зрения решения задачек на олимпиаде.

Предполагаю, что схожее ощущение остаётся и от перехода с КП на Модула-2 или Паскаль.

Что касается ФП, то вопрос производительности даже для олимпиад является актуальным. Мой вопрос "можно ли реализовать сортировку за O(N log N) на ФЯ?" в соседней ветке проигнорировали. Но из моего опыта участия в олимпиадах могу сказать, что даже в простых задачах, тестирование проводится таким образом, что бы "простое" решение не проходило по времени на 20% тестах. Что является принципиальным в олимпиадах АСМ.


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


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

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

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

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

Перейти на конкретную страницу по номеру
  
Время на сайте: 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» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
Все используемые на сайте торговые марки являются собственностью их производителей.

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