Войти
ФлеймФорумПрограммирование

Почему я никогда не буду использовать STL. (107 стр)

Страницы: 1106 107 108 109112 Следующая »
#1590
20:57, 23 окт 2011

Zefick
> А если у нас итератор?

Вот с итератором - не знаю, самому что-то стало интересно как в STL реализовано.

P.S.

А, доперло как с итератором - решение о том куда делать следующий шаг - вверх, влево-вниз или вправо-вниз принимаем на основании того откуда был сделан предыдущий шаг, вроде этого достаточно чтобы так же обойти за O(2N) (sic!).

#1591
21:06, 23 окт 2011

innuendo
> уточните пожалуйста
"не холивор" забыл добавить!

#1592
21:19, 23 окт 2011

Ктстаи да, обход того же списка - это чистый O(N), просто берем следующего элемента и всё. А обход дерева всё таки тяжелее - на каждый элемент надо сперва спустится, потом поднятся, т.е. как минимум O(2N). А ваще то кроме того - действия по проверке на NULL ссылок лево-право, в случае итератора - проверки на направление перехода, т.е. еще тяжелее константа то будет.

#1593
21:27, 23 окт 2011

=A=L=X=
Я почему против такого фривольного понимания O().
А потому, что ваши оценки O(2N), я уверен, не соответвуют мнению профайлера.

=A=L=X=
> О, так выходит сложность обхода двоичного дерева есть O(N), ибо число ребер
> совпадает с числом элементом + 1 первый. =)

Нифига ты не первый.

TarasB
> Ну и никто не спорил, что обойти всё дерево - это O(N)

#1594
21:35, 23 окт 2011

TarasB
блин мне надоело, хотел не ввязываться.
при чем здесь O() и профайлер?
почему ты постоянно разговор о сложности переводишь в какие то конкретные не абстрактные подсчеты на каком нибудь конкретном железе/компиляторе

в подсчете O() участвуют только те константы, появление которых обусловлено самим алгоритмом, а не его реализацией,
я вот приводил пример алгоритма поиска индекса максимального элемента, то у него сложно O(2N) только из-за особенностей алгоритма, а не изза того что он так работает на каком то конкретном железе,

там один умник предлагал представить, что у нас не массив, а список я подумал ну его нафиг с такими споры вести, но не могу удержаться.
Что изменится в сложности того алгоритма если мы будем использовать список? вот что объясните мне?

И давай те уже без этих бестолковых доводов, вроде я помню учебник по мех мату который читал в СПБГУ.
Мне надо привести человека который закончил с красным дипломом мет мах МГУ? для того что б он подтвердил мои слова? или что?
быть может уже хоть кто нибудь приведет доказательство своих слов, а не будет нести тот бред который тут через пост встречается у представителей так называемой "не оппозиции"?

#1595
21:37, 23 окт 2011

innuendo
> уточните пожалуйста
там был пример кода, который я родил в качестве велосипеда, но потом посмотрев на него я его переделал на stl (map не использовал) и пример уже не привел, так как это часть проекта.
правда потом я еще посмотрел, и опять убрал стл и сделал на массивах с алгоритмами, а в качестве итератора использовал указатель.
не, вспомнил, оказалось что там массив не нужен. верней нужен но не там.

#1596
21:39, 23 окт 2011

cNoNim
> блин мне надоело, хотел не ввязываться.
> при чем здесь O() и профайлер?

Да притом, что на пальцах можно вычислить только порядок.
А константу, которую ты пытаешься найти, ты так не найдёшь. Кнут пытался на своём псевдокоде, но то работало только для тогдашних примитивных процессоров.
Хочешь знать константу - иди в профайлер. И тогда говори, что такой-то алгоритм в 2.13 раз быстрее такого-то. А твоё "в 2 раза" - это тоже, по-твоей логике, неверно, так как 2 не равно 2.13

cNoNim
> И давай те уже без этих бестолковых доводов, вроде я помню учебник по мех мату
> который читал в СПБГУ.

И как, сдал зачёт?
Я не понимаю, откуда у тебя такая манера агрессивно вести споры о вещах, которые ты не изучал, с теми, кто сдал полный курс?

#1597
21:46, 23 окт 2011

TarasB
> Да притом, что на пальцах можно вычислить только порядок.
да какой порядок?
если алгоритм использует 2 прохода, то его сложность 2N при чем здесь вычисления на пальцах? при чем здесь 2.13 раз быстрее?

TarasB
> Я не понимаю, откуда у тебя такая манера агрессивно вести споры о вещах,
> которые ты не изучал, с теми, кто сдал полный курс?
с какого ты так уверен что я не изучал и не сдал полный курс я не пойму?
ты когда универ закончил то?

#1598
21:47, 23 окт 2011

TarasB
> Я почему против такого фривольного понимания O().

У меня лично достаточно простое понимание того O() о котором я говорю - это число элементарных операций которые выполняет машина. Ессесно я знаю про кеш, спекуляцию и тэдэ и тэпэ. Тем не менее как минимум я смею утверждать, что обход двоичного дерева тяжелее обхода списка в разы на "незамутненной алгоритмической машине", коей в достаточной мере являлись процы лет 20-30 назад. Повторюсь, если мне не изменяет склероз, тот же Кнут чуть ли не по тактам высчитывал в своих пресловутых томах.

> Нифига ты не первый.

О, я так увлекся чтением вашего обсуждения про sqrt(N) и N/4, что даже не понял что это уже было ответом, прежде чем сам начал думать.

#1599
21:55, 23 окт 2011

TarasB

О, пока писал ты и сам написал половину того что высказывал я. =)
Так вот, подведу более четкую черту - несмотря на то что спекуляции и кеш в среднем алгоритмы одинаковой сложности но с разной константой даже на современных компах имеют больший шанс работать медленее те у кого константа больше и наоборот. Действительно возможны даже парадоксальные ситуации когда более громоздкий ассемблерный код выполняется быстрее более компактного и тому подобное, но в среднем шансы обратного выше.

#1600
22:10, 23 окт 2011

cNoNim
> если алгоритм использует 2 прохода, то его сложность 2N при чем здесь
> вычисления на пальцах?

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

cNoNim
> с какого ты так уверен что я не изучал и не сдал полный курс я не пойму?

Ошибки у тебя нубские. В сочетании с уверенностью в своей правоте получается просто ужасный, невыносимый собеседник.

=A=L=X=
> Так вот, подведу более четкую черту - несмотря на то что спекуляции и кеш в
> среднем алгоритмы одинаковой сложности но с разной константой даже на
> современных компах имеют больший шанс работать медленее те у кого константа
> больше и наоборот.

Именно. Поэтому оценка константы "на бумаге" вообще лишена смысла.
Есть даже пример того, как пузырёк ускорился втрое от перестановки двух операторов, не меняющих логику.

Так что константы можно оценивать только прямой проверкой.

#1601
22:28, 23 окт 2011

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

#1602
22:35, 23 окт 2011

TarasB
> Есть даже пример того, как пузырёк ускорился втрое от перестановки двух
> операторов, не меняющих логику.
>
> Так что константы можно оценивать только прямой проверкой.

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

У меня тоже хороший пример есть - на асме помню делал тест примитивного цикла никуда не обращающегося. Три варианта - один с loop (в то время как раз уже успевшим морально устареть), другой с проверкой регистра по cmp, но с легкой оптимизацией (код сравнительно короткий, вроде сравнение с нулем) и третий - самый большой, с проверкой по cmp с константой. На древнем пне было ожидаемо - первый вариант работал то ли медленее всех, то ли почти как второй, второй был быстрее всех, третий медленее второго. На современном (на то время) пне первый вариант - самый тормоз, второй вариант лучше, а третий работал быстрее всех. О, прозреваю силу конвеера! Далее беру атлон тоже современного (на то время) поколения и уже смеюсь - все три варианта работают абсолютно идиентично.
Это я к чему - это к тому, что если на каком то тесте что-то работает аномально - это не значит что оно будет работать анломально всегда, константа всё же придаёт тяжеловесности, либо по меньшей мере - равенства.
Поэтому её вполне разумно закладывать в предварительную оценку.

#1603
22:36, 23 окт 2011

cNoNim
> ты бредишь, братко, какое отношение время на загрузку данных в кэш имеет к
> оценке сложности алгоритма,

А какое отношение тогда твоя оценка имеет к реальности?
Порядок сложности - понятно, что значит, потому что особенности архитектуры на него пока повлиять не в силах.
А твоё "в 2 раза быстрее" - ваще не понятно. В реальности может как угодно быть.

И на будущее - перестань считать оппонентов идиотами, не так эпично хоть сливать будешь.
Пока что твой метод спора напоминает это:
holywar | Почему я никогда не буду использовать STL.

#1604
22:40, 23 окт 2011

TarasB

Подытожу:
Если меня сейчас спросить - а вот если написать на MS VC++ итерирование по списку и двоичному дереву - что будет работать быстрее?
Я скажу так: если элементы контейнеров будут рассеяны по памяти с одинаковой хаотичностью, то поиск по дереву будет скорее всего медленее. По меньшей мере быстрее он точно (в среднем) не будет. Насколько - это уже надо тестировать, в худшем случае ну где-то 3-4 раза, но оптимизатор может сгладить.

Страницы: 1106 107 108 109112 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.