Здравствуйте, AndreyFedotov, Вы писали:

AF> практическую бессмысленность этой задачи

1) Задача о конечных автоматах имеет практический смысл.
2) Наиболее эффективное решение этой задачи, без всяких сомнений, тоже имеет практический смысл.
3) Я показал способ решения более эффективный чем способ большого switch-я по состояниям.

Так в чем же бессмысленность?

Здравствуйте, Дарней, Вы писали:

Д>Я уже обосновал. Ты собираешься доказывать, что язык первобытных людей был сложнее современного?
Д>Языки не появляются ниоткуда, они являются продуктом развития общества. И чем сложнее становится общество, тем сложнее становится язык.

Ну, блин. Повторяю еще раз: русский, английский, немецкий, испанский, французский стали проще за последнюю 1000 лет. Так понятно? Теперь приведи примеры усложняющихся языков.
Как говорили первобытные люди никто не знает. Насколько сложен санскрит — предок всех индоевропейских языков я не знаю. Но латынь, например, сложнее всех порожденных ею европейских языков. Древнегреческий сложнее новогреческого.

Здравствуйте, Сергей Губанов, Вы писали:

СГ>1) Задача о конечных автоматах имеет практический смысл.
Несомненно.
СГ>2) Наиболее эффективное решение этой задачи, без всяких сомнений, тоже имеет практический смысл.
Несомненно.
СГ>3) Я показал способ решения более эффективный чем способ большого switch-я по состояниям.
Иди учить матчасть.

Здравствуйте, Дарней, Вы писали:

Д>В таком случае, вероятно, пещерные люди говорили на невообразимо сложном языке?
Д>Характерным для естественных языков является усложнение, а упрощение — это достаточно редкое явление и обычно является спутником деградации общества в целом.

Вы оба неправы. Для естественных языков характерна стабилизация в некоторой точке, когда содержание информации в тексте стремится к некоторой величине, для основных языков приблизительно 25%.

Здравствуйте, Сергей Губанов, Вы писали:

СГ>Здравствуйте, AndreyFedotov, Вы писали:

AF>> практическую бессмысленность этой задачи

СГ>1) Задача о конечных автоматах имеет практический смысл.
Безусловно.

СГ>2) Наиболее эффективное решение этой задачи, без всяких сомнений, тоже имеет практический смысл.
Безусловно. Но краткость записи — ещё не гарантия большей эффективности решения. D mathcad или mathlab формулы записываются не в пример короче C++/Java или Оберона — а вот считаются отнюдь не быстрее.
Тем более, если практически используется кодогенераторы...

СГ>3) Я показал способ решения более эффективный чем способ большого switch-я по состояниям.
Возможно, хотя это ещё надо проверять.

СГ>Так в чем же бессмысленность?
В пункте 2. Так как не доказано, что наиболее эффективное решение с точки зрения абстрактной математики является таковым и с точки зрения реализации. А так же в том, что кодогенератору вобщем случае всё равно, под какой язык генерировать код. Он может прекрасно воспользоваться указателями на функции — а в это случае выигрыша у Оберона вообще нет.

Здравствуйте, Дарней, Вы писали:

Д>А откуда перед этим взялась усложенная грамматика и орфография? Зеленые человечки научили?

Усложненная грамматика есть следствие желания более конкретно описать ситуацию. Т.е. отдельно с помощью грамматики передать длительность, обычность, законченность или порядок действий. Это вполне соответствует примитивному мышлению, не привыкшему к абстракциям. Но по сути в этом нет никакой необходимости. Часть этих оттенков можно передать другими средствами языка и тем самым упростить сам язык ничего практически не потеряв. В русском нет, например, времени для обозначения действия, которое произошло до другого действия в прошлом (а раньше оно было), и ничего — вполне можно пользоваться обычным прошедшим временем. Далее, в испанском обычно не употребляются личные местоимения — а зачем, если по форме глагола и так понятно о ком речь. Такое было бы и в русском если бы наше прошедшее время изменялось по лицам. В настоящем времени, во всяком случае, есть тенденция опускать местоимения. А во французском окончания глаголов не произносятся, поэтому там местоимения обязательны. В том же французском исчезло из разговорной речи одно из прошедших времен, поскольку существует второе время, которое его фактически дублирует.

Поэтому сложная грамматика — это как раз признак древнего языка. Можешь спросить об этом лингвистов, если мне не веришь.
Если говорить языках программирования, то аналог этого процесса — исчезновение ненужных или малоиспользуемых операторов из императивных языков. Но, поскольку, ЯП создаются исскуственно, там это менее заметно.

Здравствуйте, Сергей Губанов, Вы писали:

СГ>Здравствуйте, vdimas, Вы писали:

V>>Представь, что у тебя есть правило, которое верно для 100 случаев, но имеет исключения для 101-го...

СГ>Представить я это себе могу. Но, видители в чем дело, как только я начинаю на этом форуме чего-то представлять, то мне сразу тыкают, что я, мол, занимаюсь изучением сферических коней в вакууме и воюю с ветряными мельницами ака чудищами.

А что делать, если по твоим постам всё выглядит именно так?

СГ>Теперь по существу вопроса. Эффективные алгоритмы сортировки для разных типов чисел разные.
СГ>1) Однобайтовые числа — сортировка за один проход.
СГ>2) Двух байтовые числа — в зависимости от экономии/неэкономии памяти либо за один либо за два прохода, либо еще как...
СГ>3) Четырех байтовые числа — в зависимости от скорости памяти и размера кэша процессора и стратегии экономии или не экономии памяти есть несколько реализаций O(N) алгоритмов.
СГ>4) 64-битные — тоже что и для предыдущих пунктов с учетом большей нагрузки на пропускную способность памяти....
СГ>5) Тоже что и для предыдущих пунктов, но еще и для чисел со знаком — там нужен дополнительный "подкрут" в конце работы...
СГ>6) Числа из заданного диапазона.
СГ>....

И всё равно — все эти случаи довольно хорошо обобщаются. Фактически вопрос скорее в критериях для определения достаточного или не достаточного объёма памяти, а не неписании шаблона. Но даже если бы возникла ситуация, когда некая реализация сортировки (например байт) гораздо эффективнее, когда она сделана на прямую, вместо шаблона для чисел произвольного размера — сути дела это не меняет, так как может существовать миллион типов, основанных на байте, и лучше реализовать код в виде шаблона для типа, размером в байт, чем в куче мест делать приведение типов к байту и обратно.
Кроме того, очевидно, что сам пример с сортировкой не совсем корректен. Так как обычно нужен алгоритм достаточно быстрой NxLn(N), а не сверх быстрой сортировки. Если задача настолько критична по быстродействию, что потребовались такие методы — то это признак того, что код вообще должен не только писаться, но и проектироваться иначе, чем в обычных слуаях. Скорее всего тут может вообще потребоваться оптимизировать некоторые куски на ассемблере.

СГ>То есть, например, говорить о шаблонах и приводить в качестве примера шаблонную сортировку — это НЕХОРОШО. Так как в этом случае все наоборот: есть 1 общий случай и 100 частных конкретизаций, а раз так, то в случае сортировок шаблоны просто не нужны.
Как раз в большинстве случаев — нужны.

Здравствуйте, WolfHound, Вы писали:

AVC>>Код содержится в третьей главе упомянутой книги Кернигана и Пайка.
AVC>>На всякий случай привожу его здесь.
WH>А это... ну его уже порвали... Там использованы разные алгоритмы...
WH>Отсюда и дальше
WH>http://gzip.rsdn.ru/Forum/?mid=559116

Автор:
Дата: 03.03.04

WH>рвут на следующей странице.
WH>

После того, как я посмотрел на код свежим взглядом, выяснилось, что все, что я говорил про данный (С++) код ранее, мягко говря, бред Т.е. время уходит именно на заполнение map'а. Попробовал поиграть с типом ключа — без толку... А вот замена на hash_map (пришлось, правда, свою функцию написать) действительно, ускорила время в два раза. Итого на MSVC 6.0 SP5 + STLPort 0.23 sec, (ANCI C вариант — 0.22).

WH>Те в приделах погрешности измерения... А если сравнить объем кода

Спасибо, за ссылку на интересное обсуждение.
Вот такая конкретная аргументация мне нравится!
Однако, насколько я понял, Вы цитируете "сговорчивого" Андрея Ушакова, а не Кернигана (как я сначала подумал).
Но, похоже, я читал "первоисточник" внимательнее, чем Андрей.
И здесь есть маленькая такая тонкость.
Продолжу цитирование Кернигана и Пайка.

"Переход с дека на список (в STL это двухсвязанный список) кардинальным временем улучшает время. Переход же с отображения (map) на (нестандартный) контейнер hash под Irix не приносит никаких изменений (на машине с Windows у нас не было реализации hash)."

Ни я, ни тем более Керниган с Пайком (они, в принципе, STL там хвалят) не утверждали, что код STL не может быть эффективным в принципе.
Утверждалось следующее: реализации STL пока страдают недоделками, их производительность непредсказуема, стандартного контейнера hash нет.
И что же из сказанного неверно?
Если при переходе с deque на list производительность поменялась в 7 с лишним раз, а переход на (нестандартный) hash не привел к выигрышу, разве честно утверждать, что причина была в разнице между hash_map и map?
На Windows Керниган и Пайк в 1999г. не нашли hash_map (возможно, они не слишком и утруждали себя). Наверное, нашли бы, если бы этот шаблон входил в стандарт Си++.
Однако почему-то такие большие дяди, заседавшие в комитете по стандартизации Си++, не смогли прийти за 10(!) лет к единому мнению, каким он должен быть. Разве это не говорит о том, что не все ладно в "королевстве Си++"?
Но в целом за пост спасибо. Он информативен и конкретен. Так и надо!

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

Здравствуйте, Дарней, Вы писали:

Д>интересно, и что ты этим хотел доказать?
Д>Что любой начинающий сможет прочитать эту страничку и сразу начать программировать?
Д>

Я прочитал, программировать на Обероне не научился , наверно невнимательно читал.

А вобще компактность языка не так критична, главное стройность и логичность, возможности.
Меня не очень напрягает что в C# 2.0 появятся новые фичи и он станет немного сложнее, даже наоборот жду с нетерпением

Здравствуйте, Сергей Губанов, Вы писали:

СГ>

СГ>VAR m: SelfReplicatindMachine;
СГ>BEGIN
СГ>  m := m0;
СГ>  WHILE m # NIL DO m := m() END
СГ>

А состояние тогда где лежит? В глобальных переменных? Очень мило!

Здравствуйте, Сергей Губанов, Вы писали:

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

СГ>Теперь по существу вопроса. Эффективные алгоритмы сортировки для разных типов чисел разные.
согласен, для чисел малой разрядности можно использовать адресную сортировку, но уже для 32 бит это, ИМХО, излишество. Затраты на выделение временной памяти могут сожрать весь выигрыш от алгоритма. К тому же эти алгоритмы ведут себя одинаково на разных последовательностях (даже практически отсортированных), что, зачастую, тоже не есть гут.

[кусь]

СГ>То есть, например, говорить о шаблонах и приводить в качестве примера шаблонную сортировку — это НЕХОРОШО. Так как в этом случае все наоборот: есть 1 общий случай и 100 частных конкретизаций, а раз так, то в случае сортировок шаблоны просто не нужны.

ты привел идеальный случай, показывающий полезности шаблона.

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

Что ты получишь, определив данную стратегию?
— Полезную, повторно используемую наработку, применимую даже вне стен целевого алгоритма.
— К тому же, открытую к расширению, ибо для каждого нового типа тебе будет достаточно лишь определить новую специализацию (если вдруг стандартная не устраивает).
— Скорость разработки и отладки. В первом варианте ты можешь использовать самый общий оригинальный шаблон без специализаций (quick sort — неплохое "начало"). После, в процессе оптимизации, ты можешь "вылизать" свою стратегию, но смежники пока могут спокойно работать с твоим первоначальным кодом.
И т.д. и т.п.

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


Шаблоны — это отличная форма хранения наработок. Трудно, практически невозможно накапливать эти наработки в "отлитом из металла" виде. Еще ни разу не удалось применить их от проекта к проекту без серьезной доработки до требований конкретной задачи. И только шаблонные наработки легко и изящно кочуют из проекта в проект, позволяя минимумом движений адаптировать свое содержимое под конкретную задачу. А в подавляющем большинстве случаев гладко "ложатся" без каких-либо дополнительных телодвижений.

В этом смысле шаблоны — это серьезная альтернатива компонентам ("отлитым" в бинарные формы, а потому недоступным, загадочным и негибким. )

Компонент на уровне исходного кода, идеально вписывающийся в условия конкретного применения. Чем не мечта разработчика.

Здравствуйте, Геннадий Васильев, Вы писали:

ГВ>Здравствуйте, Сергей Губанов, Вы писали:

СГ>>

СГ>>VAR m: SelfReplicatindMachine;
СГ>>BEGIN
СГ>>  m := m0;
СГ>>  WHILE m # NIL DO m := m() END
СГ>>

ГВ>А состояние тогда где лежит? В глобальных переменных? Очень мило!

можно таблицу как параметр передавать
целесообразность подобного решения становится еще более спорной.

Здравствуйте, vdimas, Вы писали:

ГВ>>А состояние тогда где лежит? В глобальных переменных? Очень мило!
V>можно таблицу как параметр передавать
V>целесообразность подобного решения становится еще более спорной.

Мда. Разве что, можно ещё раз поругаться на тему инкапсуляции/полиморфизма/свободных функций и т.п.

Здравствуйте, Геннадий Васильев, Вы писали:

Я вообще не понимаю, чего на мужика накинулись.
Ну улучшили Паскаль. Ну на здоровье!
Через 10 лет еще улучшат. Мне вообще кажется, что языки, нацеленные на одни задачи, и нацеленные на выполнение их одинаковыми методами (здесь ООП + GC), где-то в будущем должны сходиться, с точностью до деталей синтаксиса и имен операторов. Просто Оберон отстает на старте, но еще неизвестно, каким он будет на середине дистанции.

Пути нашей братии неисповедимы...

Здравствуйте, vdimas, Вы писали:

V>Я вообще не понимаю, чего на мужика накинулись.
Так на Вирта никто по большому счёту и не набрасывается. Кхм... почти никто. Губанов уж больно провокационно выступает. Вот и расшумелись.

V>Ну улучшили Паскаль. Ну на здоровье!
V>Через 10 лет еще улучшат. Мне вообще кажется, что языки, нацеленные на одни задачи, и нацеленные на выполнение их одинаковыми методами (здесь ООП + GC), где-то в будущем должны сходиться, с точностью до деталей синтаксиса и имен операторов. Просто Оберон отстает на старте, но еще неизвестно, каким он будет на середине дистанции.
Это верно. Aos, кстати, любопытная система.

Здравствуйте, Mamut, Вы писали:

M>И это вариант скидывать со счетов не надо



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

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

Здравствуйте, Quintanar, Вы писали:

Q>Поэтому сложная грамматика — это как раз признак древнего языка. Можешь спросить об этом лингвистов, если мне не веришь.

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

Здравствуйте, Сергей Губанов, Вы писали:

СГ>Теперь, что, собственно, Вирт предлагает. А предлагает он свои обероны. Они очень простые — исчерпывающее описание оберонов спокойно убираются примерно на 30 страницах (последняя книга Вирта Programming in Oberon (от 1 октября 2004 года) содержит всего полсотни страниц). Каждый из них можно освоить, как раз, за ту самю неделю. Зачем пользоваться сложным если с тем же успехом можно пользоваться простым?

Язык по этой книге освоить нельзя. Она не описывает его в полной мере. Где, например, определение IS в книге? Вирт тут хитрит, жертвует содержанием ради уменьшения количества страниц. Not good.

Я даже не говорю об описании стандарной библиотеки Оберона, если таковая вообще существует.

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

Д>С этим я конечно не спорю. Я бы даже сказал, что в развитии любого софтверного проекта тоже происходят очень схожие процессы — про это пишут "три друга", к примеру
Д>Но если рассмотреть процесс в целом, то языки все-таки развиваются от простого к сложному. К примеру, в первых языках вообще не было такого понятия как время (и у некоторых современных неразвитых племен — то же самое). Но затем появилась потребность выражать в языке отношения во времени — и появились конструкции, которые позволяют это сделать.

Я с этим тоже не спорю. Язык усложняется, но до определенной точки, после которой он усложняется за счет расширения словарной базы, а не за счет новых грамматических наворотов.