Здравствуйте, Сергей Губанов, Вы писали:
СГ>Здравствуйте, Дарней, Вы писали:
Д>>Здравствуйте, Сергей Губанов, Вы писали:
СГ>>>в то время как для ряда частных случаев существуют O(N) алгоритмы. Тривиальный пример — сортировка массива целых чисел. А ведь именно массив целых чисел наиболее часто и встречается.
Д>>Как раз для такого случая существует частичная специализация шаблонов
СГ>Вот именно. На каждое средство в С++ есть противосредство. Даже на шаблоны придумали противошаблоны — частичную специализацию.
Сергей, если ты не понимаешь суть вопроса (а судя по всему это так и есть), то, пожалуйста, воздержись от выводов (которые не верны).
Здравствуйте, Quintanar, Вы писали:
Q>Сомнительная аналогия. Для естественных языков характерна тенденция к упрощению.
В таком случае, вероятно, пещерные люди говорили на невообразимо сложном языке?
Характерным для естественных языков является усложнение, а упрощение — это достаточно редкое явление и обычно является спутником деградации общества в целом.
Здравствуйте, Quintanar, Вы писали:
Q>Аналогия не верна. Пиджинг-инглиш — это что-то типа VB script, а не полноценный язык.
А что, с каких пор скриптовые языки стали неполноценными?
На том же самом VB script пишут даже системные службы, например. А ты говоришь — неполноценный
Здравствуйте, WolfHound, Вы писали:
AVC>>Ну, что же, в таком случае предлагаю "порвать" заодно и Кернигана вместе с Пайком. Эти злобные критики Си++ пишут в третьей главе своей книги "Практика программирования": WH>Канэчно порвем. Код в студию!
Код содержится в третьей главе упомянутой книги Кернигана и Пайка.
На всякий случай привожу его здесь.
/* Copyright (C) 1999 Lucent Technologies */
/* Excerpted from 'The Practice of Programming' */
/* by Brian W. Kernighan and Rob Pike */#include <time.h>
#include <iostream>
#include <string>
#include <deque>
#include <map>
#include <vector>
using namespace std;
const int NPREF = 2;
const char NONWORD[] = "\n"; // cannot appear as real line: we remove newlinesconst int MAXGEN = 10000; // maximum words generatedtypedef deque<string> Prefix;
map<Prefix, vector<string> > statetab; // prefix -> suffixesvoid build(Prefix&, istream&);
void generate(int nwords);
void add(Prefix&, const string&);
// markov main: markov-chain random text generationint main(void)
{
int nwords = MAXGEN;
Prefix prefix; // current input prefix
srand(time(NULL));
for (int i = 0; i < NPREF; i++)
add(prefix, NONWORD);
build(prefix, cin);
add(prefix, NONWORD);
generate(nwords);
return 0;
}
// build: read input words, build state tablevoid build(Prefix& prefix, istream& in)
{
string buf;
while (in >> buf)
add(prefix, buf);
}
// add: add word to suffix deque, update prefixvoid add(Prefix& prefix, const string& s)
{
if (prefix.size() == NPREF) {
statetab[prefix].push_back(s);
prefix.pop_front();
}
prefix.push_back(s);
}
// generate: produce output, one word per linevoid generate(int nwords)
{
Prefix prefix;
int i;
for (i = 0; i < NPREF; i++)
add(prefix, NONWORD);
for (i = 0; i < nwords; i++) {
vector<string>& suf = statetab[prefix];
const string& w = suf[rand() % suf.size()];
if (w == NONWORD)
break;
cout << w << "\n";
prefix.pop_front(); // advance
prefix.push_back(w);
}
}
Но существует одно качество, которое нельзя купить, — это надежность. Цена надежности — погоня за крайней простотой. Это цена, которую очень богатому труднее всего заплатить.
Здравствуйте, Дарней, Вы писали:
Д>Здравствуйте, Quintanar, Вы писали:
Q>>Сомнительная аналогия. Для естественных языков характерна тенденция к упрощению.
Д>В таком случае, вероятно, пещерные люди говорили на невообразимо сложном языке? Д>Характерным для естественных языков является усложнение, а упрощение — это достаточно редкое явление и обычно является спутником деградации общества в целом.
Ну тогда обоснуй свое мнение. Я уже привел пример русского. Точно также проще стали французский, испанский и немецкий. А англиский — это вообще потомок немецкого и то, что там практически полностью исчезли рода говорит само за себя. И почему тебя удивляет, что древние языки очень сложные? Какая-нибудь деревянная хата, построенная без единого гвоздя, может быть тоже в определенном смысле сложнее простого как палка небоскреба. Однако, последний явно превосходит ее технологически. Языки избавляются от лишней грамматической мути, которая только мешает излагать свои мысли.
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Именно такая конструкция является самым простым способом для программирования конечного автомата.
Те программирование сферического коня в вакууме? Не смешите мои тапочки. Конечные автоматы ручками не пишут. А если и пишут то на языке специально для этого заточеном.
Например лексер эффективнее всего реализовать именно конечным автоматом но блин вдолбить ручками конечный автомат в котором может быть несколько сотен состояний и при этом ни разу не ошибиться это не реально. По этому все пользуются генераторами лексеров, задают лексемы регулярными выражениями и не парятся. А построением по регулярному выражению НДКА, объеденением всех НДКА в один с несколькими конечными состояниями, преобразованием НДКА в ДКА, оптимизацией ДКА и генерацией кода занимается программа.
Короче Дон-Кихот (в смысле Вирт) нашол очередную мельницу и успешно ее победил. Ура товаррищи! Урррра!!!
ЗЫ Даже если не брать готовый генератор то ИМХО его проще написать чем ручками долбить конечный автомат.
ЗЗЫ Готов спорить что генереный КА будет работать быстрее чем рукописный построеный на указателях на функции.
... << RSDN@Home 1.1.4 rev. 185 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH> Конечные автоматы ручками не пишут.
А разве я предлагал ручками писать? Нет, действительно, я предлагал руками писать или не предлагал??? В моем сообщении написано, что указанный способ — самый простой. Могу добавить что еще и самый эффективный, так как нет затрат на switch. Там где-нибудь написано, что данный способ надо кодировать РУКАМИ, а не КОДОГЕНЕРАТОРОМ??? Что Вы себе позволяете, в конце-то концов...
Здравствуйте, Quintanar, Вы писали:
Q>Ну тогда обоснуй свое мнение. Я уже привел пример русского. Точно также проще стали французский, испанский и немецкий. А англиский — это вообще потомок немецкого и то, что там практически полностью исчезли рода говорит само за себя. И почему тебя удивляет, что древние языки очень сложные? Какая-нибудь деревянная хата, построенная без единого гвоздя, может быть тоже в определенном смысле сложнее простого как палка небоскреба. Однако, последний явно превосходит ее технологически. Языки избавляются от лишней грамматической мути, которая только мешает излагать свои мысли.
Я уже обосновал. Ты собираешься доказывать, что язык первобытных людей был сложнее современного?
Языки не появляются ниоткуда, они являются продуктом развития общества. И чем сложнее становится общество, тем сложнее становится язык.
Здравствуйте, AVC, Вы писали:
WH>>Канэчно порвем. Код в студию!
AVC>Код содержится в третьей главе упомянутой книги Кернигана и Пайка. AVC>На всякий случай привожу его здесь.
А это... ну его уже порвали... Там использованы разные алгоритмы...
Отсюда и дальше http://gzip.rsdn.ru/Forum/?mid=559116
После того, как я посмотрел на код свежим взглядом, выяснилось, что все, что я говорил про данный (С++) код ранее, мягко говря, бред Т.е. время уходит именно на заполнение map'а. Попробовал поиграть с типом ключа — без толку... А вот замена на hash_map (пришлось, правда, свою функцию написать) действительно, ускорила время в два раза. Итого на MSVC 6.0 SP5 + STLPort 0.23 sec, (ANCI C вариант — 0.22).
Те в приделах погрешности измерения... А если сравнить объем кода
... << RSDN@Home 1.1.4 rev. 185 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Вот именно. На каждое средство в С++ есть противосредство.
СГ>Даже на шаблоны придумали противошаблоны — частичную специализацию.
угу, спасибо авторам, здоровья им!
СГ>Смысл шаблона состоит в том что он одинаков для всех случаев. А если писать специализацию, то спасибо, я и без шаблона ее могу написать. Мне такие шаблоны не нужны.
Полная и частичная специализация — разные вещи.
Полная:
Представь, что у тебя есть правило, которое верно для 100 случаев, но имеет исключения для 101-го. Если бы не возможность полной специализации, ты бы должен был написать 101-у реализацию, а так ты пишешь всего 2.
Частичная:
Представь, что у тебя есть весьма общее правило, которое верно для 100 случаев, но при соблюдении определенного условия для каждого случая. Предположим, что этих дополнительных условий 3. Если бы не частичная специализация, ты бы должен был написать 100 реализаций, а так ты пишешь всего 3.
Мне такие шаблоны нужны.
-----------
очень жаль, что до сих пор нет частичных специализаций ф-ий, хотя ничего принципиально мешающего этому нет, и вроде их собираются когда-то ввести. Из-за их отсутствия приходится юзать классы-оболочки.
Д>Я уже обосновал. Ты собираешься доказывать, что язык первобытных людей был сложнее современного? Д>Языки не появляются ниоткуда, они являются продуктом развития общества. И чем сложнее становится общество, тем сложнее становится язык.
Упрощается грамматика и орфография языка, так как становится важным донести большее количество информации за меньшее количество времени. Но при этом используемые понятия, то есть используемый словарь в целом, становится сложнее.
имхо
... << RSDN@Home 1.1.4 beta 3 rev. 185>> ... <<Winamp is now playing "Silence">>
Здравствуйте, Mamut, Вы писали:
M>Упрощается грамматика и орфография языка, так как становится важным донести большее количество информации за меньшее количество времени. Но при этом используемые понятия, то есть используемый словарь в целом, становится сложнее.
А откуда перед этим взялась усложенная грамматика и орфография? Зеленые человечки научили?
Здравствуйте, Сергей Губанов, Вы писали:
СГ>А Вы так уверены в мощности С++? Думаете на нем все можно выразить? А можно попросить Вас задуматься как на С++ объявить тип функции, возвращаемым значением которой является переменная ее собственного типа?
Разумеется я так не думаю. Но во-первых на C++ эта задача решается, с помощью фукнторов, но дело в тругом. А зачем это вообще нужно и как часто встречается потребность в подобном?
А как насчёт сравнения обычных конструкций языка?
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Здравствуйте, WolfHound, Вы писали:
WH>> Конечные автоматы ручками не пишут.
СГ>А разве я предлагал ручками писать? Нет, действительно, я предлагал руками писать или не предлагал??? В моем сообщении написано, что указанный способ — самый простой. Могу добавить что еще и самый эффективный, так как нет затрат на switch. Там где-нибудь написано, что данный способ надо кодировать РУКАМИ, а не КОДОГЕНЕРАТОРОМ??? Что Вы себе позволяете, в конце-то концов...
Сир, а не кажется ли Вам, что кодогенератору сложность языка, под который он что-либо генерирует слегка по барабану? И что Вы сами, преведя пример конструкции, да ещё и заявив о ней, как о самом эффективнорм методе написания конечного автомата — в свете вышесказанного — просто-таки всячески намекали именно на возможность ручного написания конечного автомата?
И на что теперь обижаться — на то, что опоненты указали Вам на практическую бессмысленность этой задачи?
Здравствуйте, Сергей Губанов, Вы писали:
СГ>Вы правы. Таких ленивцев пруд пруди. Я в интернете однаждый видел реализацию оберона с генериками. Ссылка, правда, сейчас стала битой, поэтому дать не могу. Мерещится, что это был какой-то из вариантов OOC, O2C.
Вот это другое дело. Мне кажется — что в Обероне есть интересные идеи и возможно, что он со временем разовётся в нечто более инетерсное, чем сейчас комплект C++/C#/Jaba. И чем больше мы будем непредвзято обмениваться фактами — как позитивными, так и негативными для той или иной технологии — тем лучше будут они развиваться. В том числе и оберон.
Здравствуйте, Дарней, Вы писали:
Д>Здравствуйте, Mamut, Вы писали:
M>>Упрощается грамматика и орфография языка, так как становится важным донести большее количество информации за меньшее количество времени. Но при этом используемые понятия, то есть используемый словарь в целом, становится сложнее.
Д>А откуда перед этим взялась усложенная грамматика и орфография? Зеленые человечки научили?
И это вариант скидывать со счетов не надо
На самом деле, как я понимаю, сложность языка растет до определенного уровня. На сложность влияет ассимиляция других этнических груп, проникновение в язык неологизмов и заимствований из других языков, но в один прекрасный момент язык неизбежно должен остановиться и остаться на достигнутом уровне или попытаться очиститься от лишнего груза.
Так, русский сохранил в себе всего 5 времен для глаголов (будущее и прошедшее могут быть совершенного или несовершенного вида), но в нем все еще есть неправильные глаголы и причастия с деепричастиями.
В английском есть только герундий, но орфография — бррр. Причем в американском английском идет ее частичное упрощение (neighbour -> neighbor, colour -> color, programme -> program, dialogue -> dialog, plough -> plow), а некоторые из 16 возможных времен почти не используются (Future Perfect Continuous/Progressive in the Past — would have been doing ).
Турецкий — почти идеальный язык. Четкая система правил, которым следуют все слова чистого турецкого языка. Но оттоманское прошлое в виде заимствований из арабского и множество неологизмов, заимствованых из английского подрывают его устои.
И так, пожалуй, со всеми языками. Достигается определенный предел сложности, за которым идет некоторый откат назад — отсекаются избыточные и ненужные части (например, звательный падеж в румынском и, имхо, в руском).
Сейчас в большинстве современных языков достаточно развитых наций, как мне кажется, идет тенденция к упрощению грамматики языка (в том же румынском плюсквамперфект/Past Perfect, еще относительно недавно бывший не таким уж и редким, сейчас — удел поэтов; когда вы в последний раз видели букву ё в русском?; невозможно встретить какой-нибудь Future Perfect Continuous in the Past Passive Voice в английском, а в турецком заимствованые слова screen, kral(король) постепенно становятся sikrin, kiral, чтобы соответствовать правилам языка).
Но опять же, упрощение грамматики языка не ведет к упрощению самого языка, так как растет словарь языка. И, возвращаясь к предмету спора, то, что мы зачастую называем грамматикой языка программирования, является аналогом словаря разговорного языка, так как они призваны выражать концепции, а концепции выражаются словами.
... << RSDN@Home 1.1.4 beta 3 rev. 185>> ... <<Winamp is now playing "Silence">>
Здравствуйте, vdimas, Вы писали:
V>Представь, что у тебя есть правило, которое верно для 100 случаев, но имеет исключения для 101-го...
Представить я это себе могу. Но, видители в чем дело, как только я начинаю на этом форуме чего-то представлять, то мне сразу тыкают, что я, мол, занимаюсь изучением сферических коней в вакууме и воюю с ветряными мельницами ака чудищами.
Теперь по существу вопроса. Эффективные алгоритмы сортировки для разных типов чисел разные.
1) Однобайтовые числа — сортировка за один проход.
2) Двух байтовые числа — в зависимости от экономии/неэкономии памяти либо за один либо за два прохода, либо еще как...
3) Четырех байтовые числа — в зависимости от скорости памяти и размера кэша процессора и стратегии экономии или не экономии памяти есть несколько реализаций O(N) алгоритмов.
4) 64-битные — тоже что и для предыдущих пунктов с учетом большей нагрузки на пропускную способность памяти....
5) Тоже что и для предыдущих пунктов, но еще и для чисел со знаком — там нужен дополнительный "подкрут" в конце работы...
6) Числа из заданного диапазона.
....
То есть, например, говорить о шаблонах и приводить в качестве примера шаблонную сортировку — это НЕХОРОШО. Так как в этом случае все наоборот: есть 1 общий случай и 100 частных конкретизаций, а раз так, то в случае сортировок шаблоны просто не нужны.
Здравствуйте, Quintanar, Вы писали:
Q>>>Сомнительная аналогия. Для естественных языков характерна тенденция к упрощению.
Q>Ну тогда обоснуй свое мнение. Я уже привел пример русского. Точно также проще стали французский, испанский и немецкий. А англиский — это вообще потомок немецкого и то, что там практически полностью исчезли рода говорит само за себя. И почему тебя удивляет, что древние языки очень сложные? Какая-нибудь деревянная хата, построенная без единого гвоздя, может быть тоже в определенном смысле сложнее простого как палка небоскреба. Однако, последний явно превосходит ее технологически. Языки избавляются от лишней грамматической мути, которая только мешает излагать свои мысли.
Ага. Тогда, следуя этой логике, идеальный язык — это язык без слов.
Я, вообщем-то, склонен с этим согласиться, ибо еще Лао-Цзы сказал:
"Слово которое можно сказать — не есть истинное Слово"
Здравствуйте, Дарней, Вы писали:
Д>Здравствуйте, Mamut, Вы писали:
M>>Упрощается грамматика и орфография языка, так как становится важным донести большее количество информации за меньшее количество времени. Но при этом используемые понятия, то есть используемый словарь в целом, становится сложнее.
Д>А откуда перед этим взялась усложенная грамматика и орфография? Зеленые человечки научили?
В одной деревне говорили так, а в другой — по-другому. Чтобы никого не обидеть, пришлось всем учить оба наречия. Когда куча деревень стала городом, наречий стало еще больше. Когда встречались разные культуры, заимствование происходило в обе стороны, несмотря на то, что правило словообразования сильно отличались (классический пример — кофе мужского рода и парашют). Чтобы передать ВСЕ многообразие произносимых звуков, граммакика и орфография расширялись и расширились настолько, что это стало излишним. Плюс многие слова стали анахронизмами, а многие наречия — признаком "провинциальность" и "неаристократичности". Вот тогда и начался обратный процесс — вычленения лишних и малоиспользуемых форм и формирования стройной и логически правильной структуры языка. Так исчезли "ять", "фита", лишние падежи и прочее. И процесс этот продолжается до сих пор.
Здравствуйте, Сергей Губанов, Вы писали:
СГ>А разве я предлагал ручками писать? Нет, действительно, я предлагал руками писать или не предлагал??? В моем сообщении написано, что указанный способ — самый простой.
А к чему тогда все эти
Именно такая конструкция является самым простым способом для программирования конечного автомата.
Ведь если КА генерируется то это не имеет ни какого значения. Простота может иметь значение только при ручной работе. Когда работают машины там уже несколько иные критерии. СГ>Могу добавить что еще и самый эффективный, так как нет затрат на switch.
Без комментариев. Иди учить матчасть
... << RSDN@Home 1.1.4 rev. 185 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Ура товаррищи! 
).
