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

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

Страницы: 1107 108 109 110112 Следующая »
#1605
22:43, 23 окт 2011

=A=L=X=
Ну понимаешь, это всё опять же очень уж зависит от реализации алгоритма.
Всё это приводит к тому, что оценивать константу в теории практически нереально.
Да, грубо оценить можно, но тогда так и надо писать - "порядок одинаковый, но за счёт константы первый метод в среднем во столько-то раз быстрее второго".
Но вот если человек считает, что это разный порядок сложности, называя оппонентов идиотами, то это уже проблема.

#1606
23:39, 23 окт 2011

TarasB

Ну в общем к чему то общему вроде пришли. За сим испаряюсь из этого жаркого топега. =)

#1607
1:01, 24 окт 2011

TarasB
может ты уже усмиришь свои буйный фантазии?
ни кто не говорил про разный порядок сложности
или для тебя запись
O(log(N+C))>O(log(N)) обозначает разный порядок сложности?

TarasB
> И на будущее - перестань считать оппонентов идиотами, не так эпично хоть сливать будешь.
ты не поверишь, но пока ты ведешь себя, точно так как я считаю.
хз почему так.

> А какое отношение тогда твоя оценка имеет к реальности?
очень простое, если алгоритм выполняет в два раза больше операций то он и в другой вселенной выполняет в два раза больше операций

#1608
1:10, 24 окт 2011

TarasB
Кстати в который раз хочу спросить, расскажи каким образом
"среднее" связано с O()?

#1609
5:57, 24 окт 2011

cNoNim
> если алгоритм использует 2 прохода, то его сложность 2N
  Да хоть десять, сложность O(N). Или давайте тогда не количество проходов считать, а количество тактов, затрачиваемых в среднем на каждый элемент. Будет получаться 123456*N.

#1610
8:28, 24 окт 2011

Zefick
> Или давайте тогда не количество проходов считать, а количество тактов,
> затрачиваемых в среднем на каждый элемент...

Програмиисты микроконтроллеров, а ранее и PC, а ранее и Кнут, светоч информатики при определенных задачах так и делают/ли, и не в среднем, а точно.

...

Блджаж, да загляните все в вики уже (http://ru.wikipedia.org/wiki/Вычислительная_сложность):

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

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

cNoNim (и я зачастую) говорит о временной сложности алгоритма, а TarasB об ассимптотической сложности.
Это действительно похожие, но в то же время разные понятия, и они оба существуют в реальности и используются то там то сям по сей день.
Причем даже когда говорят об ассимптотической сложности про константы таки нередко вспоминают и используют для отдания предпочтения тому или иному алгоритму в той или иной ситуации - см. ту же вики.
Если произошла терминологическая путаница - так только она и всё.

Можно посраться на следующую тему, цитата оттуда же:

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

Мне выделенное жирным кажется ложью, или я не понимаю о чём они хотели сказать. Потому что если есть, например, F1(2*N^2) и F2(N^2), то какие бы большие N мы не взяли, первый алгоритм будет всегда работать В ДВА РАЗА дольше второго. Говорить что "вклад постоянных множителей становится крайне незначительным" тут фимозно. День или два работает алгорим - это большие разницы.

#1611
14:59, 24 окт 2011

cNoNim
> O(log(N+C))>O(log(N)) обозначает разный порядок сложности?

Да.

cNoNim
> ты не поверишь, но пока ты ведешь себя, точно так как я считаю.
> хз почему так.

Странно, даже после чтения теории, только подтвердившей то, что я говорю, ты продолжаешь считать меня идитом. Может быть, идиот - ты?

cNoNim
> очень простое, если алгоритм выполняет в два раза больше операций то он и в
> другой вселенной выполняет в два раза больше операций

Нифига. Зависит от неявных действий процессора.

=A=L=X=
> Мне выделенное жирным кажется ложью, или я не понимаю о чём они хотели сказать.

Ну к константе-множителю это нельзя отнести, а вот к константе-слагаемому можно.

#1612
16:07, 24 окт 2011

=A=L=X=
> Мне выделенное жирным кажется ложью, или я не понимаю о чём они хотели сказать
они хотели сказать, что когда есть O(N) и допустим O(N^2), то мы всегда можем подобрать достаточно большое N, чтобы O(N) было быстрее O(N^2) в произвольное количество раз независимо от того что там на самом деле скрывается под O

но сказали криво, да

по факту, все эти O(N) нужны только для того, что бы можно было заявить - в нашем коде нет ничего заметно хуже чем O(NlogN)
при этом нужно понимать, что всякие сортировки пузырьком для N<число можно свести к O(1)

PS: списки и деревья в чистом виде не нужны.

#1613
16:16, 24 окт 2011

=A=L=X=
> Мне выделенное жирным кажется ложью, или я не понимаю о чём они хотели сказать.
  Речь идёт о том, что для двух алгоритвом со стожностью (N^2 + 100500) и (2N^2+10) первый будет быстрее на больших значениях M, а второй на маленьких, хотя классы сложностей одинаковые. В твоих примерах F1(2*N^2) и F2(N^2) нет вообще никаких слагаемых низших порядков. Ну и да, бывает, что алгоритм со сложностью O(N^2) работает быстрее, чем O(N*ln(N))

#1614
16:34, 24 окт 2011

О(N^C)=О(N)
It's joke. Take it easy.

И так, по теме:
djonmalkovi4
> Почему я никогда не буду использовать STL.
Потому что слаб мозгом? Только человек со слабым мозгом может заявить, что никогда не будет использовать STL ни при каких обстоятельствах. Решение об использовании чего либо или нет - следует принимать на трезвую голову отдельно перед началом или во время работы над каждым проектом в отдельности. В отрыве от конкретного проекта дать конкретный ответ нельзя.

#1615
16:38, 24 окт 2011

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

:)

короче, будут примеры как проще без stl - покажи

#1616
18:21, 24 окт 2011

Кстати, кто знает, когда итераторы становятся недействительными, то недействительные итераторы хоть в каких то реализациях STL оповещаются об недействительности? Может хотя бы с включенным SECURE_STL в MS VS?

#1617
18:38, 24 окт 2011

innuendo
сетевой двиг
клиентов либо 1 либо 3 либо 10
массив выделялся при инициализации, поиск по std::find
пул пакетов, 64 пакета на одного клиента
выделялся одним куском, указатели на свободные хранились в векторе. если вектор пуст, брался пакет из хипа, после введения алгоритма нагла хип не понадобился но на всякий случай его не удаляли
стрим движковый и он мне не очень нравился, там был косяк с определением размера но мне он мешал только в одном месте, заюзал workaround и забыл.
и так как всегда работа была только с буфером, можно было уйти от полиморфности стрима.

очередь отправки важных данных std::vector, удаление - обмен с последним, в среднем пакетов 20-30 на 10 клиентов (опять таки нагл выручил), обход в цикле

принимающая сторона сама заботилась о сортировке там где это было нужно
каждый объект содержал буфер на 2 сек (30 фреймов)
заполение зависело от пинга, чем больше пинг тем меньше пакетов в буфере. lag статический 250 мс, частота отправки 15 раз/сек
добавление в конец, при нарушении порядка std::sort, удаление через std::copy
поиск через std::lower_bound
у каждого сетевого перса свой буфер, максимум около 20 персов, можно было сгрупировать, так как время по которому сортировалось во всех очередях одно, и двигать/сортировать один раз но данные более крупного размера, так как данных не много, не проверял что быстрее

если бы писал сейчас, отказался бы от пула пакетов в сторону стрима с копированием неотправленных в начало.

#1618
18:43, 24 окт 2011


Pushkoff
> если бы писал сейчас, отказался бы от пула пакетов в сторону стрима с
> копированием неотправленных в начало.

напомнило мне это один сетевой код :)

ну а там в не таймкритикал местах ?

#1619
18:55, 24 окт 2011

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

очень хотелось иметь array<type, count> но на рефакторинг никто не давал времени
часто массивы виделялись на стеке, если что-то в них не влезало, отбрасывали. допустим апдейтилось максимум 8 или 16 комнат вокруг текущей, если больше то заставляли править уровень. не помню чтоб с этим были проблемы
боты могли взаимодействовать только с 30 персами в зоне видимости, хотя реально хватило бы и 10
максимум 32 скриптовых графа у объекта, когда перестали работать сетевые игроки, я понял что вылез за лимит, но двиг промолчал, или показывал очень невнятные места, у большей части объектов граф был 1, остальные 31 слот простаивали, не помню менял ли кто это поведение

самое смешное, что взрывающиеся бочки были персонажами без головы

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

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