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

E>>Так что элементарную эффективность на уровне кода так же нельзя сбрасывать со счетов.
M>Со временем это работает на автомате.

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

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

GZ>Maybe. Я чаще встречаюсь с незнанием подобных функций. И в очень извращенной форме.

Не без этого. Мне порой приходится студентам 3 курса объяснять. что цикл по символам при копировании строки с записью нуля в конце не есть хорошо, если есть strcpy.

GZ>ЗЫ Какой негодяй написал что while(*p++==*p1++); нормальный способ копирования строки

K&R


>(хотя знаю кто , но IMHO — это ошибка)?

Ты хочешь подхватить знамя дискуссии моей с Синклером на предмет того, есть ли у строки длина ?

>А самое главное сказал что это нормально.

В С — абсолютно нормально.

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

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

E>>>Так что элементарную эффективность на уровне кода так же нельзя сбрасывать со счетов.
M>>Со временем это работает на автомате.

E>При всем уважении, не могу согласиться. Слишком много факторов сейчас влияют на разработчика, чтобы можно было предугадать, где произойдет потеря производительности.

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

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

CS>Еще один пример: cascading style sheets и их computational complexity.

CS>Смотри, для документа с N DOM элементами, M стилями и D — средняя глубина дерерва
CS>задача нахождения стиля для каждого элемента это O( N * M * D ). Могу тебе сказать сразу — без тщательной прорабоки алгоритмов, просто так в лоб эту задачу не решить. Кстати я например использую один трюк который на managed в принципе не реализуем. Но это к слову.

Это получается "множественная диспетчеризация". Интересно, оно в языках, её поддерживающих, как то оптимизируется?

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

E>>>>Так что элементарную эффективность на уровне кода так же нельзя сбрасывать со счетов.
M>>>Со временем это работает на автомате.

E>>При всем уважении, не могу согласиться. Слишком много факторов сейчас влияют на разработчика, чтобы можно было предугадать, где произойдет потеря производительности.

M>Могу ответить прямо если бы я так думал , то был бы уже давно уволен.

А мне профайлер помогает
Так что я не думаю, я узнаю, где же я ошибся.

gwg-605,

> необходимое железо + стоимость разработки + стоимость поддержки = затраты. Минимум затрат большая прибыль.

Из Вашего уравнения выпали несколько существенных составляющих, начиная с качества, функциональности и usability получившегося продукта.

GlebZ,

> MS> Знаешь, какова сложность данного цикла? O(N^3).

> Учитывая особенности функции strcpy — меньше.

Уж не о том ли ты, что strcpy может копировать словами, а не байтами? Если да, то на оценку вычислительной сложности это никак не влияет, т.к. при определении O(...) константные множители игнорируются:

O( N * N * (N/4) ) == O( 1/4 * N^3 ) == O( N^3 )

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

Д>абсолютно не понимаю, что ты хотел продемонстрировать этими прописными истинами

Давай мы с тобой не будем спорить? Ибо "Если ты споришь с идиотом, вероятно, то же самое делает и он". Это ни в коем случае не оскорбление, наоборот — это некий само-сарказм. Чем больше мы с тобой разговариваем, тем большим идиотом я себя чувствую.

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

GZ>Индус — гений. Такое придумать жутко умная голова нужна.

Между прочим, пример вполне реальный, примерно пятилетней давности. И это был именно индус, очень коричневого цвета морды лица.

MS>>Знаешь, какова сложность данного цикла? O(N^3).
GZ>Учитывая особенности функции strcpy — меньше. Правда картины не меняет. Но все равно круто.

Кто познал сущность О-нотации, тот истинно крут! Какая такая "особенность strcpy" может убавить O?

Кстати, я был неправ в оценке времени для первого варианта. На 10 миллионах символов, при одной наносекунде на условную операцию это будет работать всего-навсего 31 тысячу лет. Ничтожное время по космическим меркам. Но зато на 100 миллионах уже будет 31 миллиард лет — вполне ощутимое время.

Здравствуйте, Павел Кузнецов, Вы писали:

>> Учитывая особенности функции strcpy — меньше.
ПК>Уж не о том ли ты, что strcpy может копировать словами, а не байтами? Если да, то на оценку вычислительной сложности это никак не влияет, т.к. при определении O(...) константные множители игнорируются:
ПК>

ПК>O( N * N * (N/4) ) == O( 1/4 * N^3 ) == O( N^3 )
ПК>

Грешен, ляпнул не разобрамшись. Почему делить на 4?

С уважением, Gleb.

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

MS>Кто познал сущность О-нотации, тот истинно крут! Какая такая "особенность strcpy" может убавить O?
Честно говоря такие шняги лучше мерять от и до. Это будет примерно O(N^2)<=x<=O(N^3). В зависимости от кол-ва пробелов.
Хотя O(N^2) по сравнению с O(N) — при большом N уже показания к сипуке.

Сейчас наставят минусов, но все-таки признаюсь.
Если бы это было в месте в котором я был бы уверен в том, что количество строк 2-3 и запускается только при загрузке, то может быть я бы пропустил такой код. Гадость но не смертельная. Даже под гнетом того, что код может перекочевать. Если бы в чем-то повторяющемся, или в месте где влияет на нагрузку работы — сипука.

С уважением, Gleb.
ЗЫ Ставьте минусы предателю.

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

Д>то есть примерно то же самое, что я предлагал
Д>хотя дьявол, как всегда, в деталях

Чтобы понять, что "дьявол в деталях", надо попытаться имплементировать. А этого в W3C никто не любит. Они же "теоретики"! Едреныть. И судя по неким косвенным признакам, они тоже не понимают сущности О-нотации. Ибо, если бы понимали, не гнали бы такую лажу. С SVG — то же самое. А потом они удивляются, почему это убогий Flash завоевал полмира, а наш великий и могучий SVG до сих пор в глубокой... где-то между ягодицами.

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

ПК>>

ПК>>O( N * N * (N/4) ) == O( 1/4 * N^3 ) == O( N^3 )
ПК>>

GZ>Грешен, ляпнул не разобрамшись. Почему делить на 4?

Наверное потому что на современных процах одно слово — это четыре байта. Можно делить на 8, на 1024, на 65536. Это не имеет значения. Сложность все равно остается "эн-куб".

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

GZ>Сейчас наставят минусов, но все-таки признаюсь.

А плюсик можно поствить?

MS>>Кто познал сущность О-нотации, тот истинно крут! Какая такая "особенность strcpy" может убавить O?
GZ>Честно говоря такие шняги лучше мерять от и до. Это будет примерно O(N^2)<=x<=O(N^3). В зависимости от кол-ва пробелов.
GZ>Хотя O(N^2) по сравнению с O(N) — при большом N уже показания к сипуке.

Я честно сказать тоже не понимаю О-нотацию. Но осмелюсь утверждать, что понимаю в ней хотя бы что-то. Это действительно сильное колдунство. Например, если в строке не более одного, не более тысячи, не более миллиарда пробелов, то формальная сложность алгоритма остается O(N^2) вне зависимости от фактического количества — ибо есть ограничение в виде некой константы. Но как только мы говорим, что каждый десятый символ — пробел, то сложность цикла сразу становится O(N^3). Можно даже сказать, что каждый миллиардный символ — пробел и все равно это будет N^3. Хотя фактически и практически никакой разницы нет.

GZ>Если бы это было в месте в котором я был бы уверен в том, что количество строк 2-3 и запускается только при загрузке, то может быть я бы пропустил такой код. Гадость но не смертельная. Даже под гнетом того, что код может перекочевать. Если бы в чем-то повторяющемся, или в месте где влияет на нагрузку работы — сипука.

Я и не утверждаю, что это плохо. Есть случаи, где такое вполне допустимо. Но!!! Надо четко оговаривать ограничения — типа не более 1000 символов. Или даже — "я написал лажу, вы имеете право ее использовать". Но таких признаний никто не любит — и в этом заключается весь корень зла. Типа одни индусы подразумевают, что "у нас супер-ультра-функция", а другие индусы, не подозревая о неявных ограничениях, используют эту функцию для 5000 символов. Получается полная вешалка.

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

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

Д>>то есть примерно то же самое, что я предлагал
Д>>хотя дьявол, как всегда, в деталях

MS>Чтобы понять, что "дьявол в деталях", надо попытаться имплементировать. А этого в W3C никто не любит. Они же "теоретики"! Едреныть. И судя по неким косвенным признакам, они тоже не понимают сущности О-нотации. Ибо, если бы понимали, не гнали бы такую лажу. С SVG — то же самое. А потом они удивляются, почему это убогий Flash завоевал полмира, а наш великий и могучий SVG до сих пор в глубокой... где-то между ягодицами.

Угу. я второй месяц пытаюсь найти автора придумавшего вот это:

8.3.2 Indirect adjacent combinator
Indirect adjacent combinators are made of the "tilde" (~) character that separates two sequences of simple selectors. The elements represented by the two sequences share the same parent in the document tree and the element represented by the first sequence precedes (not necessarily immediately) the element represented by the second one.

Example:
h1 ~ prerepresents a pre element following an h1. It is a correct and valid, but partial, description of:
<h1>Definition of the function a</h1>
<p>Function a(x) has to be applied to all figures in the table.</p>
<pre>function a(x) = 12x/13.5</pre

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

GlebZ,

>>> Учитывая особенности функции strcpy — меньше.

> ПК>Уж не о том ли ты, что strcpy может копировать словами, а не байтами? Если да, то на оценку вычислительной сложности это никак не влияет, т.к. при определении O(...) константные множители игнорируются:

> ПК>

> ПК>O( N * N * (N/4) ) == O( 1/4 * N^3 ) == O( N^3 )
> ПК>

> Грешен, ляпнул не разобрамшись. Почему делить на 4?

Ну, если бы речь шла о копировании словами вместо копирования байтами, то на 32-битной машине операций было бы в 4 раза меньше... Что на вычисление O(...) все равно не влияло бы

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

MS>А плюсик можно поствить?
Да на здоровье

MS>Я честно сказать тоже не понимаю О-нотацию. Но осмелюсь утверждать, что понимаю в ней хотя бы что-то. Это действительно сильное колдунство. Например, если в строке не более одного, не более тысячи, не более миллиарда пробелов, то формальная сложность алгоритма остается O(N^2) вне зависимости от фактического количества — ибо есть ограничение в виде некой константы. Но как только мы говорим, что каждый десятый символ — пробел, то сложность цикла сразу становится O(N^3). Можно даже сказать, что каждый миллиардный символ — пробел и все равно это будет N^3. Хотя фактически и практически никакой разницы нет.
У O нотации есть множество подводных камней. Один из которых ты как раз указал. Более классический пример — quicksort и пузырек. По моему ты как-то упоминал что с этим боролся. Полностью и маразматически доверять O нотации нельзя. Иначе мы бы давно сидели бы на хешах. Построить функцию которая будет с очень большой(даже можно сказать космической) вероятностью уникальна для значения(как это делается в криптохешах) в принципе легко. То есть организовать доступ O(1) для любой структуры можно. Но благодаря тому, что такая функция сама по себе достаточно тормозная, а результат функции будет достаточно большой по объему, никому это в голову и не приходит.

MS>Я и не утверждаю, что это плохо. Есть случаи, где такое вполне допустимо. Но!!! Надо четко оговаривать ограничения — типа не более 1000 символов. Или даже — "я написал лажу, вы имеете право ее использовать". Но таких признаний никто не любит — и в этом заключается весь корень зла. Типа одни индусы подразумевают, что "у нас супер-ультра-функция", а другие индусы, не подозревая о неявных ограничениях, используют эту функцию для 5000 символов. Получается полная вешалка.
Фигово когда не проводится нагрузочное тестирование и программа не анализируется через профайлер. В маленьких программах это действительно не особо нужно, так как все алгоритмы перед глазами. А вот в крупных комплексах, будь у тебя семь пядей во лбу, фиг спрогнозируешь что и где будет тормозить. К сожалению такие вещи не всегда возможны, но пытаться на опытных данных попробывать какая получилась производительность, и где находится bottle neck надо. И тогда никакие индусы не страшны.

С уважением, Gleb.

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Ну, если бы речь шла о копировании словами вместо копирования байтами, то на 32-битной машине операций было бы в 4 раза меньше... Что на вычисление O(...) все равно не влияло бы
Я то думал что ты каким-то неизвестным способом учитываешь что strcpy вызывается не всегда. Уже записал тебя в непризнанные гении. А тут такой облом. Такие вещи учитывать себя не любить. Со сменой проца менять аксиоматику рассчетов? А еще, ты не учел что шина 64битная и у тебя идет копирование по 8 байтам в кэш и во многом каждая вторая операция — профанация.

С уважением, Gleb.

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

CS>Сдуреть можно.

Ну его нафик, Андрей. Пойду-ка я лучше на роликах прокачусь вдоль West-side NYC.

E>Тогда ответь мне на такой вопрос: для какой-то задачи нужна машина класса P-200 и 128Mb памяти. Где ее взять?

Например вот современная машина с 32 Мб памяти под управлением Linux.
Мы писали для неё софт.
Работает отлично. Правда пришлось самим искать для неё C++ компилятор...

http://www1.linksys.com/products/product.asp?prid=640&amp;scid=43