Здравствуйте, Паблик Морозов, Вы писали:

_DA>>А можно подробнее, какие именно заносы у с++ в плане реализации динамического массива?

ПМ>Например то, что он использует конструкторы копирования при ресайзе. Неподготовленного человека это может несколько "удивить", причем, как обычно бывает в случае C++, "удивление" наступит во время выполнения, а не на этапе компиляции, как это пытаются делать в нормальных языках.

А как ещё ты хотел? Не нравится, используй указатели или смарт поинтеры.

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

BFE>Здравствуйте, Паблик Морозов, Вы писали:

BFE>>>Речь о каком-то конкретном языке?
ПМ>>Естественно, ArrayList — это название класса.

BFE>Это стандартный класс?
Видимо речь идёт об ArrayList из первого дотнета либо аrrayList с java. List тут запутывает. Ещё больше запутает List<> из генериков.

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

MTD>Если человек научился кататься на велосипеде — он уже не разучится, в противном случае он никогда и не умел. Для меня незнание О-большого, равнозначно незнанию базовых алгоритмов, элементарного непонимания когда следует взять список, когда массив, а когда бинарное дерево.
Скажи честно, ты прочитал весь мой пост или только часть?

Я же развернул. Сейчас в разработке полно случаев, где О-большое просто не используется. Скажем, я программирую GUI. У меня тормозит рендеринг, но все алгоритмы чики-пики. Беда в том, что алгоритмы задают только что рисовать, а не как. Поможет ли мне О-большое повлиять на ветку "как", когда там "черный ящик"? Не поможет. И мне приходится оперировать совсем другими терминами. Использовать приемы оптимизации, связанные со спецификой рендерера.

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

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Здравствуйте, Sorc17, Вы писали:

S>>Ну ежели вы спрашиваете просто на понимание о чём вообще речь, то ладно.

ПМ>Ну я могу спросить, какая, например, сложность добавления элемента в конец ArrayList-а и в начало, и почему так получается.

O(n) в начало (из-за сдвига остальных элементов) и O(1) в конце? Перевыделение памяти, если вдруг свободные элементы в конце закончились, не учитываем. Угу?

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

A>А как ещё ты хотел? Не нравится, используй указатели или смарт поинтеры.

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

14.03.2012 19:59, мыщъх пишет:

> если алгоритмическая сложность O(N!), то это не масштабируется в
> принципе и потому разрабатывать гибкую архитектуру смысла нет, т.к. ей
> все равно не удастся воспользоваться. если алгоритмическая сложность
> O(N), то имеет смысл писать так, чтобы программа "подхватывала" как
> можно больше ядер ЦП.
А если N=5?
А с квадратом, кубом и т.д. ядра ЦП не надо использовать?

SD>Что-то вас занесло. Немало современных кодогенераторов довольно тупо поступает — генерирует пары test reg, const -> jz caseconst.
visual c++ с незапамятных времен (версия 6.0 умела уже) умеет конвертировать набор таких пар в бинарный поиск с помощью cmp & ja/jb
получается что-нть вроде
cmp reg, 10
ja above10
cmp reg, 5
ja above5
; тут обработка от 0 до 5
jmp exit
above5:
; тут обработка от 6 до 10
jmp exit
above10:
и так далее

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

DB>Естественно нет. Никогда и нигде задачи в виде "подсчитай алгоритмическую сложность этого куска кода" не было. С другой стороны, алгоритмическая сложность она везде. Особенно в правильном выборе структуры данных и работой с большими объёмами. Ещё у алгоритмической сложности есть одно замечательное свойство. Если программист профессиональный и понимает (не помнит назубок!) алгоритмы и структуры данных, то он не думает об алгоритмической сложности и пишет качественный быстрый код. Если программист слабый, то он тоже никогда не думает об алгоритмической сложности, но пишет тормознутое глючное фуфло.
Что вы так с быстротой возитесь? Иногда понятность алгоритма важнее алгоритмической сложности. Вот пример один — у меня сейчас есть место, где О с хвостиком, то есть тета(N) хотя можно было сделать О с хвостиком от 1. А если брать О без хвостика, то там будет умножение на константу еще, которая сравнима с типичным N, то есть у меня де факто чуть ли не куб для типичного N. При этом я еще не стад делать неблокирующий алгоритм, чтобы сделать попроще. Просто у меня типичный N=1, иногда 2, максимальный N, который потянет одна машина — 10, абсолютно максимально возможный на одной машине, без выноса узкого места на черти какой кластер — 100. И вот скажите мне одну вещь. Правильно ли я понимаю, что на моем месте так называемый хороший мегасеньер программист 20 лет с годом коммерческого и десятью лет некомменческого опыта — просто обязан переписать совершенно некритичное по скорости место гораздо более продвинуто, но за О(1), потратив на это в 10 раз больше времени (а то и во все 100, ибо чтоб не допустить запутывание кода, еще и сделать кодогенератор, в том числе и тестов)?
Рассказываю два случая диких тормозов с миллионом записей, с O(N) не связанных. В одном случае весьма квалифицированный специалист, который в том числе и проводит собеседование, спрашивая О нотацию, забыл один индекс для редкого специфического случая сделать. В результате периодически один запрос подвешивал всю систему. Причину я потом лично я нашел, и как то претензий к автору не имею — со всеми бывает. Когда тормоза заключены в одном компактном месте кода — это не проблема вообще!
В другом случае в цикле перебора, который О(N), и по другому никак — встретилась утечка памяти, в результате через полмилиона записей пошел такой своп, что уже и не завершить это до конца. Больше я на своей практике тормозов не припомню.
Оптимизации делать приходится периодически. Техники, которые довелось использовать, в порядке важности:
1) Кеширование;
2) Предвыборка данных;
3) Распараллеливание.
Учитывая то, что числодробилки я не пишу, как и какие сверхсложные алгоритмы — ни разу не припоминаю случая, чтоб мне О(N) требовалось в жизни. Я прекрасно понимаю, что во всех учебниках на первом месте стоит выбор алгоритма. Но вот что то мне подсказывает, что 90% разработчиков ПО крайне редко разрабатывают какие либо нетривиальные алгоритмы, которые являются узким местом системы. И если я для каждого алгоритма буду априори делать черти какие оптимизации, ибо можно сделать оптимальнее, но за счет большей сложности алгоритма — я сорву все сроки и напложу неимоверное количество трудновоспроизводимых багов.
Нет лучших алгоритмов и худших! Все зависит от задачи, всегда it depends. Брутфорс алгоритмы тоже имеют право на жизнь, у них есть неоспоримое преимущество — четко понятно как они работают, с одного взгляда! Потому selection sort может быть лучше как пузырька, так и quick sort.
Чем, блин, алгоритмами мыслить, лучше б про расширяемость, модифицируемость и отсутствие копипасты думали. А то, блин, каждый цикл оптимизируют, экономят на вызовах процедур, пишут все в одном методе, при этом вообще без проектирования — все данные пихаем прямо в контролы, ибо оптимально, памяти меньше жрет, никакого разделения на слои, бакэнд знает про UI и активно вызывает соответствующие методы — это тоже типа оптимально! При прочих равных всегда предпочел бы того, кто городит всегда супернеоптимальные алгоритмы, но все косяки и тормоза у него в одном месте, которое при необходимости легко находится. Чем тех, у кого все структуры данных и сложность от зубов отскакивает, и каждый раз это все копипастит заново.
Нет слов блин, относительно этого российского образования — чем прививать эту склонность к оптимизации, лучше б эти О вообще из вузовской программы выкинули, но взамен от склонности к копипасте избавили. Да что там к копипасте, хоть бы форматировать текст бы научились, хоть бы про code convention иногда задумывались, а не хреначили в чисто своем стиле. И еще было б неплохо чтоб приучились часто коммитить в репозиторий, а не делать что неделями, боясь панически что сломать, а потом у них винт грохается и ни хрена в результате не сделают. Хрен с ней, с абстракцией и тому подобное — это с опытом придет. Нет, блин, это все не обязательно, главное чтоб O от зубов отскакивало и на бумажке сортировки с закрытыми глазами писал — основной показатель квалификации.

E>И вот скажите мне одну вещь. Правильно ли я понимаю, что...

Нет, абсолютно не правильно. Остальное комментировать смысла нет.

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

SD>Индусы так работают. Работают успешно — в том смысле, что продукты выпускаются, бизнесу выгодно.

Как минимум надо знать о существовании такой табличке , и что в ней написано. Это уже немало (судя по ветке).

E>Оптимизации делать приходится периодически. Техники, которые довелось использовать, в порядке важности:
E>1) Кеширование;
E>2) Предвыборка данных;
E>3) Распараллеливание.

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

M>Как минимум надо знать о существовании такой табличке , и что в ней написано. Это уже немало (судя по ветке).

Дык это. Я им говорю. Вот, говорю, индусы, вот табличка. Как заводите переменную-коллекцию — вот сюда, в табличку, смотрите.

Знать определения O большого и т.п. не так важно как понимание, вот задание с реального собеседования


Индусу Рамачарджану дали задание написать функцию, удалить все проблелы из строки (ANSI). Он быстро выкатил вариант:

void delete_spaces(char* str)
{
for(int i = 0; i < strlen(str); i++)
{
if(str[i] == ' ') { strcpy(str + i, str + i + 1); i--; }
}
}

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

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

BFE>>>>И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
MTD>>>Ну вот как, как, такое может придти в голову?
BFE>>Как, как ... Из практики!
MTD>>> Я даже не об алгоритмах говорю, а о несчастных юзерах.
BFE>>Что с ними не так? Их последнее время расплодилось столько, что в 32 бита не влезают.
MTD>Да уж... Может чем нибудь другим стоит заняться?

Вы о чём?

MTD>>> Однозначно теперь первый вопрос про О-большое, ну после виртуального деструктора
BFE>>Ну причём тут О-большое
MTD>Сразу позволяет понять стоит общаться дальше или нет. После этой темы я это хорошо понял.

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

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

MTD>>>Количество шагов может быть небольшим, а время выполнения огромным по сравнению с поставленными временными рамками. Так что это важно.
BFE>>Нет. Это значит, что для разных задач нужны разные алгоритмы.
MTD>Молодец, мозг включился

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

BFE>>если никаких проблем, значит и цикл можно развернуть по тому же принципу.
MTD>Можно в некоторых случаях.

И, как оказалось

Автор: _DAle_
Дата: 15.03.12

, далеко не во всех случаях можно для switch построить таблицу переходов за O(1).

BFE>>А причем тут цикл обработки 100 гигабитного потока?
MTD>А при чем тут лист бокс?
А при чем тут алгоритмическая сложность?

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

_DA>Я вот прямо на рсдне однажды жаловался уже на qt: http://rsdn.ru/forum/cpp.qt/3193572.1.aspx

Автор: _DAle_
Дата: 29.11.08

. Может подойдет в качестве какого-то примера.

Я вот тут подумал, что это отличный пример того, что все любители О-больших "идут лесом", потому что у qSort сложность O(n log n). Вот они и применили её... А результат несколько неожиданный.

15.03.2012 13:39, minorlogic пишет:

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

З.Ы. Вот что поражает, так это некорректная постановка задачи, а потом
удивление, а почему этот код еще сам и деньги мне на счет не кладет.

Вы еще раз подтвердили , как замечательно работает эта задача для оценки кандидата. Спасибо.

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

M>Знать определения O большого и т.п. не так важно как понимание, вот задание с реального собеседования

M>
M>Индусу Рамачарджану дали задание написать функцию, удалить все проблелы из строки (ANSI). Он быстро выкатил вариант:

M>void delete_spaces(char* str)
M>{
M> for(int i = 0; i < strlen(str); i++)
M> {
M> if(str[i] == ' ') { strcpy(str + i, str + i + 1); i--; }
M> }
M>}

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

А оценка сложности приведённого куска какова? У меня: О(n+n*logn).
Только я не много понимаю в данной теме и про logn совершенно не настаиваю.

По вопросу как улучшить (код писать некогда):
1. цикл с выходом по 0 == str[i],
2. два индекса — откуда читать символ и куда его писать.
3. индексы увеличиваем на каждой итерации, а индекс "откуда читать" дополнительно увеличиваем на 1, если он указывает на пробел.

Получим O(n). Так?

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

К>А оценка сложности приведённого куска какова? У меня: О(n+n*logn).

О(n^2).

К>Получим O(n). Так?

Мысли в правильном направлении.