За что не любят Python?

Ты либо никогда не писал ничего сложнее hello world, либо хорошо упоролся. Почему ж тогда в Си есть модификатор «const», а не какой-нибудь «not_const» или «modifiable»?

во первых есть mutable, который как раз и нужен для изменения константных величин. Т.е. кто-то объявил твой класс const, но ты всё равно меняешь в нём поля mutable.

Все потому что объектам свойственно менять свое состояние. И как ты собираешься это описывать без присвоения уже инициализированных переменных?

специально предназначенными для этого методами очевидно! Например переместить указатель вперёд я смогу методом operator++(), при этом мне не помешает то, что этот итератор константный. Я ведь не менял объект.

Но уж никак не оператором operator=(), ибо знаю, что он часто ведёт к быдлокоду (гуру рекомендуют делать его private, дабы кто-то случайно не накосорезил, как и конструктор копирования).

И как ты собираешься это описывать без присвоения уже инициализированных переменных? А подсчет объектов, удовлетворяющих определенным условиям, алгоритмы поиска в структурах чуть более сложных, чем базовые контейнеры? Все это, значит, не нужно?

нужно. Только нужно также помнить о том, что без присваивания почти всегда можно обойтись. А когда нельзя, это именно не изменение, а отправка прошлого значения в помойку, и уж потом присваивание. Естественно, это не относится к базовым типам вроде int. За то относится к любым указателям - присвоить указателю можно ТОЛЬКО после того, как этот указатель был очищен.

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

какую архитектуру тебе не удалось реализовать?

Да, лучше создать еще десяток новых переменных. Тогда в мусор ничего не отправится, нет, оно просто все _останется_висеть_в_памяти_... пока, опять же, не отправится в мусор, причем, в том же объеме.

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

А вот в плюсах есть такая штука как умные указатели.

за тебя умные указатели собирают мусор? Сами? Научишь? А то мне их приходится обучать...

for(j = 0; j < 100500; j++) x = new int[1<<20];

А за это по-хорошему надо бы на костре сжигать.

за что именно? Это и есть повторное присваивание одной и той же переменной.

Краткость — сестра таланта!

Будь проще. А то уже такие портянки понакатали…

Будь проще.

действительно. Если проще, то x=... это уже быдлокод, если это x уже определено. И исключение тут может быть только одно - какой-нить ассемблер, в котором всего 8 регистров, по типу x86.

x=... это уже быдлокод, если это x уже определено

Это кто такую чушь сморозил?

x=... это уже быдлокод, если это x уже определено

Это кто такую чушь сморозил?

я. у тебя есть возражения? контрпримеры?

Допустим, у тебя в функции раз 100 встречаются циклы (поочередно). Так что — заводить 100 итераторов?

Допустим, у тебя в функции раз 100 встречаются циклы (поочередно). Так что — заводить 100 итераторов?

постой, 100 РАЗНЫХ циклов? Тогда да, к каждому *особому* циклу свой *особый* итератор.

Ну а если ты сделал 100 одинаковых циклов в одной функции, и с одним итератором(К.О.), то это говнокод. У него даже название есть: http://lurkmore.to/Индусский_код#K.D0.B8.D1.82.D0.B0.D0.B9.D1.81.D0.BA.D0.B8....

Это же идиотизм получится, писать

for(i = 0; i < X; i++){…}
for(j = 0; j < X; j++){…}
for(k = 0; k < X; k++){…}
for(l = 0; l < X; l++){…}

for(i = 0; i < X; i++){…}
for(i = 0; i < X; i++){…}
for(i = 0; i < X; i++){…}
for(i = 0; i < X; i++){…}

Это же идиотизм получится, писать

идиотизм. Потому-что, IRL это у тебя наверное одна матрица, с которой ты совершаешь некоторые действия (умножаешь на другую матрицу, прибавляешь матрицу, умножаешь на вектор, и т.д.). Почему нелогично все эти действия вынести в разные функции, которые тебе наверняка в дальнейшем пригодятся? например ввести функцию, которая перемножает матрицы, к примеру multi_matrix()? Зачем ты разворачиваешь это всё в одной функции? Думаешь, компилятор настолько тупой, что сам не может развернуть? Если ты так думаешь, то ты заблуждаешься, пруфы ты найдёшь в листинге objdump -S.

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

Если эти функции больше ни откуда не вызываются, то не логично.

Зачем ты разворачиваешь это всё в одной функции?

Я так делаю только тогда, когда код будет использоваться лишь единожды. Иногда делаю inline-функции, но их все равно надо будет определять внутри той функции, откуда они будут вызываться, чтобы не делать 100500 глобальных переменных или 100500 аргументов каждой функции.

Думаешь, компилятор настолько тупой, что сам не может развернуть?

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

Если эти функции больше ни откуда не вызываются, то не логично.

логично. Хотя-бы потому, что ты инкапсулируешь внутрь функций своё i, и у тебя не будет с ним проблем. Кроме проблемы повторного присваивания, существуют ещё как минимум одна проблема: внутри цикла ты не сможешь заюзать ещё раз своё i. Однако, внутри функции ты можешь юзать i, несмотря на то, что внутри вложенной функции юзается другое i.

Я так делаю только тогда, когда код будет использоваться лишь единожды. Иногда делаю inline-функции, но их все равно надо будет определять внутри той функции, откуда они будут вызываться, чтобы не делать 100500 глобальных переменных или 100500 аргументов каждой функции.

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

Думаешь, компилятор настолько тупой, что сам не может развернуть?

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

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

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

mutable - это свойство величины, проявляющееся в константном экземпляре класса. А ты что сморозил?

А когда нельзя, это именно не изменение, а отправка прошлого значения в помойку, и уж потом присваивание.

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

За то относится к любым указателям - присвоить указателю можно ТОЛЬКО после того, как этот указатель был очищен.

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

да, лучше. да, останутся.

Ну и чем же висящие в памяти никому не нужные переменные лучше чем немедленная отправка их в мусор?

за тебя умные указатели собирают мусор?

Я говорю про Си. Что такое «мусор» в этом контексте? Libtelepathy mode: они его не собирают, а предотвращают его появление.

за что именно?

За безусловное выделение памяти в цикле. Тем более, фиксированного размера.

я. у тебя есть возражения? контрпримеры?

Примеры - запросто:

int warnLevel = 0;
for( ItemList::const_iterator i = someList.begin(); i != someList.end(); ++i )
{
  if( (*i)->isAvailable() && warnLevel < (*i)->getWarnLevel() )
    warnLevel = (*i)->getWarnLevel();
}
return warnLevel;

mutable - это свойство величины, проявляющееся в константном экземпляре класса. А ты что сморозил?

никто не запрещает тебе почитать о том, зачем нужно это свойство. Раз ты этого не знал.

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

Во первых, в твоих постах через слово присутствуют умные указатели, которые и являются «сложными классами, имеющие нетривиальный деструктор», а во вторых, программы имеют свойство усложняться, потому сегодняшнее int завтра станет «простой структурой», а после завтра «сложным классом».

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

т.е. у твоего SP есть ещё метод, который рожает глупый указатель, для передачи во внутренний код? А где гарантия, что внутренний код не порушит SP через глупый указатель? А где гарантия, что глупые указатели будут рожаться только для внутреннего кода?

Ну и чем же висящие в памяти никому не нужные переменные лучше чем немедленная отправка их в мусор?

кто говорил про отправку в мусор? у меня значит переменная висит в C++, а у тебя пременные отправляются в мусор в пайтоне? Мы про присваивание или про C++ vs py?

Я говорю про Си. Что такое «мусор» в этом контексте?

тоже самое, что и в других ЯП. вместо того, что-бы кидать хабарики в пепельницу, мы кидаем их куда попало. Время от времени приходит уборщица, и их собирает. Если помещение большое, то это не сильно мешает работе, и даже помогает, ибо нам не надо отвлекаться, дабы идти к пепельнице.

Libtelepathy mode: они его не собирают, а предотвращают его появление.

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

За безусловное выделение памяти в цикле. Тем более, фиксированного размера.

ну-да, ну-да... Предлагаешь создать SP, который выделят память у себя в кишочках?

Примеры - запросто:

int warnLevel = 0;
for( ItemList::const_iterator i = someList.begin(); i != someList.end(); ++i )
{
  if( (*i)->isAvailable() && warnLevel < (*i)->getWarnLevel() )
    warnLevel = (*i)->getWarnLevel();
}
return warnLevel;

хм... warnLevel у тебя отрицательный? тебе поддержка яйца ещё не оторвала? Да и вообще, этот код имеет как минимум два недостатка (кроме интуитивно непонятного уровня, который ВНЕЗАПНО отрицательный):

1. нудно обойти весь список целиком в поисках минимума, это долго.

2. чисто архитектурно, минимум - свойство списка, потому у ItemList по уму должен быть метод ItemList::get_min_warnLevel(), который отдаёт минимум. А внутри пусть считает так, как оно ему виднее. Для прототипа пойдёт и этот код, хотя возможно в продакшене будет дешевле проверять минимум каждый раз, когда он изменяется.

Впрочем, ты всегда можешь сказать, что этот код вызывается 1 раз в 100500 запусков, что он не нужен, впрочем как и весь этот проект...

умные указатели, которые и являются «сложными классами, имеющие нетривиальный деструктор»

Умный указатель как раз заточен на использование оператора присвоения. Я не пойму, это такой стиль троллинга - заставлять объяснять очевидные вещи? Если да, то знай - это выставляет тебя не в лучшем свете.

сегодняшнее int завтра станет «простой структурой», а после завтра «сложным классом».

Далеко ходить не надо - есть руби. Но это еще не повод говорить об усложнении во всех ЯП.

вместо того, что-бы кидать хабарики в пепельницу, мы кидаем их куда попало. Время от времени приходит уборщица, и их собирает. Если помещение большое, то это не сильно мешает работе, и даже помогает, ибо нам не надо отвлекаться, дабы идти к пепельнице.

Отлично. Объяснение концепции GC на пальцах. Только где ты его в Си увидел?

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

Это С++ детка. Здесь нет никаких гарантий, что криворукий кодер не сгенерирует трудноотлавливаемый баг. И использование обычных указателей не сильно увеличивает эту вероятность.

SP это такие сигареты, которые имеют встроенный вертолётик, который их вовремя сам доставляет в пепельницу. Потому-то уборщица не нужна. Но сигареты в Over9000 раз дороже.

Дороже чего? GC? Ты видел реализации GC в С++? Эти убожества никак не быстрее обычного освобождения памяти и служат лишь для имитации выпрямления рук некоторых разработчиков.

SP, который выделят память у себя в кишочках?

Почитай, что такое SP - меньше будешь писать тупняка.

хм... warnLevel у тебя отрицательный?

Хм... ты еще и читать код не умеешь. Либо логика подкачала. Знание шаблонов программирования - это, конечно, хорошо, но ограничиваясь ими ты едва ли будешь лучше нердов-математиков, отрицающих их, и пишущих код основываясь лишь на мат. аппарате.

нудно обойти весь список целиком в поисках минимума, это долго.

Знания в области теории сложности у тебя тоже поверхностные. Видимо, я разорву тебе шаблон, если заявлю, что для некоторых n O(n) меньше O(log(n)).

по уму должен быть метод ItemList::get_min_warnLevel(), который...

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

Умный указатель как раз заточен на использование оператора присвоения. Я не пойму, это такой стиль троллинга - заставлять объяснять очевидные вещи?

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

сегодняшнее int завтра станет «простой структурой», а после завтра «сложным классом».

Далеко ходить не надо - есть руби. Но это еще не повод говорить об усложнении во всех ЯП.

я не про усложнение ЯП, а про усложнение самой программы.

Отлично. Объяснение концепции GC на пальцах. Только где ты его в Си увидел?

в C не видел, а в C++ лично реализовывал. УМВР. Не только у меня, кстати.

Это С++ детка. Здесь нет никаких гарантий, что криворукий кодер не сгенерирует трудноотлавливаемый баг. И использование обычных указателей не сильно увеличивает эту вероятность.

Да? А я думал, что SP как раз и нужны для уменьшения вероятности fuckup'а связанного с глупыми указателями (а в C/C++ только такие и есть, нету GC как и SP).

SP это такие сигареты, которые имеют встроенный вертолётик, который их вовремя сам доставляет в пепельницу. Потому-то уборщица не нужна. Но сигареты в Over9000 раз дороже.

Дороже чего?

умный указатель в Over9000 раз дороже глупого. Сам по себе. Понятное дело, для int'ов никто делать умный указатель не станет, а для огромных структур цена SP относительно невелика.

Ты видел реализации GC в С++? Эти убожества никак не быстрее обычного освобождения памяти и служат лишь для имитации выпрямления рук некоторых разработчиков.

GC в C++ в Over9000 раз быстрее по освобождению, т.к. освобождения нет в принципе. Как и в любом другом ЯП. Другое дело, что как и везде, использовать GC получается дороже. Ну и выделять место - тоже. В принципе, на SP получаются годные GC, если конечно не рожать ими глупые указатели (которые в принципе не отслеживаются).

Почитай, что такое SP - меньше будешь писать тупняка.

smart pointer http://en.wikipedia.org/wiki/Smart_pointer

Хм... ты еще и читать код не умеешь. Либо логика подкачала. Знание шаблонов программирования - это, конечно, хорошо, но ограничиваясь ими ты едва ли будешь лучше нердов-математиков, отрицающих их, и пишущих код основываясь лишь на мат. аппарате.

да я особо не вчитывался. Что не так?

Знания в области теории сложности у тебя тоже поверхностные. Видимо, я разорву тебе шаблон, если заявлю, что для некоторых n O(n) меньше O(log(n)).

а я тебе порву шаблон тем, что величина n в этих формулах значения не имеет. Они про то, как растёт время, а не про его конкретную величину. Т.ч. твоё заявление попросту не имеет смысла. (обычно полагают, что O() не зависит от величины N)

чуть позже дам тебе код без присваивания...

вот поиск максимума

(defun find-maximum (l)
(defun i (l maximum)
(if (null l)
maximum
(i (cdr l) (if (> (car l) maximum) (car l) maximum))))
(if (null l)
NIL
(i (cdr l) (car l))))

я не про усложнение ЯП, а про усложнение самой программы.

сегодняшнее int завтра станет «простой структурой», а после завтра «сложным классом».

Это что же такое должно произойти, чтобы инт так вывернуло?

в C не видел, а в C++ лично реализовывал. УМВР. Не только у меня, кстати.

А бенчмаркал? Результаты сравнения с классическим new/delete будут?

GC в C++ в Over9000 раз быстрее по освобождению, т.к. освобождения нет в принципе.

Осутвтвие освобождения называется memory leak-ом и у приличных людей считается проблемой.

да я особо не вчитывался. Что не так?

Все так, только непонятно, откуда ты отрицательные warnLevel-ы взял.

smart pointer http://en.wikipedia.org/wiki/Smart_pointer

Ну а дальше? Про смарт-поинтеры, выделяющие массивы «в своих потрохах»?

а я тебе порву шаблон тем, что величина n в этих формулах значения не имеет.

Какой он у тебя, однако, крепкий, этот шаблон. Упорно продолжаешь спорить о сферических формулах в вакууме, даже когда приблизительные значения N известны на этапе проектирования. В пример могу привести библиотеку GMP (Gnu Multiple Precision), где умножение реализовано двумя методами - классическим и по Карацубе. Второй имеет лучший показатель на бесконечности и используется для N, больших некоторого порогового значения, до которого классический алгоритм быстрее. Таким образом, формула времени работы оптимального алгоритма зависит от значения N.

вот поиск максимума

Отлично, спрятал присвоение за хвостовой рекурсией. Ожидалось все-таки красивое, правильное решение, а не изворот ради отказа от использования присвоения.

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

Это что же такое должно произойти, чтобы инт так вывернуло?

что угодно. Сегодня твоя функция выводит код возврата 0..255, а завтра это развитая система обработки и логирования ошибок.

А бенчмаркал? Результаты сравнения с классическим new/delete будут?

проверял. Работает на порядок быстрее. Что не удивительно: new/delete могут выделить что угодно и как угодно, мои варианты - только то, что надо и только так как надо. Было-бы странно, если-бы универсальный инструмент был-бы лучше специализированного.

Осутвтвие освобождения называется memory leak-ом и у приличных людей считается проблемой.

именно эту проблему и решает GC. Если у тебя нет GC, то освобождать память тебе необходимо во вполне определённое время, а не абы когда. С другой стороны, очевидно, что это не оптимально. Вот GC и откладывает этот момент. См. выше - уборщице проще подмести помещение 1 раз в день, чем бегать за каждым хабариком. А сам по себе хабарик на полу(кусок занятой памяти) проблемы обычно не представляет. Проблему представляют горы мусора, которые мешают производству. Очевидно же!

Все так, только непонятно, откуда ты отрицательные warnLevel-ы взял.

в твоём коде изначальная непонятка с нулём, с которым ты всё и сравниваешь. Сравнивать нужно первый элемент с остальными. Потому-что нет переносимого способа задать самое маленькое или самое большое число. На первый взгляд, раз ты взял int=0, то это может быть самым большим только для отрицательных, или самым маленьким для положительных, но почему тогда int? Что делать с отрицательными, которые меньше минимума?

Ну а дальше? Про смарт-поинтеры, выделяющие массивы «в своих потрохах»?

ну почитай... Я так бегло русский вариант просмотрел - вроде всё правильно написано. Явных ляпов как не странно нет.

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

шаблон да, крепкий. Я просто знаю очень простую вещь: определение. Так вот, O(f(N)) это по определению время выполнения, делённое на константу, в случае если N стремится к бесконечности. Потому разговоры о величине N не имеют смысла - оно задано в самом определении.

В пример могу привести библиотеку GMP (Gnu Multiple Precision), где умножение реализовано двумя методами - классическим и по Карацубе. Второй имеет лучший показатель на бесконечности и используется для N, больших некоторого порогового значения, до которого классический алгоритм быстрее. Таким образом, формула времени работы оптимального алгоритма зависит от значения N.

а причём тут «время работы»? мы про о-большое? А время - да, зависит от N. И запись O(f(N)) как раз и говорит, как это время зависит в пределе.

Отлично, спрятал присвоение за хвостовой рекурсией. Ожидалось все-таки красивое, правильное решение, а не изворот ради отказа от использования присвоения.

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

Ну а в твоём коде максимум _переписывается_ если он не максимум. Разница не слишком принципиальна в тривиальных случаях, но она есть.

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

Суть в том, что присваивание нужно намного реже, чем это кажется. В SICP много обсирают императивные ЯП именно за это. Хотя дело тут совсем не в императивности.

Сегодня твоя функция выводит код возврата 0..255, а завтра это развитая система обработки и логирования ошибок.

Еще раз спрошу - что может вызвать такую метаморфозу? Или ты сначала пишешь код системы, а потом принимаешься за ее проектирование?

мои варианты - только то, что надо и только так как надо.

Т.е. специализированый менеджер памяти? Так он и без GC даст прирост производительности.

в твоём коде изначальная непонятка с нулём, с которым ты всё и сравниваешь. Сравнивать нужно первый элемент с остальными.

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

Я так бегло русский вариант просмотрел - вроде всё правильно написано. Явных ляпов как не странно нет.

Я тоже бегло прочитал, потом воспользовался поиском по странице - нигде ничего не написано про выделение памяти, только про освобождение.

Так вот, O(f(N)) это по определению время выполнения, делённое на константу, в случае если N стремится к бесконечности.

Если N стремится к бесконечности, любая возрастающая функция от него тождественно равна бесконечности. Так зачем же все-таки записывают функцию?

И запись O(f(N)) как раз и говорит, как это время зависит в пределе.

В каком пределе? В бесконечности? А зачем мне эта бесконечность, если реальные значения N у меня колеблются в совсем других пределах.

Да, на x86 это скорее всего в присваивание развернётся - как я уже говорил, в x86 8 регистров

А если их будет 16 или, скажем, 64 - что-то кардинально изменится?

Суть в том, что присваивание нужно намного реже, чем это кажется.

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

Еще раз спрошу - что может вызвать такую метаморфозу? Или ты сначала пишешь код системы, а потом принимаешься за ее проектирование?

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

struct{
int value;
Game блекджек;
List шлюхи;
};

Т.е. специализированый менеджер памяти? Так он и без GC даст прирост производительности.

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

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

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

Я тоже бегло прочитал, потом воспользовался поиском по странице - нигде ничего не написано про выделение памяти, только про освобождение.

потому-что для выделения памяти SP не нужен. Он нужен для-того, что-бы её освободить и не потерять. А выделить можно в простой указатель. Но что-бы правильно освободить память, её надо правильно выделить - как SP узнает, что надо освобождать память, если она выделялась где-то сбоку? Никак. Именно потому, выделение происходит инкапсулированно в SP. Как я выразился «в кишочках SP». Проблема C/C++ в том, что указатели глупые, и кроме адреса ничего не знают. А любое использование адреса не по назначению - это непереносимое UB. Единственное, что ты можешь, это проверить на NULL. Узнать, в стеке или в куче ты не можешь. Узнать освободилось или нет - тоже.

Если N стремится к бесконечности, любая возрастающая функция от него тождественно равна бесконечности. Так зачем же все-таки записывают функцию?

Что-бы узнать КАК время стремится к бесконечности. Вот простой пример: сортируем массив на 1000000 эл-тов. Время равно T. Вопрос, сколько займёт сортировка массива в 1000000000 элементов? Если нам известно, что O(N*log(N)), и если для нашего компьютера 1000000 это БОЛЬШОЕ число, то мы можем применить эту формулу, и узнать, что время будет 10000*T (потому-что log(1000)=10). На самом деле время будет несколько меньше, но не намного. В любом случае, мы уже можем примерно оценить время. Т.е. проведя тест на массиве в 1000000, и получив секунду, мы можем _гарантировать_, что сортировка завершится менее, чем за 2 часа 45 минут, если N<1000000000. (конечно при этом мы должны быть уверены в формуле О()).

(это вводное объяснение на пальцах, сильно упрощённое, но достаточное для применения, если ты в Меня Веришь, как в Б-га. Если не веришь: читай Кнута, у него это правильно разжёвано, и с пруфами полными матана).

В каком пределе? В бесконечности? А зачем мне эта бесконечность, если реальные значения N у меня колеблются в совсем других пределах.

если твой алгоритм выполняется за секунду, то это ОЧЕНЬ долго. И в этом случае вполне можно пренебречь многим. Формулы становятся вполне точными - у тебя за секунду выполняются сотни миллионов действий, потому погрешность от лишней сотни действий - одна миллионная. Это вполне достаточная точность практически для любого заказчика. Кроме того, почти всегда нам нужна верхняя граница, если твоя программа сработает быстрее, тебя ругать не будут (в противном случае о-большое не подходит).

А если их будет 16 или, скажем, 64 - что-то кардинально изменится?

да. Дело в том, что _каждый_ регистр в x86 имеет своё уникальное назначение. Потому, даже если алгоритму надо всего 5 регистров, коду на х86 всё равно придётся кидать из регистра в регистр. Это быстро, но это тоже время. Имея 16 _универсальных_ регистров всё намного проще(но не быстрее. 16 универсальных регистров в 20+ раз сложнее 8и уникальных. В итоге профит от универсальности регистров съедается более низкой тактовой частотой).

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

ну вот когда понадобится, вспомни о том, что «повторное присваивание - источник ошибок».

ЗЫЖ в твоём примере присутствует оптимизация. На самом деле, алгоритм поиска максимума заключается в том, что-бы создать список максимумов, и взять последний элемент. Но ты оптимизировал этот алгоритм, и хранишь список в одном целом, постоянно его переписывая.

«Преждевременная оптимизация — это корень всех бед»

наоборот. но потом приходит заказчик, и говорит «всё хорошо, но это число должно быть с блекджеком и шлюхами».

Если изменения требуют больших переделок, мы его усаживаем оформлять новые требования, обсуждать сроки сдачи уже нового проекта, после чего, как правило, он соглашается на то, о чем договаривались. Учись иногда говорить «нет».

в таком случае и инициализировать надо было минимальной константой.

В моем случае это - ноль.

да и тип должен быть соответствующий enum, а не int.

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

Именно потому, выделение происходит инкапсулированно в SP. Как я выразился «в кишочках SP»

Сколько пишу на плюсах, ни разу не сталкивался с выделением памяти через код SP. Это разве что если реализовывать в них свой менеджер памяти...

как SP узнает, что надо освобождать память, если она выделялась где-то сбоку?

Ему приходит указатель на объект с обнуленным счетчиком ссылок. После освобождения его последним SP этот счетчик вновь обнуляется - вот и признак необходимости освободить память.

Что-бы узнать КАК время стремится к бесконечности... если N<1000000000.

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

если твой алгоритм выполняется за секунду, то это ОЧЕНЬ долго.

Как такой код на массиве максимум из 20 элементов может занять СЕКУНДУ???

да. Дело в том, что _каждый_ регистр в x86 имеет своё уникальное назначение. Потому, даже если алгоритму надо всего 5 регистров, коду на х86 всё равно придётся кидать из регистра в регистр. Это быстро, но это тоже время. Имея 16 _универсальных_ регистров всё намного проще(но не быстрее. 16 универсальных регистров в 20+ раз сложнее 8и уникальных. В итоге профит от универсальности регистров съедается более низкой тактовой частотой).

Ты не только вынуждаешь объяснять очевидные вещи, ты еще и сам это делаешь. В то же время, на вопрос ты не ответил - как дополнительные регистры могут избавить от операции присвоения в данном алгоритме?

ЗЫЖ в твоём примере присутствует оптимизация.

Тут нет никакой оптимизации - это тупейший алгоритм поиска максимума.

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

Это другой алгоритм, и я от него не отталкивался.

«Преждевременная оптимизация — это корень всех бед»

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

Если изменения требуют больших переделок, мы его усаживаем оформлять новые требования, обсуждать сроки сдачи уже нового проекта, после чего, как правило, он соглашается на то, о чем договаривались. Учись иногда говорить «нет».

случаи разные бывают на самом деле. Замена int на структуру - не всегда так кардинально. Может оно в трёх местах (пока) присутствует.

В моем случае это - ноль.

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

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

тут не нужно придумывать. Всё уже придумано до нас.

Сколько пишу на плюсах, ни разу не сталкивался с выделением памяти через код SP. Это разве что если реализовывать в них свой менеджер памяти...

странно. Что-то я не пойму, как твои SP освобождают память, которую выделил кто-то другой? Это же фундаментальный принцип: кто выделял память, тот и освободить должен!

Ему приходит указатель на объект с обнуленным счетчиком ссылок. После освобождения его последним SP этот счетчик вновь обнуляется - вот и признак необходимости освободить память.

ЯННП

А когда счётчик увеличивается? А почему счётчик не инкапсулирован в SP?

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

это пример для лучшего понимания.

Как такой код на массиве максимум из 20 элементов может занять СЕКУНДУ???

я говорил про массив из 1000000, и из 1000000000. Откуда ты 20 взял?

Тут нет никакой оптимизации - это тупейший алгоритм поиска максимума.

Это другой алгоритм, и я от него не отталкивался.

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

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

тут профайлер не поможет. Проблема в том, что возможно более правильное решение - изменять максимум не проверяя весь список, а в момент _изменения_ списка. А возможно, тебе тут надо два списка хранить - один по порядку, как уже есть, а второй по этому максимуму. Решений на самом деле много. Может это - оптимальное, а может и нет.

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

Так... присвоения не нужны, константы не нужны... сразу скажи, что еще ненужно - мне чисто чтоб поржать.

тут не нужно придумывать. Всё уже придумано до нас.

Ну ладно, перефразирую: лучше б _нашел_ красивое решение без повторного присвоения

Что-то я не пойму, как твои SP освобождают память, которую выделил кто-то другой? Это же фундаментальный принцип: кто выделял память, тот и освободить должен!

Стандартным деаллокатором. Никаких подобных принципов не слышал. Может, это тоже твоя личная задумка?

А когда счётчик увеличивается? А почему счётчик не инкапсулирован в SP?

Увеличивается при создании нового SP на объект. А счетчик должен быть привязан к объекту или той области памяти, в которой он размещен, а не к указателю на нее, коих может быть много. Вот инкремент/декремент этого счетчика - да, инкапсулирован в SP.

это пример для лучшего понимания.

Вот и я привел формулы O(n) и O(log(n)) для лучшего понимания, но получил только непонимание. Если совсем на пальцах - то алгоритмы, выигрывающие по времени на больших объемах данных, как правило, проигрывают в производительности на малых входах.

я говорил про массив из 1000000, и из 1000000000. Откуда ты 20 взял?

У меня массив из максимум, 20 элементов. Если что, это идентификаторы плагинов. Их не может быть 1000000.

Факт заключается в том, что список максимов - это общий алгоритм

Еще раз: одна задача, даже такая тривиальная как поиск максимума, может иметь несколько алгоритмов. Какой из них является «общим»? И если я воспользовался не так называемым «общим», каким-нибудь другим - что в этом плохого?

Проблема в том, что возможно более правильное решение - изменять максимум не проверяя весь список, а в момент _изменения_ списка.

Вызывать мьютекс при каждом изменении, вместо того, чтобы воспользоваться тем, что уже защищает ресурс «лог»? Нет, это не есть более правильное решение.

А возможно, тебе тут надо два списка хранить - один по порядку, как уже есть, а второй по этому максимуму.

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

Так... присвоения не нужны, константы не нужны... сразу скажи, что еще ненужно - мне чисто чтоб поржать.

много чего не нужно...

Ну ладно, перефразирую: лучше б _нашел_ красивое решение без повторного присвоения

выше было решение на LISP. оно не слишком красивое, я просто сделал то, чего ты хотел.

Что-то я не пойму, как твои SP освобождают память, которую выделил кто-то другой? Это же фундаментальный принцип: кто выделял память, тот и освободить должен!

Стандартным деаллокатором. Никаких подобных принципов не слышал. Может, это тоже твоя личная задумка?

тогда зачем тебе нужен SP, если ты «стандартным delete» память освобождаешь? Почему нельзя было обойтись обычным указателем?

Задумка не моя. Это чистая логика - никто не может убрать лучше того, кто здесь нагадил. Я надеюсь это очевидно, и примеров из RL не нужно? Но из этой логики также следует и то, что наибольший эффект уборки тогда, когда убирает тот, кто гадит.

Увеличивается при создании нового SP на объект. А счетчик должен быть привязан к объекту или той области памяти, в которой он размещен, а не к указателю на нее, коих может быть много. Вот инкремент/декремент этого счетчика - да, инкапсулирован в SP.

ну тут у нас некоторое разночтение в терминологии: я считаю, что понятие «счётчик» и понятие «значение счётчика» - разные. Значение лежит естественно в объекте. А вот сам счётчик - только считает, т.е. инкапсулирован в SP.

На самом деле, SP это обобщённая ссылка, и очевидно, что счётчик ссылок не может быть инкапсулирован в ссылку.

Вот и я привел формулы O(n) и O(log(n)) для лучшего понимания, но получил только непонимание. Если совсем на пальцах - то алгоритмы, выигрывающие по времени на больших объемах данных, как правило, проигрывают в производительности на малых входах.

ага. Непонимание. Выигрывание на больших объёмах данных вообще _никак_ не связано с выигрышем на малых. Просто в том учебнике, который ты осилил, это тебе пытались доказать на примерах. Но ты понял эти примеры слишком сильно: сортировка вставками сосёт на больших объёмах по сравнению с qsort, а qsort сосёт на малых, по сравнению с вставками. Из-за недостатка места в твоём учебнике, там не сказали, что пузырёк сосёт на малых объёмах, и сосёт на больших тоже. Мало того, qsort сосёт на малых у вставки, что не мешает пузырьку сосать у qsort и на малых тоже!

Нет такого правила «алгоритмы, выигрывающие по времени на больших объемах данных, как правило, проигрывают в производительности на малых входах», тебе просто примеры дали для подтверждения _другого_ правила «если алгоритм А сосёт у Б на больших входах, то это НЕ значит, что алгоритм А будет сосать у Б на малых».

И наконец, O() имеет смысл только для больших объёмов. Для малых это о-большоее просто не имеет смысла.

У меня массив из максимум, 20 элементов. Если что, это идентификаторы плагинов. Их не может быть 1000000.

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

достать из холодильника самый большой апельсин.

Какой смысл искать внутри холодильника самый большой апельсин, и класть его на специальную полку внутри этого холодильника? (как ты получаешь warnLevel)

Это и есть - преждевременная оптимизация.

Еще раз: одна задача, даже такая тривиальная как поиск максимума, может иметь несколько алгоритмов. Какой из них является «общим»?

вопрос не имеет смысла: алгоритмы не укладываются в дерево, у каждого узла которого единственный родитель. У алгоритма может быть любое число родителей. Минимально - 1. Любой алгоритм ты можешь написать «с нуля».

И если я воспользовался не так называемым «общим», каким-нибудь другим - что в этом плохого?

плохо то, что ты воспользовался не алгоритмом, а велосипедом. Вот две возможности:

1. можно стандартно отсортировать список, и взять первый эл-т. Это и есть максимум.

2. можно стандартно использовать отсортированный список. Тогда его максимум всегда будет в первом эл-те.

Вызывать мьютекс при каждом изменении, вместо того, чтобы воспользоваться тем, что уже защищает ресурс «лог»? Нет, это не есть более правильное решение.

не наблюдаю тут никаких мьютексов.

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

вообще-то этот код уже давно написан...

выше было решение на LISP. оно не слишком красивое

Не «слишком красивое» ?! Да это рекурсивный костыль, который в более сложном случае може и не прокатить.

тогда зачем тебе нужен SP, если ты «стандартным delete» память освобождаешь?

Потому что RAII-это удобно. «Стандартным delete» пользуется деструктор SP, который компилятор не забудет добавить в нужном месте, в отличие от человека. Потому что код выглядит эстетичнее.

никто не может убрать лучше того, кто здесь нагадил.

SP - это такой наблюдатель, который заставляет убрать уже ненужную вещь того, кто ее вытащил.

Просто в том учебнике, который ты осилил

Этому я как-то безо всяких учебников научился. Может, и к лучшему - теперь не пытаюсь подстроить реальную задачу под шаблон.

Нет такого правила «алгоритмы, выигрывающие по времени на больших объемах данных, как правило, проигрывают в производительности на малых входах»

_Правила_, конечно же, нет. Есть закономерность, полученая на личном опыте.

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

Я получаю максимум потому что он мне нужен. И как ты уже мог бы заметить, для этого я как раз «перебираю плагины и не парюсь».

плохо то, что ты воспользовался не алгоритмом, а велосипедом.

Я изобрел полный перебор? Может, стоит запатентовать?

можно стандартно отсортировать список, и взять первый эл-т. Это и есть максимум.

Надо ли говорить, что сортировка _любого_ объема данных занчительно накладнее их пербора?

не наблюдаю тут никаких мьютексов.

Потому что сейчас они за пределами данной функции.

Не «слишком красивое» ?! Да это рекурсивный костыль, который в более сложном случае може и не прокатить.

я не вижу разницы в «рекурсивном» и «итеративном» костыле. Ну я ладно, важнее то, что компилятор тоже не видит.

Потому что RAII-это удобно. «Стандартным delete» пользуется деструктор SP, который компилятор не забудет добавить в нужном месте, в отличие от человека. Потому что код выглядит эстетичнее.

ты меня запутал: с твоей delete мне всё понятно, а где порылась твоя new?

SP - это такой наблюдатель, который заставляет убрать уже ненужную вещь того, кто ее вытащил.

что-бы эффектно убирать хабарики, самый простой метод - отобрать спички/зажигалки. Тогда окурков не будет. А если и будут, то контроллер спичек будет о них знать.

Этому я как-то безо всяких учебников научился. Может, и к лучшему - теперь не пытаюсь подстроить реальную задачу под шаблон.

проблема в том, что твоё понимание неверное.

_Правила_, конечно же, нет. Есть закономерность, полученая на личном опыте.

возможно, у тебя просто мало опыта...

Я получаю максимум потому что он мне нужен. И как ты уже мог бы заметить, для этого я как раз «перебираю плагины и не парюсь».

т.е. ты всё равно будешь заниматься бесполезной работой, даже если она бесполезная?

плохо то, что ты воспользовался не алгоритмом, а велосипедом.

Я изобрел полный перебор? Может, стоит запатентовать?

да. нет.

ты изобрёл велосипед. патентовать не нужно.

Надо ли говорить, что сортировка _любого_ объема данных занчительно накладнее их пербора?

да. надо. попробуй доказать...

(впрочем не надо. RADIX сортировка как раз и является перебором. Именно RADIX сортировка и является одним из предков твоего перебора. Из неё можно вывести Bucket sort, а для неё прямо следует твой алгоритм поиска максимума(вырожденный частный случай). Все эти алгоритмы имеют сложность O(N)).

Потому что сейчас они за пределами данной функции.

там много чего за пределами.

я не вижу разницы в «рекурсивном» и «итеративном» костыле.

А я вижу - итеративный точно не будет выжирать стек, а рекурсию не всегда удается сделать хвостовой. Во-вторых, если мое решение - костыль, то что же тогда «не костыль»? Всеэти твои манипуляции с сортировками - вот это костыли в реализацию, дабы удовлетворить твоим представлениям о программировании.

ты меня запутал: с твоей delete мне всё понятно, а где порылась твоя new?

А new - за пределами кода SP: ObjectPtr someVar = new Object(...); Просто и понятно, а главное - при чтении кода сразу видно, что выделяется объект на куче.

что-бы эффектно убирать хабарики, самый простой метод - отобрать спички/зажигалки. Тогда окурков не будет.

Т.е. теперь ты уже говоришь, что выделение на куче не нужно...

проблема в том, что твоё понимание неверное.

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

возможно, у тебя просто мало опыта...

Его достаточно, чтобы насмотреться подобных примеров.

т.е. ты всё равно будешь заниматься бесполезной работой, даже если она бесполезная?

Где ты увидел «бесполезную работу»? А даже если и есть более простой вариант с меньшим объемом кода, не придется ли за него платить процессорным временем при исполнении? Ну ладно, этот код, который выполняется редко. А в общем случае?

ты изобрёл велосипед. патентовать не нужно.

Я не пойму, к чему претензия - к процессу изобретения? Ну уж извини, в данном случае поиск готового решения займет значительно больше времени, чем написание вот того клочка кода. Иногда проще изобрести свой велосипед без руля для езды по прямой, чем неоправданно возиться с установкой руля просто ради соответствия общепринятому виду.

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

да. надо. попробуй доказать...

Один проход с поиском максимума занимает линейное от размера входа время. Любая сортировка - минимум N*logN. Из накладных расходов - цикл со сравнением и опциональным присвоением, любая сортировка затребует больше. Таким образом, для N=1 оно эффективнее и растет медленнее.

там много чего за пределами.

Да, и оно должно было там остаться, если б ты не начал предлагать заменить всю функцию. А я вместо того, чтобы сказать, что это в споре офф-топик, начал объяснять как да почему.

А я вижу - итеративный точно не будет выжирать стек, а рекурсию не всегда удается сделать хвостовой.

потому-что рекурсия - более общий алгоритм: любой цикл можно перевести в рекурсию, и любая _такая_ рекурсия переводится в цикл. Но есть рекурсия, которая в цикл не переводится. Ну и что? В данном случае у нас именно такая рекурсия, которая не выжирает стек.

Во-вторых, если мое решение - костыль, то что же тогда «не костыль»? Всеэти твои манипуляции с сортировками - вот это костыли в реализацию, дабы удовлетворить твоим представлениям о программировании.

дело не в моих представлениях, а в том, что ты просто не видишь связей между алгоритмами. Это временно.

А new - за пределами кода SP: ObjectPtr someVar = new Object(...); Просто и понятно, а главное - при чтении кода сразу видно, что выделяется объект на куче.

ИМХО плохой дизайн - не видно, как объект освобождает память. Или наоборот. Потому-что код SP далеко от того кода, который этот SP использует. В данном случае, программист должен дать честное пионерское слово, что к любому объекту он присобачит SP, дабы он удалился. Но чем это лучше, обещания присобачить delete?

что-бы эффектно убирать хабарики, самый простой метод - отобрать спички/зажигалки. Тогда окурков не будет.

Т.е. теперь ты уже говоришь, что выделение на куче не нужно...

4.2

я не говорил - бросать курить, я предлагал контролировать спички. И я не предлагал не использовать кучу, я предлагал контролировать SP не только delete, но и new. Тогда с кодеров не нужно будет брать честного пионерского - кодер просто делает SP, и работает с ним. Когда SP будет удалён, он(SP) (если надо) удалит и свои кишки.

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

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

Его достаточно, чтобы насмотреться подобных примеров.

очевидно, ты видел несколько навороченных и сложных алгоритмов, которые дают выигрыш лишь на больших N. Потому и думаешь, что «если алгоритм хорош на больших N, то он плох на малых». Но это не верно.

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

вот именно. Докажи, что массив должен быть _несортированным_, мне это не очевидно.

Один проход с поиском максимума занимает линейное от размера входа время.

это верно, но не доказана обязательность такого прохода.

Любая сортировка - минимум N*logN.

бред полный. Это относится только к обменной сортировке массива, да и то, лишь в случае, если у нас есть O(1) памяти. Не более.

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

это не так. Формула с O-большое не учитывает накладные расходы. В итоге, сортировка займёт меньше, но меньше, чем она сама. Сравнивать разные сортировки ты права НЕ имеешь. Только лишь в случае, когда N равно бесконечности.

Таким образом, для N=1 оно эффективнее и растет медленнее.

когда N=1, то что у тебя «растёт»? Куда?

Да, и оно должно было там остаться, если б ты не начал предлагать заменить всю функцию. А я вместо того, чтобы сказать, что это в споре офф-топик, начал объяснять как да почему.

ну... У тебя демагогические аргументы: с таким-же успехом ты мог-бы доказывать, что тут надо плагины пузырьком сортировать, ибо их 20 штук всего, и проблемы быстродействия тебя не волнуют. Хотя, когда я предложил список отсортировать, ты ВНЕЗАПНО вспомнил про быстродействие. Почему-то постулируя то, что стандартная сортировка, написанная людьми поумнее нас с тобой, работает заведомо медленнее, чем твой велосипед. Но вот доказать ты это не хочешь, апеллируя к О-большому, которое, ты сам не воспринимаешь при малых N.

Но чем это лучше, обещания присобачить delete?

Тем, что он не забудет это сделать. Не говоря уж о читаемости кода. И вообще, в С++ бесполезно пытаться защитить криворукого кодера от выстрела себе в ногу. Он найдет еще 1000 и один способ это сделать. SP нужны не для этого, а просто потому что они удобны.

я предлагал контролировать SP не только delete, но и new.

И как ты предлагаешь запретить использование оператора new? Кому надо, тот все равно вызовет.

пруф был - сортировка пузырьком, которая всегда хуже других.

И как это коррелирует с вопросом о моем понимании формул О большого?

Потому и думаешь, что «если алгоритм хорош на больших N, то он плох на малых».

Я такого не думал, и не говорил. Видимо, ты приравнял выражение «как правило» к слову «всегда». Ну извини, ты не предупреждал, что у тебя плохо с русским языком.

Докажи, что массив должен быть _несортированным_, мне это не очевидно.

На входе он несортированный. Понимаешь, бывает, данные лежат не совсем в том формате, в котором тебе хочется, и приходится обрабатывать их как есть. А если уж и следует сортировать данный массив, то уж по более важному критерию, чем этот warnLevel.

это верно, но не доказана обязательность такого прохода.

Доказательство - пожалуйста: пусть мы можем выкинуть элемент под некоторым номером из перебора. Тогда в случае, когда он содержит единственное максимальное число, алгоритм отработает неправильно.

бред полный. Это относится только к обменной сортировке массива, да и то, лишь в случае, если у нас есть O(1) памяти. Не более.

Ок, приведи пример сортировки с меньшей сложностью.

когда N=1, то что у тебя «растёт»? Куда?

При увеличении N же.

Формула с O-большое не учитывает накладные расходы.

Ну и пусть не учитывает. Я ее и не использую для рассчета накладных расходов.

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

В _данном_ примере - не волнуют, ибо код выполняется раз в несколько секунд. Но аналогичный код можно встретить и в узких местах, и с еще меньшим размером входных данных.

Почему-то постулируя то, что стандартная сортировка, написанная людьми поумнее нас с тобой, работает заведомо медленнее, чем твой велосипед.

_Стандартная_ ?! Это какая из них?

Тем, что он не забудет это сделать. Не говоря уж о читаемости кода. И вообще, в С++ бесполезно пытаться защитить криворукого кодера от выстрела себе в ногу. Он найдет еще 1000 и один способ это сделать. SP нужны не для этого, а просто потому что они удобны.

отстрелить себе ногу можно в любом ЯП, в C++ с глупыми указателями это легче всего.

И как ты предлагаешь запретить использование оператора new? Кому надо, тот все равно вызовет.

нельзя вызвать new к тому, чего нет. Если инкапсулировать указатель внутрь SP, то для такого внутреннего указателя нельзя будет вызвать new. В твоей архитектуре SP вовсе не умный, ибо не знает, КАК выделена память. Он даже не знает, из кучи память, и ли нет, и _тупо_ делает delete неизвестно чего. StupidPointer.

Я такого не думал, и не говорил. Видимо, ты приравнял выражение «как правило» к слову «всегда». Ну извини, ты не предупреждал, что у тебя плохо с русским языком.

дык и правила такого нет. Ему просто неоткуда взяться - ты его придумал сам, чисто имперически. Спорить с ним, всё равно, что спорить с тем, что «холодное как правило горькое». Ну да, водка горькая, холодец горький... Мороженое - исключение.

На входе он несортированный. Понимаешь, бывает, данные лежат не совсем в том формате, в котором тебе хочется, и приходится обрабатывать их как есть. А если уж и следует сортировать данный массив, то уж по более важному критерию, чем этот warnLevel.

кто тебе запрещает хранить отсортированный массив? Религия?

Доказательство - пожалуйста: пусть мы можем выкинуть элемент под некоторым номером из перебора. Тогда в случае, когда он содержит единственное максимальное число, алгоритм отработает неправильно.

...в том и только в том случае, если этот твой список == Откровение Божие. И твоя программа впервые видит этот список. Если это не так, то ты можешь выкинуть всё элементы кроме новых и старого максимума.

Ок, приведи пример сортировки с меньшей сложностью.

я уже привёл: over9000 версий поразрядной сортировки.

когда N=1, то что у тебя «растёт»? Куда?

При увеличении N же.

тогда и пиши N>=1.

Ну и пусть не учитывает. Я ее и не использую для рассчета накладных расходов.

зря. При малых N обычно накладные расходы дороже. Потому, отбрасывать надо как раз o-большое.

В _данном_ примере - не волнуют, ибо код выполняется раз в несколько секунд. Но аналогичный код можно встретить и в узких местах, и с еще меньшим размером входных данных.

ну вот и определись, важна тебе скорость, или не важна.

_Стандартная_ ?! Это какая из них?

не знаю. Если речь о списках, посмотри на http://en.wikipedia.org/wiki/Merge_sort (неужели для твоего списка такой нет?).

отстрелить себе ногу можно в любом ЯП, в C++ с глупыми указателями это легче всего.

Это быстро проходит с опытом. Тем более, от них можно отказаться. Зато потом проявляются другие, более противные способы, например, операторы и конструкторы копирования по-умолчанию.

Он даже не знает, из кучи память, и ли нет, и _тупо_ делает delete неизвестно чего.

А если не из кучи - то из чего? Из стека? Из статической памяти? Ну и зачем делать для таких объектов SP?

дык и правила такого нет.

Так, иди учи русский. Могу даже помочь - http://jeck.ru/tools/SynonymsDictionary/как правило

кто тебе запрещает хранить отсортированный массив? Религия?

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

Ну ладно еще, что страдает процессорное время - им часто жертвуют в угоду облегчения процесса разработки. Но тут и разработчику работы добавляется.

если этот твой список == Откровение Божие. И твоя программа впервые видит этот список.

Это откровение юзерово, изложенное в конфигах. И на то, что ко второму запуску приложения оно не поменяется, надеяться не стоит.

в том и только в том случае...

В общем случае. Когда у программы нет дополнительной информации об этом списке. Независимо от того, была ли возможность ее получить.

я уже привёл: over9000 версий поразрядной сортировки.

Меньше верь википедии, больше думай головой. Временная сложность всех этих сортировок оценивается как O(n*m*k), где m - количество значащих блоков (в данном случае битов или их групп) в сортируемых ячейках, а k - размер множества возможных значений такого блока. Конечно, для данных фиксированной длины (как в данном случае, 4 байта), мы можем объявить m и k константами и попросту выкинуть их из формулы, хотя в случае сортировки _уникальных_ значений произведение m*k как раз и будет верхней оценкой log(n).

Поскольку значения не уникальны, тем более, у меня всего 6 возможных значений warnLevel, я мог бы просто посчитать количество элементов каждого значения, и это заняло бы линейное время. Но зачем это делать, если я сделал еще проще - вычленил нужное значение без выделения доп. памяти за то же самое время.

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

По этой причине, а также потому, что для ее реализации требуется знать структуру сортируемых ячеек, она не входит в библиотеки стандартных алгоритмов. Так что аргумент «все уже написано до нас» не прокатывает.

При малых N обычно накладные расходы дороже.

Т.е. их удельный вес больше. А я про абсолютное количество дополнительных операций, которое, конечно же, не уменьшается с ростом N.

ну вот и определись, важна тебе скорость, или не важна.

Я привел пример, где скорость не важна, т.к. не думал, что такой вопрос вообще возникнет. Но ты вдруг заговорил об оптимизации, видимо, полагая, что сортировка массива будет здесь более уместна, и тем самым избавиться от злополучного присвоения. Вот я и начал объяснять, что она здесь ничего не ускорит.

Почему-то постулируя то, что стандартная сортировка, написанная людьми поумнее нас с тобой, работает заведомо медленнее, чем твой велосипед.

Если речь о списках, посмотри на http://en.wikipedia.org/wiki/Merge_sort

Так вот эта сортировка заведомо медленнее моего «велосипеда» (скорее даже, «табуретки со школьных уроков труда», ибо поиск минимума/максимума, который задают современным школьникам они как правило обычно реализуют таким способом. Не помню, чтоб кто-то подходил к этому вопросу со стороны сортировок).

А если не из кучи - то из чего? Из стека? Из статической памяти? Ну и зачем делать для таких объектов SP?

не знаю зачем ты делаешь такие SP, которые удаляют delete объекты из стека. Мои SP так не умеют.

дык и правила такого нет.

Так, иди учи русский.

причём тут русский? правило выводит какую-то связь. Связи между временем (при малом N) и о-большое - нет. Просто по определению о-большого.

Я уже сказал - накладные расходы на сортировку.

ещё ты сказал, что они тебя не волнуют в данном случае. (и правильно не волнуют, ибо полный перебор списка займёт примерно столько же, сколько сортировка при малом N).

И это не говоря уже о том, что для сортировки списка «на лету» придется пожертвовать его константностью во времени исполнения и облачить обращения к нему в критические секции.

не нужно. всё равно надо менять item_list->next для добавления. Просто надо будет менять не у первого, а у какого-то другого (вставить в нужное место).

Ну ладно еще, что страдает процессорное время - им часто жертвуют в угоду облегчения процесса разработки. Но тут и разработчику работы добавляется.

в одном месте чуть сложнее, в другом чуть проще...

Это откровение юзерово, изложенное в конфигах. И на то, что ко второму запуску приложения оно не поменяется, надеяться не стоит.

а ты надейся. в 999 случаях из 1000 твой новый максимум не нужен.

Меньше верь википедии, больше думай головой.

про radix-сортировку я знал задолго до появления википедии.

Конечно, для данных фиксированной длины (как в данном случае, 4 байта), мы можем объявить m и k константами и попросту выкинуть их из формулы, хотя в случае сортировки _уникальных_ значений произведение m*k как раз и будет верхней оценкой log(n).

ты бредишь? В _твоём_ случае у тебя вообще десяток констант. Ну а в общем случае, твои рассуждения верны, только если m,k у тебя стремятся к бесконечности. А это какой-то _очень_ специальный случай.

Поскольку значения не уникальны, тем более, у меня всего 6 возможных значений warnLevel, я мог бы просто посчитать количество элементов каждого значения, и это заняло бы линейное время. Но зачем это делать, если я сделал еще проще - вычленил нужное значение без выделения доп. памяти за то же самое время.

ну если-бы у тебя было 6 счётчиков, то за константное время ты можешь поддерживать отсортированную структуру, в качестве максимума выбирая первый ненулевой счётчик. Т.е. для добавления в список надо О(1) операций, для поиска максимума О(1) операций. Хранить только максимум нельзя - если ты удалил максимальный элемент из списка, то непонятно, каким был прошлый максимум.

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

ЩИТО? причём тут вставки, слияние, и qsort?? radix не имеет никакого отношения к эти трём сортировкам. Смысл radix сортировки в том, что эл-ты СРАЗУ расставляются по своим местам. Без всяких перестановок и слияний. А вот для остальных сортировок приходится последовательно применять несколько итераций, в конце которых эл-ты будут упорядочены.

При все итерации занимают O(N), но для вставок нужно O(N) итераций, для qsort от O(log(N)) до O(N), и для слияния всегда O(N). Для radix надо всегда O(1) итераций, кроме случая сортировки бесконечных множеств.

Т.е. их удельный вес больше. А я про абсолютное количество дополнительных операций, которое, конечно же, не уменьшается с ростом N.

проблема в том, что ты рассуждаешь про _время_ операции. А надо считать не время, а _разность_ времени. Например - Tb это премя пузырька, а Tq это время qsort. Так вот, Tb > Tq не только для больших N, но и для малых N. к примеру, сортируя массив 3 2 1 с помощью qsort нужен один обмен, а при пузырьке

3 2 1
2 3 1
2 1 3
1 2 3

По этой причине, а также потому, что для ее реализации требуется знать структуру сортируемых ячеек, она не входит в библиотеки стандартных алгоритмов. Так что аргумент «все уже написано до нас» не прокатывает.

ну сделать массив из 6и счётчиков ты не в состоянии?

Я привел пример, где скорость не важна, т.к. не думал, что такой вопрос вообще возникнет. Но ты вдруг заговорил об оптимизации, видимо, полагая, что сортировка массива будет здесь более уместна, и тем самым избавиться от злополучного присвоения. Вот я и начал объяснять, что она здесь ничего не ускорит.

не ускорит, но сделает программу более простой и масштабируемой.

Так вот эта сортировка заведомо медленнее моего «велосипеда»

кстати, вдвое быстрее при малых N. если слияние совместить с вставкой.

не знаю зачем ты делаешь такие SP, которые удаляют delete объекты из стека. Мои SP так не умеют.

Я не делаю SP на объекты на стеке. А если точнее, не выделяю разделяемые объекты на стеке. Попутно отрываю руки тем, кто так делает.

причём тут русский?

При том, что ты не знаешь устойчивых выражений. Я для тебя даже объяснил, что вводное выражение «как правило» означает «обычно», «зачастую» и т.п. Даже ссылку привел. Нет, ты мне про какое-то «правило» продолжаешь талдычить.

не нужно. всё равно надо менять item_list->next для добавления.

Для добавления чего?

а ты надейся. в 999 случаях из 1000 твой новый максимум не нужен.

Конечно же, это весомая причина фейлить каждый 1000-ый запуск.

Ну а в общем случае, твои рассуждения верны, только если m,k у тебя стремятся к бесконечности. А это какой-то _очень_ специальный случай.

Этот _очень_ уникальный случай в жизни встречается _очень_ часто. Например, массивы строк произвольной длины. Надо ли говорить, что в доброй половине случаев приходится сортировать уникальные данные?

ну если-бы у тебя было 6 счётчиков, то за константное время ты можешь поддерживать отсортированную структуру, в качестве максимума выбирая первый ненулевой счётчик. Т.е. для добавления в список надо О(1) операций, для поиска максимума О(1) операций. Хранить только максимум нельзя - если ты удалил максимальный элемент из списка, то непонятно, каким был прошлый максимум.

А я об этом и говорил. И эти манипуляции придется делать при каждом изменении какого-то из этих значений. И использовать объекты синхронизации.

ЩИТО? причём тут вставки, слияние, и qsort?? radix не имеет никакого отношения к эти трём сортировкам.

Википедия переводит «radix sort» на русский как «сортировка вставками». Да и описание алгоритма то же самое.

Смысл radix сортировки в том, что эл-ты СРАЗУ расставляются по своим местам.

Ну и как ты можешь СРАЗУ поставить первый элемент на свое место, не зная ничего об остальных? В radix элементы сначала сортируются в отдельную область памяти, а потом уже оттуда «сразу» переносятся в исходную память.

Для radix надо всегда O(1) итераций, кроме случая сортировки бесконечных множеств.

Конечно, ведь время вставки зависит от размера множества. Если его зафиксировать, то и время станет O(1). Таким же образом можно говорить что сложность сортировки, скажем, 100 элементов слиянием оценивается как O(1).

ну сделать массив из 6и счётчиков ты не в состоянии?

Да, но это уже придется делать самому. Это, конечно, не сложно, но и не проще того цикла, что я написал.

не ускорит, но сделает программу более простой и масштабируемой.

Масштабируемой? в каком смысле? При добавлении нового warnLevel-а появится риск забыть увеличить число счетчиков. Или если, как ты говорил, enum придется заменить на структуру - придется переписывать и сортировку. Где масштабируемость?

кстати, вдвое быстрее при малых N. если слияние совместить с вставкой.

Ну приведи код, работающий «в 2 раза быстрее» приведенного мной. Слабо в это верится.

Я не делаю SP на объекты на стеке. А если точнее, не выделяю разделяемые объекты на стеке. Попутно отрываю руки тем, кто так делает.

ну а я могу делать SP на стеке и даже статически. УМВР.

При том, что ты не знаешь устойчивых выражений. Я для тебя даже объяснил, что вводное выражение «как правило» означает «обычно», «зачастую» и т.п. Даже ссылку привел. Нет, ты мне про какое-то «правило» продолжаешь талдычить.

потому-что тут не «обычно» и «как правило». Есть только «холодное» и «горькое», которые друг от друга никак не зависят.

не нужно. всё равно надо менять item_list->next для добавления.

Для добавления чего?

эл-та в список.

Конечно же, это весомая причина фейлить каждый 1000-ый запуск.

да. если фэйл заключается в десятикратных тормозах.

Этот _очень_ уникальный случай в жизни встречается _очень_ часто. Например, массивы строк произвольной длины. Надо ли говорить, что в доброй половине случаев приходится сортировать уникальные данные?

да, при поразрядной сортировке строк нужно O(m*n) операций, где m - средняя длинная строки. Если ты решил, что сложность другой сортировки будет O(n*log(n)) - ты ошибся. Проблема в том, что число сравнений будет таким, но каждое сравнение будет O(m), в итоге получаем O(m*n*log(n)), что заметно хуже radix-sort.

ЩИТО? причём тут вставки, слияние, и qsort?? radix не имеет никакого отношения к эти трём сортировкам.

Википедия переводит «radix sort» на русский как «сортировка вставками». Да и описание алгоритма то же самое.

у нас разные википедии.

1. radix-sort эо сортировка _размещением_. Например в твоём случае мы делаем шесть «корзинок» (buckets), и СРАЗУ кладём элемент с warnLev==3 в корзинку №3. Очевидно, нам нужно ровно N операций. Однако, никто не мешает нам вставлять элементы в список и сразу сортировать. Тогда достаточно _одной_ операции.

2. сортировка вставками работает иначе: в начале у нас есть отсортированный массив, и мы вставляем туда эл-т. На это требуется O(N) операций. Если у нас массив не сортированный, то мы считаем, что отсортирован массив a[0] из одного эл-та, и вставляем туда a[1] и так далее. Сложность получается O(N^2), но для малых N время небольшое.

Ну и как ты можешь СРАЗУ поставить первый элемент на свое место, не зная ничего об остальных? В radix элементы сначала сортируются в отдельную область памяти, а потом уже оттуда «сразу» переносятся в исходную память.

кто тебе сказал, что я ничего не знаю про остальные? Ну и да, для radix сортировки обычного массива в обычный массив действительно нужен буфер, в виде обычного массива той-же размерности. А в твоём случае - массив из 6и указателей на списки, которые и будут корзинками. Причём знать число эл-тов не нужно, ибо у тебя списки, а не массивы.

Конечно, ведь время вставки зависит от размера множества. Если его зафиксировать, то и время станет O(1). Таким же образом можно говорить что сложность сортировки, скажем, 100 элементов слиянием оценивается как O(1).

нет. Число операций для сортировки слиянием составляет менее 700 операций. (50 операций слияния списков по 2, 25 операций по слиянию списков по 4, 12 операций для слияния списков по 8 + 1 операция для слияния списка по 4, и т.д.). Число операций для radix-sort составляет ровно 100. При сортировке слиянием число операций примерно в 7 раз больше, потому-что 6 < log(100) < 7.

Масштабируемой? в каком смысле? При добавлении нового warnLevel-а появится риск забыть увеличить число счетчиков.

это вполне решаемо.

Или если, как ты говорил, enum придется заменить на структуру - придется переписывать и сортировку. Где масштабируемость?

причём тут структура?

кстати, вдвое быстрее при малых N. если слияние совместить с вставкой.

Ну приведи код, работающий «в 2 раза быстрее» приведенного мной. Слабо в это верится.

вставляй эл-т не в начало списка, а в нужное место. Если данные случайные, то надо просмотреть половину списка в среднем, это ровно вдвое быстрее. (если данные не случайные, то это ещё быстрее).

ну а я могу делать SP на стеке и даже статически. УМВР.

Ну хорошо, с чем тебя поздравляю. Но зачем?

Есть только «холодное» и «горькое», которые друг от друга никак не зависят.

ЯННП

Для добавления чего?

эл-та в список.

Добавляются элементы туда один раз при загрузке приложения. Еще до запуска второго потока.

да. если фэйл заключается в десятикратных тормозах.

Где ты их увидел?

в итоге получаем O(m*n*log(n)), что заметно хуже radix-sort.

логарифм в квадрат возводится. Какой ужас...

нет. Число операций для сортировки слиянием составляет менее 700 операций.

Тем не менее, это О(1).

причём тут структура?

Ну хорошо, какую масштабируемость ты имел в виду?

вставляй эл-т не в начало списка, а в нужное место.

Откуда я могу знать при инициализации списка, где это «нужное место»? Какой элемент будет иметь максимальный warnLevel при ближайшем вызове функции максимума? И что делать, когда максимальным станет другой элемент?