Re[8]: Алгоритмическая сложность и прочее - О работе

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

S>Помнится, я на 2 курсе спокойно асилил как считать эту самую сложность и запросто решал на экзаменах и зачётах любые задачи с этим связанные. И с тех пор так и не вспоминаю про это, так за за все эти годы мне это ни разу не понадобилось.

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

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

Ну и касаемо темы: спрашивать про О-теорию на собеседовании глупо и в корне не верно на мой взгляд. А спрашивать нужно конкретно по теме — если нужен специалист по работе с базами данных нужно спрашивать какие методы оптимизации конкретно он применял или знает, что лучше или хуже на его взгляд и так далее. Оптимизацию SQL запроса никакой О-теорией нормально не описать.

S>Неужто на ваших фирмах с бугалтерий@документоообротом хоть одному программисту хоть раз за всю историю разработки понадобилось посчитать алгоритмическую сложность?

Естественно нет. Никогда и нигде задачи в виде "подсчитай алгоритмическую сложность этого куска кода" не было. С другой стороны, алгоритмическая сложность она везде. Особенно в правильном выборе структуры данных и работой с большими объёмами. Ещё у алгоритмической сложности есть одно замечательное свойство. Если программист профессиональный и понимает (не помнит назубок!) алгоритмы и структуры данных, то он не думает об алгоритмической сложности и пишет качественный быстрый код. Если программист слабый, то он тоже никогда не думает об алгоритмической сложности, но пишет тормознутое глючное фуфло.

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

BFE>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность.

Это оно и есть.

BFE>Вот, например, кто-нибудь рассуждает так: "Окно в первом прототипе будет обрабатывать 5 сообщений. Количество сообщений по мере развития приложения может увеличится до сотни. Если мы напишем switch(номер сообщения), то алгоритмическая сложность составит O(n).

Нет, оно составит О(1) и это очень круто, если так можно сделать, O(n) будет если будешь "форичить".

BFE>Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше.

O(log n) — существенно больше O(1), но меньше O(n). Это при условии, что добавление/удаление сообщений будет редко.

BFE>Что-ж, заведём массив хранящий пару (номер сообщения, обработчик), отсортируем его по номеру сообщения и будем применять бинарный поиск! Тааак... теперь надо выбрать правильный алгоритм сортировки..."

И на ровном месте превратим наш алгоритм в O(n * log n), что существенно больше O(log n).

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

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

MTD>>Жду когда пойдут темы: "Не смог написать свое имя без ошибок, просто давно не писал, раньше проблем не было, надо будет научусь заново".
MM>А что, может и забывали бы и отучались, если бы имя не требовалось часто в повседневной жизни.

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

MM>Интересно другое. Ну, вот знаю, что это за сложность, могу подсчитать. Но в работе не пригождается, не было задач с необходимостью считать сложность. Теперь думаю, может значение O-большое действительно преувеличено?

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

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

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

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

BFE>Интересно. Во всех случаях? Даже если константы идут не по возрастанию?:

Нет конечно, switch — это почти всегда линейный поиск. Другое дело, что для тех случаев, когда используется swithc (десяток вариантов, набранных ручками) что-то более "умное" сожрёт больше времени. Это, кстати, хороший пример того, зачем надо знать про выч. сложность и почему на 10 кейсах можно использовать switch, а на 10000 — нет, даже если язык позволяет.

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

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

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

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

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

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

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

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

Posted via RSDN NNTP Server 2.1 beta

Здравствуйте, 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 от зубов отскакивало и на бумажке сортировки с закрытыми глазами писал — основной показатель квалификации.

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

BFE>>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность.
MTD>Это оно и есть.

Нет. Время и количество шагов могут быть не связаны.

BFE>>Вот, например, кто-нибудь рассуждает так: "Окно в первом прототипе будет обрабатывать 5 сообщений. Количество сообщений по мере развития приложения может увеличится до сотни. Если мы напишем switch(номер сообщения), то алгоритмическая сложность составит O(n).
MTD>Нет, оно составит О(1) и это очень круто, если так можно сделать, O(n) будет если будешь "форичить".
оно — это сложность?

поиск

switch(x)
{
   case 1:
   break;
   case 2:
   break;
   case 3:
   break;
   ...
   case n:
   break;
}

"равносилен", так как количество операций сравнений не меняется:

for(i = 0; i < n; i++)
  if ( x == a[i] ) 
    break;

Разве нет?

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

BFE>>Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше.
MTD>O(log n) — существенно больше O(1), но меньше O(n).

При n равным 100 ?

MTD>Это при условии, что добавление/удаление сообщений будет редко.

BFE>>Что-ж, заведём массив хранящий пару (номер сообщения, обработчик), отсортируем его по номеру сообщения и будем применять бинарный поиск! Тааак... теперь надо выбрать правильный алгоритм сортировки..."

MTD>И на ровном месте превратим наш алгоритм в O(n * log n), что существенно больше O(log n).Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность.

Похоже я вас "запутал". Я не предлагал сортировать очередь входящих сообщений. Пример неудачный. Извините.

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

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

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

Знать определения 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--; }
}
}

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

BFE>Видите, Аноним не может вычислить алгоритмическая сложность этого своего творения (а только даёт оценку):

А>>

А>>public static void Sort(int[] source, int firstArrayIndex, int secondArrayIndex)
А>>{
А>>    int i = firstArrayIndex, j = secondArrayIndex, k = -1;
А>>    while (true)
А>>    {
А>>        if (source[i] > source[j])
А>>        {
А>>            if (k == -1) k = i;
А>>            int temp = source[i];
А>>            source[i++] = source[j];
А>>            source[j++] = temp;
А>>        }
А>>        else
А>>            if (++i == j)
А>>                return;
А>>        if (j == source.Length || i == secondArrayIndex)
А>>        {
А>>            if (i == secondArrayIndex)
А>>                Sort(source, secondArrayIndex, j);
А>>            if (k + 1 < secondArrayIndex)
А>>                Sort(source, k + 1, secondArrayIndex);
А>>            return;
А>>        }
А>>    }
А>>}
А>>

BFE>а вы можете ?
Этот код, во-первых, содержит ошибки типа выхода за пределы массива, а, во-вторых, вообще не делает то, что должен был (сливать два отсортированных массива).
Тест вот такой: Sort([2,3,4,5,1,2,3,4], 0, 4).
Далее, он использует естественно не O(1) памяти, так как глубину рекурсии здесь можно сделать хоть O(n), а стек — это естественно та же память, тест для такого вырождения примерно такой:
Sort([1,2,3,4,5,0], 0, 5)
Считать здесь сложность при наличии вороха ошибок — это издевательство ) При одних изменениях в алгоритме здесь будет одна сложность, при других — другая.

BFE>И часто занимаетесь этим на практике? Сомневаюсь.
Занимаюсь этим на практике. Не часто, но бывает.

BFE>ЕМНИП, у Кнута есть строчки, что для некоторых алгоритмов вычисление алгоритмической сложности — сама по себе задача не простая.

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

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

_DA>>Двоичный поиск используется для оптимизации таких switch'ей.

ПМ>Во-первых, тут кто-то что-то говорил про таблицу переходов и O(1), во-вторых, было бы интересно взглянуть на компилятор, который сам конвертирует свитчи в двоичный поиск, потому что что-то я сомневаюсь в целесообразности такой операции.

http://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem

14.03.2012 16:05, Stanislav V. Zudin пишет:

> BFE>Расскажите, пожалуйста, про практику применения этого знания. В
> каком контексте и для каких задач вы рассчитывали алгоритмическую сложность?
>
> Вот <http://rsdn.ru/forum/alg/4659539.1.aspx>, например, хороший пример
> задач.
> Алгоритм с O(N) превратить в O(N^3) за счет неправильно выбранных
> структур данных — легко.
Это все хорошо, но где ответ на поставленный вопрос: "для каких задач вы
рассчитывали алгоритмическую сложность?"
Ну и по тем задачам, что по ссылке, чтобы рассчитать их сложность в
терминах O в зависимости от алгоритмов нужно очень нехило повозиться,
причем нафиг это никому не надо.

Posted via RSDN NNTP Server 2.1 beta

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

S>Вот уже который раз лазаю по темам про собеседования и часто вижу там слова в духе "кандидат не смог почитать сложность ля-ля-ля". Неужто на ваших фирмах с бугалтерий@документоообротом хоть одному программисту хоть раз за всю историю разработки понадобилось посчитать алгоритмическую сложность?

S>Помнится, я на 2 курсе спокойно асилил как считать эту самую сложность и запросто решал на экзаменах и зачётах любые задачи с этим связанные. И с тех пор так и не вспоминаю про это, так за за все эти годы мне это ни разу не понадобилось.

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

Ну как, как, можно забыть, что a(b + c) = ab + ac, или что проход по массиву n элементов имеет сложность O(n) ?!!

S>Помнится, я на 2 курсе спокойно асилил как считать эту самую сложность и запросто решал на экзаменах и зачётах любые задачи с этим связанные. И с тех пор так и не вспоминаю про это, так за за все эти годы мне это ни разу не понадобилось.

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

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

S>На любом этапе тут можно посчитать сложность, только не нужно, потому что это не решит проблему, а значит не нужно

Жесть!

Теперь спрашивать про о-большое буду в обязательном порядке.

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

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

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

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

Если я правильно помню, то ArrayList это просто список, но с который можно обращаться как будто он массив. Так что добавление и удаление из него — это просто поменять парочку ссылок.

"Спасибо, мы вам перезвоним в ближайшее время?"

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

НЕД. В switch это просто jump по адресу.

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

BFE>И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?

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

Здравствуйте, мыщъх, Вы писали:

М>да-да. хэш таблицы. поиск по словам post hashmap dos рулит. очень интересная дыра. потому что никому и в голову не пришло просчитать наихудший сценарий развития событий.

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

З.Ы. Во избежании осуждений в разжигании национальной розни считаю нужным сообщить, что под "индусами" (в кавычках) я подразумеваю некоторый класс программистов, преимущественно на C/С++/Java/C#, но никак жителей Индии, или людей, исповедующих Индуизм.

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

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

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

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

S>>Всё же при switch будет N сравнений, где N это количество кейсов. Пруф:

D>в упор не вижу пруфа

D>У тебя всего лишь 2 кейса и дефолт. Понятно, что в этом случае оптимальнее использовать сравнения.

Не видь дальше, что я тут тебе ещё могу сказать.

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

V>НЕД. В switch это просто jump по адресу.

Т.е. что-то вроде этого

switch(enumValue) -> jump (case[enumValue])

К>Оцениваем всегда самый плохой случай? Тогда должно быть O(n*n*X), где X явно не n, т.к. strcpy вызывается n раз, но каждый раз обрабатывает строку на 1 меньше.
O(n(n-1))=O(n^2)

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

К>Оцениваем всегда самый плохой случай?

Не всегда, обычно смотрят на среднюю и самую плохую.

К> Тогда должно быть O(n*n*X), где X явно не n, т.к. strcpy вызывается n раз, но каждый раз обрабатывает строку на 1 меньше.

x в этом случае = 0.5, оценка сложности от этого не меняется.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

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

MTD>>... или что проход по массиву n элементов имеет сложность O(n) ?!!

S>Зачем это знать? Написал foreach и всё. Какая разница какая там у него сложность?
ну как бы последняя крупная дос дыра как раз и связана с тем, что для передачи аргументов web-программисты используют hashmap без понимания как оно работает и пацаны придумали как валить мощные сервера даже со слабого модема на 33,600. если в худшем случае у нас квадратичная сложность, то это означает, что покупкой оборудования проблему не исправить.

> А если начала тормозить выборка для отчёта, сделал постраничную разбивку и всё.
жуть.

> на любом этапе тут можно посчитать сложность,
> только не нужно, потому что это не решит проблему, а значит не нужно

если сложность O(N), то да. если сложность O(N^2), то оборудования покупать придется много и потребуется принципиально иная архитектура. а если сложность O(N!), то программиста нужно забить камнями (кстати, такую сложность имеет задача коммивояжера при решении ее "в лоб").

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

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

BFE>Расскажите, пожалуйста, про практику применения этого знания. В каком контексте и для каких задач вы рассчитывали алгоритмическую сложность?

Из недавнего. Упрощенно.
Дано: кеш множества объектов (2-3 миллиона), у объектов есть тип, временная метка и идентификатор. В кеш добавляются объекты разных типов в реальном времени.
Задача: организовать быструю выборку идентификаторов по критериям тип-время, например, выбрать объекты типа А с Даты1 по Дата2.
Решение: поскольку временная метка может только увеличиваться, то можно использовать упорядоченный массив пар метка времени-идентификатор. Массив предпочтительней упорядоченных деревьев, так как при том же скорости поиска O(log n) получаем более быстрое добавление в конец — O(1) (важный момент — если бы не было гарантий на возрастание меток времени, то дерево было бы предпочтительней). Правда есть еще хеш-таблица, которая в лучшем случае даст O(1), но за счет повышенного потребления памяти — а объектов слищком много для этого, значит все может закончится печально — O(n). Добавим структуру данных хранящую пару тип-массив меток времени и задача будет решена. Типов фиксированное количество, поэтому не стоит задача их добавления, а значит без разницы использовать упорядоченный массив или дерево — скорость поиска одинакова. Так, но ведь количество типов у нас меньше десятка, а значит просто пробежать по массиву — O(n) на таком объеме точно предпочтительней поиска в дереве. О, да ведь представим тип как перечисление и будем получать массив свичом — получим O(1)!
Итого: O(1) на добавление объекта и O(log n) на выборку — удовлетворительно.

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

_DA>http://www.codeproject.com/Articles/100473/Something-You-May-Not-Know-About-the-Switch-Statem

Неплохо, бинарный поиск засчитан

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

BFE>Это значит, что класс описан в стандарте или (если у языка нет стандарта) в документации библиотеки (фрейворка), которая для данного языка является стандартом де-факто.

Да, стандартный.

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

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

BFE>>>Да на пьянке чем только программисты не занимаются. Вопрос не в оценке, а в точном подсчёте.
M>>Я это не понял.

BFE>Ради забавы я тоже могу заняться оценкой алгоритмической сложности.

BFE>>>Именно, что в соответствующей литературе, а не на практике.
M>>Не в вашей практике, уточняю.

BFE>Вот мне и интересно, когда это практики рассчитывают (а не пользуются справочными данными) сложность.
BFE>Во всей ветке только мыщъх здесь привёл нормальный пример из практики.

Я вот прямо на рсдне однажды жаловался уже на qt: http://rsdn.ru/forum/cpp.qt/3193572.1.aspx. Может подойдет в качестве какого-то примера.

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

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

З>>Я вообще никогда в жизни не слышал о таком понятии, как "алгоритмическая сложность". Нигде — ни в институте, ни на работе, ни в книжках, ни в интернетах, ни от коллег.

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

Ну так я и про Алгоритмическую Легкость первый раз слышу.

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

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

S>>>На любом этапе тут можно посчитать сложность, только не нужно, потому что это не решит проблему, а значит не нужно

MTD>>Жесть!

Теперь спрашивать про о-большое буду в обязательном порядке.

BFE>Расскажите, пожалуйста, про практику применения этого знания. В каком контексте и для каких задач вы рассчитывали алгоритмическую сложность?

Вот, например, хороший пример задач.
Алгоритм с O(N) превратить в O(N^3) за счет неправильно выбранных структур данных — легко.
Достаточно использовать "Форыча"(с) не думая.

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

M>Вы что пишите то ? документооборот или ?
Он не пишет — он программистов собеседует ну и билды деплоит

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

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

M>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается.
M>>Но с чего вы взяли что тут все документооборот клепают ?

BFE>А в какой практической области это надо?

Хм, на мой взгляд почти везде надо, чтобы не написать что-нибудь критичное по скорости со сложностью O(n^3), где достаточно O(nlogn). Но если нужны примеры..
1. Я довольно долго работал в продуктовой компании, выпускающей, например, софт для проектирования дорог или софт для геодезистов. Так там всякое бывало, начиная от нахождения точек пересечения тысяч кривых, до всяких примитивных поисков объектов по различным критериям. Как раз вот приходилось оптимизировать код после людей, зараженных преждевременной пессимизацией. И ведь работало все нормально до поры, до времени, пока проекты у пользователей не набирали достаточной критической массы, когда всякие квадратичные алгоритмы не выстреливали им по конечностям.
2. Сейчас вообще занимаюсь бизнес-приложениями.. У нас тут, например, есть оптимизирующий транслятор из DSL во, в конечном счете, SQL-запросы. Думаешь, там алгоритмики нет? Да что там.. даже, чтобы отчеты со сложными вложенными иерархиями через дурацкий JasperReports строить, пришлось повозиться c оптимизацией.

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

M>>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается.
M>>>Но с чего вы взяли что тут все документооборот клепают ?
BFE>>А в какой практической области это надо?
M>Начиная от оптимизации работы с большим к-вом данных, заканчивая 3д графикой. Или это ирония ?

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

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

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

W>Точно знаешь? И в реализацию вычисления размеров/ отрисовки лазал?
Я знаю достаточно много про различные листбоксы.
W>Да и что ж у него с ростом количества контента все тормозить начинает, если оно хотябы логарифмично, а то и вообще константа, как тебе кажется?

Я не возьмусь оценить алгоритмическую сложность отрисовки литбокса, но обычно она не константа, не логарифм и не линейность. Видел реализации, где количество операций было приблизительно O(n!).
Но это не важно. Важно, что решение принятое вами о кастомизации основано не на оценке алгоритмической сложности, а потому, что "у него с ростом количества контента все тормозить начинает".

14.03.2012 18:45, qxWork пишет:

> Например пониманием того, что операции с этим самым листбоксом в лучшем
> случае линейны по количеству элементов (а их дохрена).
Достали вы уже этими листами. Вот вам задачка "оцените сложность" EM
(Expectation Maximization) или SVM (Support vector machine) алгоритмов в
терминах O.
Неужели вы не пишете ничего сложнее, чем использование листа?

Posted via RSDN NNTP Server 2.1 beta

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

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

BFE>Ну понятно. Поиск и сортировка. Это теория. Но неужели вы рассуждали на практике так: "Этот алгоритм требует O(N^5) операций сложения. Это слишком много. Будем искать другой алгоритм и пока не найдём — ничего имплементировать не будем"?

Не только поиск и сортировка, ну да не важно. Если я вижу, что ассимптотика у алгоритма такая, что он неприменим для реальных объемов данных, которые будут возникать на практике, то зачем такой алгоритм реализовывать? Насчет искать алгоритм.. для распространенных задач все алгоритмы давно известны, остается только выбрать тот, который удовлетворяет требованиям и требует минимального количества затрат. То есть понятно, что если у нас выбор между двумя алгоритмами O(n^2) и O(nlogn), есть некая функция, которая должна выполняться, не сильно раздражая пользователя, и работать с сотнями тысяч объектов, то выбора особо не остается.

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

BFE>Ничего не понял. Преждевременная оптимизация не может привести к квадратичным алгоритмам там, где их быть не должно. А преждевременная пессимизация это вообще — как?

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

_DA>>2. Сейчас вообще занимаюсь бизнес-приложениями.. У нас тут, например, есть оптимизирующий транслятор из DSL во, в конечном счете, SQL-запросы. Думаешь, там алгоритмики нет? Да что там.. даже, чтобы отчеты со сложными вложенными иерархиями через дурацкий JasperReports строить, пришлось повозиться c оптимизацией.

BFE>Вы не путаете оптимизацию с оценкой сложности? Это разные понятия.

Я говорю про алгоритмическую оптимизацию, она непосредственно связана с оценкой асимптотики алгоритмов, ну и с O-нотацией, которой эта асимптотика выражается.

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

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

П.с. сам ни когда не знал как оно реализовано. Но если бы сам реализовывал, что-то вроде таблицы обязательно бы сделал — ибо сам по себе свич в коде — это некая форма таблицы.

Как один из критериев поиска кандидата — это наличие хоть какой-то фантазии.

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

BFE>Видите, Аноним не может вычислить алгоритмическая сложность этого своего творения (а только даёт оценку):

BFE>а вы можете ? И часто занимаетесь этим на практике? Сомневаюсь.

Есть такой метод — маляру дают задание покрасить 10 метров забора, он красит за 10 минут. Потом ему говорят покрасить 50 метров, он красит за 2500 минут, потом 100 метров, он красит за 10000 минут. Ага! По О(n^2) работает!

....

Продолжение. А почему? Выполняют анализ алгоритма — замечают, что он постоянно бегает к бочке с краской. Ок, ставят бочку на тележку, тележка едет рядом. Новые замеры: 10 метров — 10 минут, 50 метров — 50 минут, 100 метров — 100 минут. Вот другое дело — O(n)

Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Во-первых, тут кто-то что-то говорил про таблицу переходов и O(1), во-вторых, было бы интересно взглянуть на компилятор, который сам конвертирует свитчи в двоичный поиск, потому что что-то я сомневаюсь в целесообразности такой операции.
Это частный случай, нормальные свичи идут по enum-ам, где нумерация идет от 0 до N. Тут вообще не нужен поиск.

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

BFE>>

Я не возьмусь оценить алгоритмическую сложность отрисовки литбокса, но обычно она не константа, не логарифм и не линейность. Видел реализации, где количество операций было приблизительно O(n!).
MTD>Мне как-то не верится в это. Факториал очень быстрорастущая функция, уже на 15 элементах компьютер встал бы на колени совершая аж 1 307 674 368 000 бессмысленных действий.

Если я правильно помню, то с 10000 строк работать было уже невозможно. Добавление новой строки занимало несколько минут. Ну не O(n!). Ну и что это меняет?

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

ПМ>Вообще, склонность к использованию монструозных IDE редко когда хорошо характеризует профессиональный уровень программиста.

Ага vim ваше все.

П.с. ненавижу этот редактор.

П.п.с. почти год работал без отладчика. IDE было тупо для написания кода (можно было просто фаром редактировать, разницы практически не было. Больше нет желания работать с такими проектами. Если предложат еще раз подобное — откажусь.

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

Можно просто взять нормальный язык программирования с нормальным REPL-ом и не мучить себя ни vim-ом, ни многогигабайтным говном. Хотя на счет vim-а — это дело вкуса, кому-то нравится vim, кому-то другие редакторы.

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

BFE>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность. Вот, например, кто-нибудь рассуждает так: "Окно в первом прототипе будет обрабатывать 5 сообщений. Количество сообщений по мере развития приложения может увеличится до сотни. Если мы напишем switch(номер сообщения), то алгоритмическая сложность составит O(n). Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше. Что-ж, заведём массив хранящий пару (номер сообщения, обработчик), отсортируем его по номеру сообщения и будем применять бинарный поиск! Тааак... теперь надо выбрать правильный алгоритм сортировки..."

Ага. Видел таких гениев, что за деревьями не видят леса. Убъют две трети времени проекта на оптимизацию того, что в итоге либо не окажет никакого влияния на производительность, а то и будет вообще выкинуто, и прохлопают очевиднейшее бутылочное горлышко, в котором наговнокодят даже не O(n^2), а O(n^n). Специалисты блин, и все как один с дипломами, гномиков с закрытыми глазами считают и сортировки пальцами левой ноги на бумажке пишут.

Всё же при switch будет N сравнений, где N это количество кейсов. Пруф:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int main (int argc, char* argv[]) {
    int a = atoi(argv[1]);
    switch (a) {
        case 2:
            printf("2");
            break;
        case 5:
            printf("5");
            break;
        default:
            printf("Unexpected");
            break;
    }
    return EXIT_SUCCESS;
}

$ gcc -S -O3 1.c -o 1.s
$ cat 1.s
    .file    "1.c"
    .section    .rodata.str1.1,"aMS",@progbits,1
.LC0:
    .string    "Unexpected"
    .section    .text.startup,"ax",@progbits
    .p2align 4,,15
    .globl    main
    .type    main, @function
main:
.LFB30:
    .cfi_startproc
    subq    $8, %rsp
    .cfi_def_cfa_offset 16
    movq    8(%rsi), %rdi
    movl    $10, %edx
    xorl    %esi, %esi
    call    strtol
    cmpl    $2, %eax
    je    .L3
    cmpl    $5, %eax
    je    .L8
    movl    $.LC0, %edi
    xorl    %eax, %eax
    call    printf
.L5:
    xorl    %eax, %eax
    addq    $8, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret
.L3:
    .cfi_restore_state
    movl    $50, %edi
    call    putchar
    jmp    .L5
.L8:
    movl    $53, %edi
    call    putchar
    .p2align 4,,3
    jmp    .L5
    .cfi_endproc
.LFE30:
    .size    main, .-main
    .ident    "GCC: (GNU) 4.6.1 20110908 (Red Hat 4.6.1-9)"
    .section    .note.GNU-stack,"",@progbits
$

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:
и так далее

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

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

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

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

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

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

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

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

О(n^2).

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

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

void delete_spaces(char* str)
{
  if ( NULL != str ) 
    *std::remove(str, str + strlen(str), ' ') = '\0';
}

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

A>>Там цель отсеять, поэтому он такие вопросы специально накапливает.
V>Только вот кого отсеять..?

Всех, очевидно.

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

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

S>>>Да, и при этом я ни разу не видел, чтобы ее применяли к памяти. Особенно собеседователи.

_DA>>Остается только сделать вот так

Ну, я даже не знаю, привести пример что ли? http://en.wikipedia.org/wiki/Quicksort

S>Ну вот тут три темы было, кажется, про проверку навыков при собеседовании. Везде мучительно обсасывали сложность в смысле скорости, и никто ни разу не упомянул память.

Я упоминал

http://rsdn.ru/forum/job/4660501.1.aspx

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

S>>Слушайте, а что вы так уперлись в это O()? Мне представлялось, что расходы памяти не менее существенный вопрос, а для памяти, кажется, даже буквы нет общепризнанной?

M>Может в память реже упираются ?

А хрен его знает. Я по работе упираюсь как раз в память несколько чаще, чем в вычисления. Вообще в контексте собеседований у меня ощущение, задачки про O(труляля) дают потому, что это удобная теория, которую знает принимающий, а со стороны памяти просто нет ничего красивого, что можно было бы удобно спросить на собеседовании.

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

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

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

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

ПМ>Обычно это просто маркер говнокодеров. Я не встречал нормальных программистов, у которых были бы с этим проблемы, тем более, что в задачах с бугалтерий@документоообротом вся алгоритмическая сложность сводится к выбору между тремя вложенными циклами или каким-нибудь более эффективным решением. Зато говнокодеры, которые любили писать какую-нибудь лапшу без понимания, как оно работает, почти никогда не знали, что такое алгоритмическая сложность.

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

Считать сложность как таковую — нет. Но один раз в жизни алгоритмы пригодились. Где-то пол-года назад в нашем внутреннем проекте загрузка данных стала уж очень долгой, по кейсу от юзеров ~ 5 часов. Но я же краем уха помнил, что есть всякие разные поиски. Полчаса гугления и исправление в пару строк, с заменой поиска на бинарный поиск снизило это время до ~1-2 минут. Я потом месяц ходил и собой гордился, особенно с учётом того, что я простой кодерок, а исходно код писали наши ведущие программеры.

S>Помнится, я на 2 курсе спокойно асилил как считать эту самую сложность и запросто решал на экзаменах и зачётах любые задачи с этим связанные. И с тех пор так и не вспоминаю про это, так за за все эти годы мне это ни разу не понадобилось.

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

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

З>Ну так я и про Алгоритмическую Легкость первый раз слышу.

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

Нет. Этого вообще никогда не требуется. За исключением ...
S>Помнится, я на 2 курсе спокойно асилил как считать эту самую сложность и запросто решал на экзаменах и зачётах любые задачи с этим связанные. И с тех пор так и не вспоминаю про это, так за за все эти годы мне это ни разу не понадобилось.
... собеседований.

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

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

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

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

Но с чего вы взяли что тут все документооборот клепают ?

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

S>>На любом этапе тут можно посчитать сложность, только не нужно, потому что это не решит проблему, а значит не нужно

MTD>Жесть!

Теперь спрашивать про о-большое буду в обязательном порядке.

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

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

M>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается.
M>Но с чего вы взяли что тут все документооборот клепают ?

А в какой практической области это надо?

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

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

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

Вы что пишите то ? документооборот или ?

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

KP>Подсчитать — нет. Подумать какой из алгоритмов/контейнеров будет оптимальным в данный момент или придумать как решить ту или иную алгоритмическую задачу — очень часто. И вот для этого "очень часто" знание, хотя бы приблизительное, того, как устроены контейнеры, или какова сложноть у алоритмов необходимо. Хотя, возможно, это потому, что я вообще не занимаюсь ни бухгалтерией, ни документоообротом.

Истинно так, только пойди, объясни это людям, которые хронически ставят лошадь позади телеги (в данном случае — сначала дожидаются возникновения проблемы, а потом думают, какое "знание" им нужно "приобрести").

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

A>Если ваши амбиции ограничены фирмами "с бугалтерий@документоообротом", то можете смело забить на алгоритмы, их сложность и нужность. А при упоминании их на собеседовании говорить, что это прошлый век, сейчас все решается волшебным форычем.

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

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

_DA>2. Сейчас вообще занимаюсь бизнес-приложениями.. У нас тут, например, есть оптимизирующий транслятор из DSL во, в конечном счете, SQL-запросы. Думаешь, там алгоритмики нет? Да что там.. даже, чтобы отчеты со сложными вложенными иерархиями через дурацкий JasperReports строить, пришлось повозиться c оптимизацией.

Ну а вы можете оценить в терминах О-теории сложность вашего оптимизатора? O(n)? O(logn)? Опишите процесс оптимизации алгоритма в вашем случае.

Здравствуйте, Son of Northern Darkness, Вы писали:

M>>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается.
M>>>Но с чего вы взяли что тут все документооборот клепают ?
BFE>>А в какой практической области это надо?
SON>Кто-то, видимо, положил в репозиторий несколько тысяч файлов, TestTrack опять подвис на пол часа. Это не вы с Sorc17 его разрабатывали, случайно?

Вы рассуждаете в терминах временных затрат, а вовсе не в терминах алгоритмической сложности. Вот об этом я и говорю.

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

M>>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается.
M>>>Но с чего вы взяли что тут все документооборот клепают ?
BFE>>А в какой практической области это надо?

_DA>Хм, на мой взгляд почти везде надо, чтобы не написать что-нибудь критичное по скорости со сложностью O(n^3), где достаточно O(nlogn). Но если нужны примеры..

Да, хочу примеров.

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

Ну понятно. Поиск и сортировка. Это теория. Но неужели вы рассуждали на практике так: "Этот алгоритм требует O(N^5) операций сложения. Это слишком много. Будем искать другой алгоритм и пока не найдём — ничего имплементировать не будем"?

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

Ничего не понял. Преждевременная оптимизация не может привести к квадратичным алгоритмам там, где их быть не должно. А преждевременная пессимизация это вообще — как?

_DA>2. Сейчас вообще занимаюсь бизнес-приложениями.. У нас тут, например, есть оптимизирующий транслятор из DSL во, в конечном счете, SQL-запросы. Думаешь, там алгоритмики нет? Да что там.. даже, чтобы отчеты со сложными вложенными иерархиями через дурацкий JasperReports строить, пришлось повозиться c оптимизацией.

Вы не путаете оптимизацию с оценкой сложности? Это разные понятия.

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

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

Надеюсь вы принимаете ответ, что сложность зависит от способа реализации ArrayList-а?

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

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

Хороший вопрос, так видно собеседования и заваливают. Все же Array или List?

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

BFE>Нет, не ирония. Я просто никогда не встречал программистов рассуждающих в терминах алгоритмической сложности для практических задач. Например, при большом количестве данных обычно рассуждают не в терминах количества операций, а во временных затратах. Сортировка данных лежащих на диске и сортировка данных находящихся в оперативной памяти — это два разных алгоритма. Рассуждения об о-большом тут мало чем помогут. И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?

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

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

BFE>>Расскажите, пожалуйста, про практику применения этого знания. В каком контексте и для каких задач вы рассчитывали алгоритмическую сложность?
ГВ>Конечной фазой "применения этого знания" является выбор алгоритма из набора имеющихся. Но для того, чтобы этот выбор можно было сделать, нужно знать, в том числе, что такое "оценка алгоритмической сложности".

Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность. Вот, например, кто-нибудь рассуждает так: "Окно в первом прототипе будет обрабатывать 5 сообщений. Количество сообщений по мере развития приложения может увеличится до сотни. Если мы напишем switch(номер сообщения), то алгоритмическая сложность составит O(n). Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше. Что-ж, заведём массив хранящий пару (номер сообщения, обработчик), отсортируем его по номеру сообщения и будем применять бинарный поиск! Тааак... теперь надо выбрать правильный алгоритм сортировки..."

ГВ>Имено так и "применяют" такие знания. То есть фокус в том, что будучи хорошо усвоенным, это знание не требует постоянного своего "применения". И тот, кто действительно умеет применять подобные штуки нередко становится в тупик перед вопросом: "а как вы его применяете?" Никак не применяю. Это — контекст, в известном смысле — статичный.

Так и запишем.

ГВ>P.S.: Задолбали уже этим своим "применением" по поводу и без.
Задолбали уже этим своими задачками на собеседовании. Я вот работу хочу поменять. Пойду учить греческие буквы и умные слова...

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

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

ПМ>Обычно это просто маркер говнокодеров. Я не встречал нормальных программистов, у которых были бы с этим проблемы, тем более, что в задачах с бугалтерий@документоообротом вся алгоритмическая сложность сводится к выбору между тремя вложенными циклами или каким-нибудь более эффективным решением. Зато говнокодеры, которые любили писать какую-нибудь лапшу без понимания, как оно работает, почти никогда не знали, что такое алгоритмическая сложность.

Саша, ты?
Коммитить уже не боишься?

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

BFE>

Вы рассуждаете в терминах временных затрат, а вовсе не в терминах алгоритмической сложности. Вот об этом я и говорю.

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

Точно не вы писали?

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

BFE>>Нет, не ирония. Я просто никогда не встречал программистов рассуждающих в терминах алгоритмической сложности для практических задач. Например, при большом количестве данных обычно рассуждают не в терминах количества операций, а во временных затратах. Сортировка данных лежащих на диске и сортировка данных находящихся в оперативной памяти — это два разных алгоритма. Рассуждения об о-большом тут мало чем помогут. И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?

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

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

Здравствуйте, Son of Northern Darkness, Вы писали:

BFE>>

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

Точно не вы писали?

Нет. Я TestTrack не писал. (Но название мне знакомо). А на каком основании вы считаете, что авторы рассуждали в терминах временных затрат? Мне кажется, что при таком результате они не рассуждали вообще.

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

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

Точно знаешь? И в реализацию вычисления размеров/ отрисовки лазал?
Да и что ж у него с ростом количества контента все тормозить начинает, если оно хотябы логарифмично, а то и вообще константа, как тебе кажется?

S>Помнится, я на 2 курсе спокойно асилил как считать эту самую сложность и запросто решал на экзаменах и зачётах любые задачи с этим связанные. И с тех пор так и не вспоминаю про это, так за за все эти годы мне это ни разу не понадобилось.
Хорошее знание струтур важно в карьере программиста. Это дает возможность выбора. Вот я например могу запросто реализовать пузырьковую сортировка, а быструю с проблемами. В быстрой сортировке массив делится на две части, в первой части я прекрассно разбираюсь, а вот во второй путаюсь. Таким образом я могу работать как Senior Bubble Sort Developer, или как Quick Sort Developer. Учитесь и у вас тоже будет возможность выбора.

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

M>Хороший вопрос, так видно собеседования и заваливают. Все же Array или List?

import java.util.ArrayList;

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

S>>Неужто на ваших фирмах с бугалтерий@документоообротом хоть одному программисту хоть раз за всю историю разработки понадобилось посчитать алгоритмическую сложность?

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

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

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

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

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

_DA>остается только выбрать тот, который удовлетворяет требованиям и требует минимального количества затрат. То есть понятно, что если у нас выбор между двумя алгоритмами O(n^2) и O(nlogn), есть некая функция, которая должна выполняться, не сильно раздражая пользователя, и работать с сотнями тысяч объектов, то выбора особо не остается.

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

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

BFE>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность.

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

BFE>Вот, например, кто-нибудь рассуждает так: "Окно в первом прототипе будет обрабатывать 5 сообщений. Количество сообщений по мере развития приложения может увеличится до сотни. Если мы напишем switch(номер сообщения), то алгоритмическая сложность составит O(n). Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше. Что-ж, заведём массив хранящий пару (номер сообщения, обработчик), отсортируем его по номеру сообщения и будем применять бинарный поиск! Тааак... теперь надо выбрать правильный алгоритм сортировки..."

Ну, я так рассуждаю.

Нормальный ход рассуждений, ИМХО. Разве что не употребляю сам термин: "О-большое". Другое дело, что я с трудом могу представить класс окна, обрабатывающий сотни типов сообщений, но это уже из другой оперы.

Да, и на практике сложность switch далеко не всегда O(n), компилятор может сгенерировать простую таблицу переходов. Посмотри повнимательней дизассемблированный код.

ГВ>>Имено так и "применяют" такие знания. То есть фокус в том, что будучи хорошо усвоенным, это знание не требует постоянного своего "применения". И тот, кто действительно умеет применять подобные штуки нередко становится в тупик перед вопросом: "а как вы его применяете?" Никак не применяю. Это — контекст, в известном смысле — статичный.

BFE>Так и запишем.

Пиши, пиши...

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

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

> реально знать о ней нафиг не нужно. Оценка самого алгоритма — вот что действительно важно.
оценка алгоритма -- это как? O(log n) и O(n^2) -- это и есть оценка сложности. в первом случае время обработки запроса практически не зависит от кол-ва данных (точнее, зависит, но очень слабо), во втором случае -- очень быстро наступает предел, за которым наращивать производительность становится слишком дорого. однако, тут нужно смотреть к чему стремиться N. если это кол-во участников социальной сети, то это одно.

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

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

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

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

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

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

BFE>Для известных алгоритмов оценка уже сделана. Осталось только выбрать. Вопрос же стоит о том, чтобы самому подсчитать сложность. На мой взгляд на практике это не делается практически никогда.
Можно взять любой алгоритм, составленный из "известных". На практике — некий алгоритм с использованием стандартных контейнеров и библиотечных функций, там ведь уже надо как-то понять, какая сложность будет в результате. Или мы это не рассматриваем как "подсчет сложности"?

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

BFE>>>Обычно, всё-ж оценивают размеры обрабатываемых данных и временные рамки для их обработки, а не алгоритмическую сложность.
MTD>>Это оно и есть.

BFE>Нет. Время и количество шагов могут быть не связаны.

Еще как связаны.

BFE>"равносилен", так как количество операций сравнений не меняется:

BFE>

BFE>for(i = 0; i < n; i++)
BFE>  if ( x == a[i] ) 
BFE>    break;
BFE>

BFE>Разве нет?

Нет. Компилятор для свича построит таблицу переходов и вуаля — О(1)

BFE>>>Но ведь есть алгоритм бинарного поиска! Его алгоритмическая сложность меньше.
MTD>>O(log n) — существенно больше O(1), но меньше O(n).

BFE>При n равным 100 ?

Да.

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

BFE>>Для известных алгоритмов оценка уже сделана. Осталось только выбрать. Вопрос же стоит о том, чтобы самому подсчитать сложность. На мой взгляд на практике это не делается практически никогда.
_DA>Можно взять любой алгоритм, составленный из "известных". На практике — некий алгоритм с использованием стандартных контейнеров и библиотечных функций, там ведь уже надо как-то понять, какая сложность будет в результате. Или мы это не рассматриваем как "подсчет сложности"?

В моём понимании это не подсчет сложности. Вот пример: отсюда:

Сама задача в данном случае не важна, но, на всякий случай:
A>>Задача с собеседования: Есть два отсортированных массива, которые идут в памяти один за другим. Надо их слить inplace в один отсортированный массив за время O(n) и заведя O(1) дополнительной памяти.
Некий Аноним пишет:
А>Затрудняюсь точно оценить время.. здесь сильно лучше O(n^2), вопрос насколько хуже O(n)?

Видите, Аноним не может вычислить алгоритмическая сложность этого своего творения (а только даёт оценку):

А>

А>public static void Sort(int[] source, int firstArrayIndex, int secondArrayIndex)
А>{
А>    int i = firstArrayIndex, j = secondArrayIndex, k = -1;
А>    while (true)
А>    {
А>        if (source[i] > source[j])
А>        {
А>            if (k == -1) k = i;
А>            int temp = source[i];
А>            source[i++] = source[j];
А>            source[j++] = temp;
А>        }
А>        else
А>            if (++i == j)
А>                return;
А>        if (j == source.Length || i == secondArrayIndex)
А>        {
А>            if (i == secondArrayIndex)
А>                Sort(source, secondArrayIndex, j);
А>            if (k + 1 < secondArrayIndex)
А>                Sort(source, k + 1, secondArrayIndex);
А>            return;
А>        }
А>    }
А>}
А>

а вы можете ? И часто занимаетесь этим на практике? Сомневаюсь.
ЕМНИП, у Кнута есть строчки, что для некоторых алгоритмов вычисление алгоритмической сложности — сама по себе задача не простая.

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

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

M>Хороший вопрос, так видно собеседования и заваливают. Все же Array или List?

Я тоже в шоке, но в C# есть ArrayList

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

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

BFE>>"равносилен", так как количество операций сравнений не меняется:
BFE>>

BFE>>for(i = 0; i < n; i++)
BFE>>  if ( x == a[i] ) 
BFE>>    break;
BFE>>

BFE>>Разве нет?
MTD>Нет. Компилятор для свича построит таблицу переходов и вуаля — О(1)

Интересно. Во всех случаях? Даже если константы идут не по возрастанию?:

switch(x)
{
   case 1000:
   break;
   case -69876:
   break;
   case 834950:
   break;
}

MTD>>>O(log n) — существенно больше O(1), но меньше O(n).
BFE>>При n равным 100 ?
MTD>Да.

Т.е. экономия сотни наносекунд в цикле обработки оконного сообщения — это нормально?

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

З>Я вообще никогда в жизни не слышал о таком понятии, как "алгоритмическая сложность". Нигде — ни в институте, ни на работе, ни в книжках, ни в интернетах, ни от коллег.

Еще скажите, что на матане вы O-нотацию не проходили.

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

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

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

Платформа какай?

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

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

M>>>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается.
M>>>>Но с чего вы взяли что тут все документооборот клепают ?
BFE>>>А в какой практической области это надо?
M>>Начиная от оптимизации работы с большим к-вом данных, заканчивая 3д графикой. Или это ирония ?

BFE>Нет, не ирония. Я просто никогда не встречал программистов рассуждающих в терминах алгоритмической сложности для практических задач.

Это очень странно, может разные задачи у нас с вами. Я почти все время с такими общаюсь . Например на недавней пьянке спросил коллег оценить скорость выполнения двух вариантов инвертирования списков
http://rsdn.ru/forum/job/4653211.1.aspx
Почти все предположили очевидные реализации и дали правильную оценку, с описанием когда лучше использовать тот или иной метод.

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

Которые могут быть оценены испольуя и алгоритмическую сложность. Вполне реально дать оценку , на каких типах данных и объемах какую лучше использовать сортировку radix sort или intro sort и т.п.

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

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

BFE> И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?

так же как и везде

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

Размер данных это тоже входит в оценку производительности. Но мульен операций O(N) и O(N*N) это небо и земля по быстродействию. И хоть издалека програмист видит эту разницу ибо азбука.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

BFE>Но это не важно. Важно, что решение принятое вами о кастомизации основано не на оценке алгоритмической сложности, а потому, что "у него с ростом количества контента все тормозить начинает".

А решение о замене шин на автомобиле принимается после того как шина лопнет простите ?

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

BFE>Количество шагов может быть огромным, а время выполнения ничтожным по сравнению с поставленными временными рамками. Так что это не важно.

Количество шагов может быть небольшим, а время выполнения огромным по сравнению с поставленными временными рамками. Так что это важно.

BFE>Интересно. Во всех случаях? Даже если константы идут не по возрастанию?:

А какие проблемы?

BFE>Т.е. экономия сотни наносекунд в цикле обработки оконного сообщения — это нормально?

Экономия сотни наносекунд в цикле обработки 100 гигабитного потока — это очень хорошо! Смотри сам (я упрощенно): при 100 гигабитах, длительность 1 бита составит 0.01 наносекунды, а ты говоришь о сотнях наносекунд!

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

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

З>>Я вообще никогда в жизни не слышал о таком понятии, как "алгоритмическая сложность". Нигде — ни в институте, ни на работе, ни в книжках, ни в интернетах, ни от коллег.

MP>Еще скажите, что на матане вы O-нотацию не проходили.

Могу ошибаться, но в заборостроительных вузах вроде матана нет

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

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

V>НЕД. В switch это просто jump по адресу.

В большинстве случаев.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

S>"Спасибо, мы вам перезвоним в ближайшее время?"

Я не устраиваю собеседований в онлайне на rsdn, но когда мне так отвечают, я интересуюсь, как именно устроен ArrayList. В 100% случаев не отвечают. Дальше, как правило, следует еще пяток неверных ответов по основам используемой платформы, пяток неверных ответов по поводу специфичных вещей, нужных для проекта и, как правило, "спасибо, мы вам перезвоним в ближайшее время". Поэтому я и говорю, что всякие вычислительные сложности — это индикаторы. Если по ним незачёт, то дальше можно не продолжать, с высокой вероятностью ничего не потеряете, но сэкономите время.

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

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

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

M>>Хороший вопрос, так видно собеседования и заваливают. Все же Array или List?

MTD>Я тоже в шоке, но в C# есть ArrayList

Не надо шокироваться. List — это просто упорядоченный набор элементов. И у него обычно две реализации: array и linked list. В терминологии на русском языке часто под словом "список" подразумевается linked list из-за этого и часто возникающая путаница.

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

BFE>Надеюсь вы принимаете ответ, что сложность зависит от способа реализации ArrayList-а?

Да, принимаю, и сразу прощаюсь после этого.

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

A>Платформа какай?

Без разницы.

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

BFE>

Я не возьмусь оценить алгоритмическую сложность отрисовки литбокса, но обычно она не константа, не логарифм и не линейность. Видел реализации, где количество операций было приблизительно O(n!).

Мне как-то не верится в это. Факториал очень быстрорастущая функция, уже на 15 элементах компьютер встал бы на колени совершая аж 1 307 674 368 000 бессмысленных действий.

Здравствуйте, мыщъх, Вы писали:

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

У большинства реализаций симплекс-метода, кстати, worst case O(N^2) и ничё, параллелят.

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

BFE>Нет, не ирония. Я просто никогда не встречал программистов рассуждающих в терминах алгоритмической сложности для практических задач. Например, при большом количестве данных обычно рассуждают не в терминах количества операций, а во временных затратах. Сортировка данных лежащих на диске и сортировка данных находящихся в оперативной памяти — это два разных алгоритма. Рассуждения об о-большом тут мало чем помогут. И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?

Товарищи, не рассуждающие в терминах алгоритмической сложности, создали архитектуру, в которой рефреш редакторов (не суть важно каких) занимает O(N * M) (N, M- число некоторых элементов). Все было хорошо пока M было сильно меньше N. Но внезапно в реальности стали возникать ситуации, когда M ~ N и у нас получилось O(N ^ 2), что выродилось в миллионы (и сотни миллионов) итераций. Переделка решения на O(N + M) позволила существенно поднять производительность (с нескольких минут до пары секунд).

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

A>>Платформа какая?

ПМ>Без разницы.

Не думаю

Не силен в джаве, но в дотнете это всего лишь массив.

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

BFE>>И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
MTD>Ну вот как, как, такое может придти в голову?
Как, как ... Из практики!

MTD> Я даже не об алгоритмах говорю, а о несчастных юзерах.

Что с ними не так? Их последнее время расплодилось столько, что в 32 бита не влезают.

MTD> Однозначно теперь первый вопрос про О-большое, ну после виртуального деструктора

Ну причём тут О-большое

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

ПМ>Нет конечно, switch — это почти всегда линейный поиск. Другое дело, что для тех случаев, когда используется swithc (десяток вариантов, набранных ручками) что-то более "умное" сожрёт больше времени. Это, кстати, хороший пример того, зачем надо знать про выч. сложность и почему на 10 кейсах можно использовать switch, а на 10000 — нет, даже если язык позволяет.

Да уж ... пиши ище

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

V>Да уж ... пиши ище

Ну предложи свою реализацию switchа за O(n) для значений отсюда. Чего сопишь? Не слышу.

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

BFE>>Нет, не ирония. Я просто никогда не встречал программистов рассуждающих в терминах алгоритмической сложности для практических задач.

M>Это очень странно, может разные задачи у нас с вами. Я почти все время с такими общаюсь . Например на недавней пьянке спросил коллег оценить скорость выполнения двух вариантов инвертирования списков
M>http://rsdn.ru/forum/job/4653211.1.aspx
M>Почти все предположили очевидные реализации и дали правильную оценку, с описанием когда лучше использовать тот или иной метод.

Да на пьянке чем только программисты не занимаются. Вопрос не в оценке, а в точном подсчёте.

BFE>> Например, при большом количестве данных обычно рассуждают не в терминах количества операций, а во временных затратах.
M>Которые могут быть оценены испольуя и алгоритмическую сложность. Вполне реально дать оценку , на каких типах данных и объемах какую лучше использовать сортировку radix sort или intro sort и т.п.
BFE>>Сортировка данных лежащих на диске и сортировка данных находящихся в оперативной памяти — это два разных алгоритма. Рассуждения об о-большом тут мало чем помогут.
M>Еще как помогают, и оценка может быть сделанна достаточно строго. Примеры строгих оценок можно найти в соотв. литературе.

Именно, что в соответствующей литературе, а не на практике.

BFE>> И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
M>так же как и везде

Да ну? А это ничего, что основное время будет уходить на операции чтения с диска?

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

A>Не думаю

Я тоже не думаю, я знаю, поэтому и говорю, что без разницы.

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

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

V>>Да уж ... пиши ище

ПМ>Ну предложи свою реализацию switchа за O(n) для значений отсюда. Чего сопишь? Не слышу.

Двоичный поиск используется для оптимизации таких switch'ей.

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

ПМ>Ну предложи свою реализацию switchа за O(n) для значений отсюда. Чего сопишь? Не слышу.

У свича нет сложности алгоритма, все считается на уровне компиляции.

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

_DA>Двоичный поиск используется для оптимизации таких switch'ей.

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

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

V>У свича нет сложности алгоритма, все считается на уровне компиляции.

Бла-бла-бла, код показывай.

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

BFE>Да на пьянке чем только программисты не занимаются. Вопрос не в оценке, а в точном подсчёте.

Я это не понял.

BFE>Именно, что в соответствующей литературе, а не на практике.

Не в вашей практике, уточняю.

BFE>Да ну? А это ничего, что основное время будет уходить на операции чтения с диска?

Не зная всей постановки задачи , я не буду ничего угадывать , ок ?

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

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

V>>У свича нет сложности алгоритма, все считается на уровне компиляции.

ПМ>Бла-бла-бла, код показывай.

Ща только студию скачаю, только вот http://www.microsoft.com/visualstudio/ru-ru/download не открываеться.

Здравствуйте, vpchelko, Вы писали:
V>Ща только студию скачаю, только вот http://www.microsoft.com/visualstudio/ru-ru/download не открываеться.

Не мать майкрософта, ну лять! 6 гектаров на диске C: которых 10 гектар из которых 5 уже папкой windows занято?????

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

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

A>>Не думаю

ПМ>Я тоже не думаю, я знаю, поэтому и говорю, что без разницы.

Ок, погорячился. Джавистов с сишниками перепутал

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

V>Не мать майкрософта, ну лять! 6 гектаров на диске C: которых 10 гектар из которых 5 уже папкой windows занято?????

Не ну $уки, сказал студии ставиться на диск Е там места докуа, а оно просит на Ц 6 гиктаров. Ну ляти не люти в макрософте!

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

BFE>>Надеюсь вы принимаете ответ, что сложность зависит от способа реализации ArrayList-а?
ПМ>Да, принимаю, и сразу прощаюсь после этого.

Речь о каком-то конкретном языке?

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

V>Это частный случай, нормальные свичи идут по enum-ам, где нумерация идет от 0 до N. Тут вообще не нужен поиск.

Не понял, что именно является частным случаем? И enum-ы далеко не во всех языках от 0 до N, в С++/C# можно явно задавать значения.

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

ПМ>Не понял, что именно является частным случаем? И enum-ы далеко не во всех языках от 0 до N, в С++/C# можно явно задавать значения.

Ну задавай дальше явно.

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

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

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

ПМ>У большинства реализаций симплекс-метода, кстати, worst case O(N^2) и ничё, параллелят.
"параллелят" != "не масштабируется". если N возрасло в десять раз, то придется покупать очень много железа, чтобы это обсчитать. тем более, что я писал про O(N!). при росте N в десять раз время вычисления возрастет в миллионы раз. а N это кол-во участников социальной сети и некий алгоритм (например, поиск в социальном графе как перетрахать макс. кол-во баб, чтобы они как можно дольше не узнавали об измене через круг своих друзей) имеет сложность N, то с ростом сети он быстро ляжет.

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

V>Не ну $уки, сказал студии ставиться на диск Е там места докуа, а оно просит на Ц 6 гиктаров. Ну ляти не люти в макрософте!

http://gcc.gnu.org/

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

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

BFE>>Интересно. Во всех случаях? Даже если константы идут не по возрастанию?:
MTD>А какие проблемы?

если никаких проблем, значит и цикл можно развернуть по тому же принципу.

BFE>>Т.е. экономия сотни наносекунд в цикле обработки оконного сообщения — это нормально?
MTD>Экономия сотни наносекунд в цикле обработки 100 гигабитного потока — это очень хорошо! Смотри сам (я упрощенно): при 100 гигабитах, длительность 1 бита составит 0.01 наносекунды, а ты говоришь о сотнях наносекунд!
А причем тут цикл обработки 100 гигабитного потока?

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

ПМ>http://gcc.gnu.org/

Нафиг мне гну. Мне студия нужна. Не могу работать без нормального IDE. Там дизасемблер ц кода встроенный прямо в отладчик.

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

BFE>Речь о каком-то конкретном языке?

Естественно, ArrayList — это название класса.

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

V>Нафиг мне гну. Мне студия нужна. Не могу работать без нормального IDE. Там дизасемблер ц кода встроенный прямо в отладчик.

Вот дизассемблер цэ прямо в браузер http://llvm.org/demo/

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

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

A>Ок, погорячился. Джавистов с сишниками перепутал

У сишников ArrayList vector называется, и принципиальной разницы нет в реализации (не считая пары заносов С++, которые могут вынести любому, кто опирается на логику, а не на зазубривание "стандартов" этой помойки).

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

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

Это стандартный класс?

Здравствуйте, мыщъх, Вы писали:

М>"параллелят" != "не масштабируется". если N возрасло в десять раз, то придется покупать очень много железа, чтобы это обсчитать.

Я не понял, это ты сейчас пытаешься меня убедить, что при N=100 симплекс-метод уже использовать нельзя? (я опечатался, там 2^N)

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

V>Это частный случай, нормальные свичи идут по enum-ам, где нумерация идет от 0 до N. Тут вообще не нужен поиск.

Вообще-то изначально речь шла про оконные сообщения, а не про enum.

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

A>>Ок, погорячился. Джавистов с сишниками перепутал

ПМ>У сишников ArrayList vector называется, и принципиальной разницы нет в реализации (не считая пары заносов С++, которые могут вынести любому, кто опирается на логику, а не на зазубривание "стандартов" этой помойки).

Сишников вводило в ступор название в котором встречается List, а листом по сути не является.

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

BFE>Вообще-то изначально речь шла про оконные сообщения, а не про enum.

Я отвечал на вполне конкретное сообщение с вполне конкретным примером.

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

BFE>Это стандартный класс?

Что значит "стандартный"?

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

BFE>>Это стандартный класс?
ПМ>Что значит "стандартный"?

Это значит, что класс описан в стандарте или (если у языка нет стандарта) в документации библиотеки (фрейворка), которая для данного языка является стандартом де-факто.

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

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

М>>"параллелят" != "не масштабируется". если N возрасло в десять раз, то придется покупать очень много железа, чтобы это обсчитать.
ПМ>Я не понял, это ты сейчас пытаешься меня убедить, что при N=100 симплекс-метод уже использовать нельзя? (я опечатался, там 2^N)
я говорю о том, что если для обработки вдвое большего объема данных требуется в сто раз больше времени, то рост объема данных станет проблемой такой системы. напротив, при O(log n) систему даже масштабировать не надо, т.к. даже чудовищный рост объема обрабатываемых данных не сильно скажется на времени их обработки.

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

ПМ>Можно просто взять нормальный язык программирования с нормальным REPL-ом и не мучить себя ни vim-ом, ни многогигабайтным говном. Хотя на счет vim-а — это дело вкуса, кому-то нравится vim, кому-то другие редакторы.

Я вообще-то в отладке хотел посмотреть как выглядит Ц код в бинарном (дизасеблированом) виде.

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

BFE>>Да на пьянке чем только программисты не занимаются. Вопрос не в оценке, а в точном подсчёте.
M>Я это не понял.

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

BFE>>Именно, что в соответствующей литературе, а не на практике.
M>Не в вашей практике, уточняю.

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

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

MTD>Есть такой метод — маляру дают задание покрасить 10 метров забора, он красит за 10 минут. Потом ему говорят покрасить 50 метров, он красит за 2500 минут, потом 100 метров, он красит за 10000 минут. Ага! По О(n^2) работает!

Измерить и вычислить — это не одно и тоже.

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

V>Я вообще-то в отладке хотел посмотреть как выглядит Ц код в бинарном (дизасеблированом) виде.

А не думать как из возможных 4гб, сделать 6.5, чтобы студия поставилась

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

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

A>>Ок, погорячился. Джавистов с сишниками перепутал

ПМ>У сишников ArrayList vector называется, и принципиальной разницы нет в реализации (не считая пары заносов С++, которые могут вынести любому, кто опирается на логику, а не на зазубривание "стандартов" этой помойки).

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

Здравствуйте, мыщъх, Вы писали:

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

А , ну так вот, worst case не всегда означает, что потребуется в сто раз больше времени. Пример — симплекс-метод, который 2^N. Или быстрая сортировка, которая в худшем случае квадратичная. Или хеш-таблицы, которые становятся линейными.

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

Да уж... память не ресурс...

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

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

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

ПМ>А , ну так вот, worst case не всегда означает, что потребуется в сто раз больше времени. Пример — симплекс-метод, который 2^N. Или быстрая сортировка, которая в худшем случае квадратичная. Или хеш-таблицы, которые становятся линейными.

да-да. хэш таблицы. поиск по словам post hashmap dos рулит. очень интересная дыра. потому что никому и в голову не пришло просчитать наихудший сценарий развития событий.

Здравствуйте, мыщъх, Вы писали:

М>да-да. хэш таблицы. поиск по словам post hashmap dos рулит. очень интересная дыра. потому что никому и в голову не пришло просчитать наихудший сценарий развития событий.

А не было случаев с использованием "дыры" в стандартных реализациях quicksort с вырождением в O(n^2)? В java/c# раньше ведь очень легко строились killer sequences для их реализаций.

DB>Естественно нет. Никогда и нигде задачи в виде "подсчитай алгоритмическую сложность этого куска кода" не было.

Как не было. Сходите в гугл на собеседование, это там в каждой задаче.

KP>Подсчитать — нет. Подумать какой из алгоритмов/контейнеров будет оптимальным в данный момент или придумать как решить ту или иную алгоритмическую задачу — очень часто. И вот для этого "очень часто" знание, хотя бы приблизительное, того, как устроены контейнеры, или какова сложноть у алоритмов необходимо. Хотя, возможно, это потому, что я вообще не занимаюсь ни бухгалтерией, ни документоообротом.

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

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

М>да-да. хэш таблицы. поиск по словам post hashmap dos рулит. очень интересная дыра. потому что никому и в голову не пришло просчитать наихудший сценарий развития событий.

ну я минимум 10 лет назад понимал возможность таких DoS

MTD>Нет. Компилятор для свича построит таблицу переходов и вуаля — О(1)

Что-то вас занесло. Немало современных кодогенераторов довольно тупо поступает — генерирует пары test reg, const -> jz caseconst.

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

gcc при определенных ключах компиляции

L>Ага. Видел таких гениев, что за деревьями не видят леса. Убъют две трети времени проекта на оптимизацию того, что в итоге либо не окажет никакого влияния на производительность, а то и будет вообще выкинуто, и прохлопают очевиднейшее бутылочное горлышко, в котором наговнокодят даже не O(n^2), а O(n^n). Специалисты блин, и все как один с дипломами, гномиков с закрытыми глазами считают и сортировки пальцами левой ноги на бумажке пишут.

Но ведь это же хорошо! Для нас с тобой, как минимум

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

L>>Ага. Видел таких гениев, что за деревьями не видят леса. Убъют две трети времени проекта на оптимизацию того, что в итоге либо не окажет никакого влияния на производительность, а то и будет вообще выкинуто, и прохлопают очевиднейшее бутылочное горлышко, в котором наговнокодят даже не O(n^2), а O(n^n). Специалисты блин, и все как один с дипломами, гномиков с закрытыми глазами считают и сортировки пальцами левой ноги на бумажке пишут.

SD>Но ведь это же хорошо! Для нас с тобой, как минимум

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

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

_DA>Не надо шокироваться. List — это просто упорядоченный набор элементов. И у него обычно две реализации: array и linked list. В терминологии на русском языке часто под словом "список" подразумевается linked list из-за этого и часто возникающая путаница.

Лучше уж тогда избегать путающих вопросов.

L>Да как-то задалбывает бороться с ветряными мельницами, если честно.

Do not fight it. Embrace it! (C)

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

L>>Да как-то задалбывает бороться с ветряными мельницами, если честно.

SD>Do not fight it. Embrace it! (C)

Так тоже можно. Жаль только, что эти Выбегаллы сильно портят имидж профессии.

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

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

Молодец, мозг включился

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

Можно в некоторых случаях.

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

А при чем тут лист бокс?

SD>>Do not fight it. Embrace it! (C)
L>Так тоже можно. Жаль только, что эти Выбегаллы сильно портят имидж профессии.

Что, простите, портят?

Имидж, простите, профессии _ПРОГРАММИСТА_?!

Не, я еще понимаю, ореол таинственности и мифичности, но чтоб "имидж".
Имид — это, вот, скажем, в России — работа сантехника.
Или, например, в США — юриста. Это имидж. А программист...

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

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

BFE>>>И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
MTD>>Ну вот как, как, такое может придти в голову?
BFE>Как, как ... Из практики!

MTD>> Я даже не об алгоритмах говорю, а о несчастных юзерах.

BFE>Что с ними не так? Их последнее время расплодилось столько, что в 32 бита не влезают.

Да уж... Может чем нибудь другим стоит заняться?

MTD>> Однозначно теперь первый вопрос про О-большое, ну после виртуального деструктора

BFE>Ну причём тут О-большое

Сразу позволяет понять стоит общаться дальше или нет. После этой темы я это хорошо понял.

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

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

З>>Я вообще никогда в жизни не слышал о таком понятии, как "алгоритмическая сложность". Нигде — ни в институте, ни на работе, ни в книжках, ни в интернетах, ни от коллег.

MP>Еще скажите, что на матане вы O-нотацию не проходили.

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

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

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

S>>"Спасибо, мы вам перезвоним в ближайшее время?"

ПМ>Я не устраиваю собеседований в онлайне на rsdn, но когда мне так отвечают, я интересуюсь, как именно устроен ArrayList. В 100% случаев не отвечают. Дальше, как правило, следует еще пяток неверных ответов по основам используемой платформы, пяток неверных ответов по поводу специфичных вещей, нужных для проекта и, как правило, "спасибо, мы вам перезвоним в ближайшее время". Поэтому я и говорю, что всякие вычислительные сложности — это индикаторы. Если по ним незачёт, то дальше можно не продолжать, с высокой вероятностью ничего не потеряете, но сэкономите время.

А, там таки массив внутри. http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html А я в своё время по диагонали прочитал, видимо

Щито поделать.

S>Всё же при switch будет N сравнений, где N это количество кейсов. Пруф:

в упор не вижу пруфа

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

Здравствуйте, мыщъх, Вы писали:

MTD>>>... или что проход по массиву n элементов имеет сложность O(n) ?!!

S>>Зачем это знать? Написал foreach и всё. Какая разница какая там у него сложность?
М>ну как бы последняя крупная дос дыра как раз и связана с тем, что для передачи аргументов web-программисты используют hashmap без понимания как оно работает и пацаны придумали как валить мощные сервера даже со слабого модема на 33,600. если в худшем случае у нас квадратичная сложность, то это означает, что покупкой оборудования проблему не исправить.

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

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

_DA>>Не надо шокироваться. List — это просто упорядоченный набор элементов. И у него обычно две реализации: array и linked list. В терминологии на русском языке часто под словом "список" подразумевается linked list из-за этого и часто возникающая путаница.

V>Лучше уж тогда избегать путающих вопросов.

Там цель отсеять, поэтому он такие вопросы специально накапливает.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Posted via RSDN NNTP Server 2.1 beta

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

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

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

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

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

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

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

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

Вы о чём?

MTD>>> Однозначно теперь первый вопрос про О-большое, ну после виртуального деструктора

BFE>>Ну причём тут О-большое

MTD>Сразу позволяет понять стоит общаться дальше или нет. После этой темы я это хорошо понял.

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

Здравствуйте, 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). Так?

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

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

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

M>О(n^2).
А почему n^2? strlen на каждой итерации будет выполняться? Ну да, тут я лопухнулся.
А как учитывается strcpy, которая вообще непонятно как часто выполняется? Я именно про неё написал logn, но это чисто от балды; что с strcpy делать, вообще не знаю.

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

К>А почему n^2? strlen на каждой итерации будет выполняться? Ну да, тут я лопухнулся.

Угу, это раз.

К>А как учитывается strcpy, которая вообще непонятно как часто выполняется? Я именно про неё написал logn, но это чисто от балды; что с strcpy делать, вообще не знаю.

Представьте строку из одних пробелов, к-во операций.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

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

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

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

M>>О(n^2).
К>А почему n^2? strlen на каждой итерации будет выполняться? Ну да, тут я лопухнулся.
К>А как учитывается strcpy, которая вообще непонятно как часто выполняется? Я именно про неё написал logn, но это чисто от балды; что с strcpy делать, вообще не знаю.

Я к чему спрашиваю... Если код переписать так:

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

То, не учитывая strcpy, получим O(n+n) => O(2n) => O(n), вот только константа О станет весомее. А ведь вариант явно будет помедленнее (по причине strcpy), чем мой с двумя индексами (у которого также O(n)). И по оценке сложности получим одинаковую сложность двух разных алгоритмов.

У меня ошибка в рассуждениях?

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

К>У меня ошибка в рассуждениях?

strcpy сложность O(n) будет вызвана кво раз пропорционально n , т.е. O(n*n) константа зависит от частоты пробелов во входных данных.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

...
К>>А как учитывается strcpy, которая вообще непонятно как часто выполняется? Я именно про неё написал logn, но это чисто от балды; что с strcpy делать, вообще не знаю.
M>Представьте строку из одних пробелов, к-во операций.

Оцениваем всегда самый плохой случай? Тогда должно быть O(n*n*X), где X явно не n, т.к. strcpy вызывается n раз, но каждый раз обрабатывает строку на 1 меньше.

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

A>Там цель отсеять, поэтому он такие вопросы специально накапливает.

Только вот кого отсеять..?

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

Зато если этот процесс визуализировать, то будет забавно.

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

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

Слушайте, а что вы так уперлись в это O()? Мне представлялось, что расходы памяти не менее существенный вопрос, а для памяти, кажется, даже буквы нет общепризнанной?

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

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

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

S>Слушайте, а что вы так уперлись в это O()? Мне представлялось, что расходы памяти не менее существенный вопрос, а для памяти, кажется, даже буквы нет общепризнанной?

O-нотация — это нотация для обозначения асимптотики функций.

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

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

S>>Слушайте, а что вы так уперлись в это O()? Мне представлялось, что расходы памяти не менее существенный вопрос, а для памяти, кажется, даже буквы нет общепризнанной?

_DA>O-нотация — это нотация для обозначения асимптотики функций.

Да, и при этом я ни разу не видел, чтобы ее применяли к памяти. Особенно собеседователи.

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

S>Да, и при этом я ни разу не видел, чтобы ее применяли к памяти. Особенно собеседователи.

Остается только сделать вот так

Ну, я даже не знаю, привести пример что ли? http://en.wikipedia.org/wiki/Quicksort

_DA>>O-нотация — это нотация для обозначения асимптотики функций.

S>Да, и при этом я ни разу не видел, чтобы ее применяли к памяти. Особенно собеседователи.

В википедии в статье про ту же сортировку О-нотация применяется и к объему памяти тоже: http://ru.wikipedia.org/wiki/Алгоритм_сортировки (раздел Оценка алгоритма сортировки). Да и в универе, насколько я помню, О-нотацию учат применять и к памяти тоже.

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

S>>Да, и при этом я ни разу не видел, чтобы ее применяли к памяти. Особенно собеседователи.

_DA>Остается только сделать вот так

Ну, я даже не знаю, привести пример что ли? http://en.wikipedia.org/wiki/Quicksort

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

Всё минусуют и минусуют. Уж и потроллировать нельзя. Не, ну а чё, кто сказал, что у меня в switch всё так причёсано, что спокойно преобразуется во всякие там смещения?

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

S>Всё минусуют и минусуют. Уж и потроллировать нельзя. Не, ну а чё, кто сказал, что у меня в switch всё так причёсано, что спокойно преобразуется во всякие там смещения?

Вот репо дрочер же.

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

...
A>Если ваши амбиции ограничены фирмами "с бугалтерий@документоообротом", то можете смело забить на алгоритмы, их сложность и нужность. А при упоминании их на собеседовании говорить, что это прошлый век, сейчас все решается волшебным форычем.
Дело не в форыче. Большие объёмы в бухгалтерии встречаются, вот только они в БД лежат. А если они в оперативку попали — скорее всего, что что-то неверно в консерватории. Ну а оптимизация в БД — другой вопрос. А тут бухгалтерию с ГИСом сравнить пытаются %). В КСВ им уже пора.

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

S>Слушайте, а что вы так уперлись в это O()? Мне представлялось, что расходы памяти не менее существенный вопрос, а для памяти, кажется, даже буквы нет общепризнанной?

Может в память реже упираются ?

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

S>>Ну вот тут три темы было, кажется, про проверку навыков при собеседовании. Везде мучительно обсасывали сложность в смысле скорости, и никто ни разу не упомянул память.

_DA>Я упоминал

http://rsdn.ru/forum/job/4660501.1.aspx

Уел

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

S>А хрен его знает. Я по работе упираюсь как раз в память несколько чаще, чем в вычисления. Вообще в контексте собеседований у меня ощущение, задачки про O(труляля) дают потому, что это удобная теория, которую знает принимающий, а со стороны памяти просто нет ничего красивого, что можно было бы удобно спросить на собеседовании.

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

S>>А хрен его знает. Я по работе упираюсь как раз в память несколько чаще, чем в вычисления. Вообще в контексте собеседований у меня ощущение, задачки про O(труляля) дают потому, что это удобная теория, которую знает принимающий, а со стороны памяти просто нет ничего красивого, что можно было бы удобно спросить на собеседовании.

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

Ну да, разумно, что каждый спрашивает, что ему нужно, наверное. Тогда я не пойму, чего ты взъелся чуть дальше на довольно резонное замечание о том, что большие размеры нужно особо оговаривать. На самом деле там несколько стадий размеров, и сначала играет O(...), а потом в основном NUMA, и подходы к ним довольно разные. И способы улучшить выбрасывание пробелов из строки тоже будут изрядно различаться, в зависимости от того, планируете ли вы дальше размер увеличивать или нет.

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

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

Тебе показалось.

S> На самом деле там несколько стадий размеров, и сначала играет O(...), а потом в основном NUMA, и подходы к ним довольно разные. И способы улучшить выбрасывание пробелов из строки тоже будут изрядно различаться, в зависимости от того, планируете ли вы дальше размер увеличивать или нет.

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

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

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

S>> На самом деле там несколько стадий размеров, и сначала играет O(...), а потом в основном NUMA, и подходы к ним довольно разные. И способы улучшить выбрасывание пробелов из строки тоже будут изрядно различаться, в зависимости от того, планируете ли вы дальше размер увеличивать или нет.

M>Зачем же так усложнять? Я не предлагаю оптимизировать под конкретную архитектуру, а лишь предложил указать на явные косяки. Уверен , что послушать и более глубокий анализ, на собеседовании будет интересно и полезно.

Ну ладно, осталось только узнать, не спрашиваете ли вы в конце, как устроен внутри arraylist, и можно признать вопрос пригодным

_DA>>O-нотация — это нотация для обозначения асимптотики функций.

S>Да, и при этом я ни разу не видел, чтобы ее применяли к памяти. Особенно собеседователи.

Смотрите матчасть со словом SPACE.

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

S>Ну ладно, осталось только узнать, не спрашиваете ли вы в конце, как устроен внутри arraylist, и можно признать вопрос пригодным

Я редко пользую cofee based языки,чтобы помнить о таком.

... << RSDN@Home 1.2.0 alpha 5 rev. 1539>>

П>Считать сложность как таковую — нет. Но один раз в жизни алгоритмы пригодились. Где-то пол-года назад в нашем внутреннем проекте загрузка данных стала уж очень долгой, по кейсу от юзеров ~ 5 часов.

Было дело, в низкоуровневой проге на чистом C без плюсов и классов, надо было преобразовать строку в Mixed_Case. Преобразование выполнялось, но заметно тормозило. В руководстве от IBM было написано, что функция преобразования выполняет поиск в общем алфавите (все символы Unicode, включая китайский), чтобы найти букву и подобрать ей замену. Имеем время поиска порядка (длина строки * половина расстояния до кириллицы в общем алфавите), или непоймисколько сравнений на каждую букву. Я так подумал, что раз у меня программа рассчитана на 8-разрядную кодировку, то...

...продолжать?

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

O>Было дело, в низкоуровневой проге на чистом C без плюсов и классов, надо было преобразовать строку в Mixed_Case. Преобразование выполнялось, но заметно тормозило. В руководстве от IBM было написано, что функция преобразования выполняет поиск в общем алфавите (все символы Unicode, включая китайский), чтобы найти букву и подобрать ей замену. Имеем время поиска порядка (длина строки * половина расстояния до кириллицы в общем алфавите), или непоймисколько сравнений на каждую букву. Я так подумал, что раз у меня программа рассчитана на 8-разрядную кодировку, то...
O>...продолжать?

таблицу чтоли на 256 элементов слабал?

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

ПМ>Например то, что он использует конструкторы копирования при ресайзе.
Уже move constructors юзает.

... << RSDN@Home>>

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

М>>да-да. хэш таблицы. поиск по словам post hashmap dos рулит. очень интересная дыра. потому что никому и в голову не пришло просчитать наихудший сценарий развития событий.

ПМ>Да его посчитали лет 10 назад, и в языках, которые используют кто-то кроме школьников и "индусов", этой дыры уж лет 10 как нет.

We show that PHP 5, Java, ASP.NET as well as v8 are fully vulnerable to this issue and PHP 4, Python and Ruby are partially vulnerable, depending on version or whether the server running the code is a 32 bit or 64 bit machine.

ASP.NET uses the Request.Form object to provide POST data to a web application developer. This object is of class NameValueCollection. This uses a different hash function than the standard .NET one, namely CaseInsensitiveHashProvider.getHashCode(). This is the DJBX33X (Dan Bernstein's times 33, XOR) hash function on the uppercase version of the key, which is breakable using a meet-in-the-middle attack.
CPU time is limited by the IIS webserver to a value of typically 90 seconds. This allows an attacker with about 30kbit/s to keep one Core2 core constantly busy. An attacker with a Gigabit connection can keep about 30.000 Core2 cores busy.

Хм.
Жаба и .NET в списке vulnerable имеются. Следовательно их используют тока школоло и индусы. Так?

... << RSDN@Home>>

D>таблицу чтоли на 256 элементов слабал?

...не имея при этом ни малейшего представления об "О большом" и "о малом"

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

Т>Жаба и .NET в списке vulnerable имеются. Следовательно их используют тока школоло и индусы. Так?

Я бы даже сказал, что на джаве и доднете пишут преимущественно школоло и индусы. Причем на доднете больше школоло, а на джаве — больше индусы.

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

A>>Там цель отсеять, поэтому он такие вопросы специально накапливает.

V>Только вот кого отсеять..?

Этого я не знаю. Мне кажется такой вопрос у них не возникает.
Главное сколько.

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

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

Вообще, вам стоит уточнять, что именно вы понимаете под сложность. Потому что, например, O(1) на вставку в конец — это не просто сложность. Такая оценка имеет вполне конкретное название. И отличается от "ассимптотической сложности" вставки (в realtime-обработке это может быть принципиально). Надеюсь, для этой O(1) название вы напишете без заглядывания в wiki/google/javadoc и т.п.

А то ведь можно еще и оба O(1) получить. Если рассматривать сложность написания соответствующего кода. Там оба — пара простых строк. Кстати, время написания кода — тоже важная оценка. Вот у меня в UI есть список, который после нескольких фильтров приводит к выводу части элементов в UI. Некоторые фильтры еще и "обратную связь" запускают (т.е. асинхронный процесс, который влияет на вход этого фильтра). И в исходном списке могут происходить изменения. В итоге после оценок везде "единицей изменения" считается полный список. Элементов там не так много, а поддержка "гранулированных" изменений выливается в ужасную кучу кода. Размер списка сверху жестко ограничен. Если он вырастет на порядок, проблемы и так начнутся (только в другом месте). А оценка сложности... Вместо простого фильтра (Array.filter с реактивной привязкой) в каждом обработчике нужно было правильно фильтровать события, обрабатывать их и т.п. (не забываем про фильтр с обратной связью).

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

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

А разве на этот ответ вообще можно дать однозначный ответ ?
Если мы говорим про связный список, то сложность добавления элемента в конец напрямую
зависит от того, как этот список реализован. Например, если у него концевые элементы
"замкнуты" на головной, как в VC++ STL или как у double linked list из Windows Kernel,
то вставка в начало и в конец будет O(1), а если он реализован через массив, либо
концевые элементы имеют prev/next равным NULL, то для вставки в конец уже получится O(n).
При этом сам список может хранить указатель на хвостовой элемент, и тут опять возвращается O(1).

На этот вопрос, кстати, есть еще один ответ.
Например, заглядывая в MSDN по поводу ArrayList, я не нашел ни одного упоминания ни
по поводу реализации, ни по поводу сложности вставки. Это может означать, в числе прочего, то,
что на реализацию полагаться нельзя и она может измениться в любое время. И тогда системы,
рассчитанные на константное время вставки в хвост списка, вдруг начнут показывать
проседание производительности.

	От:	Sorc17
	Дата:	14.03.12 09:12
	Оценка:	-6

	От:	Злобастик
	Дата:	14.03.12 11:24
	Оценка:	-6

От:	Геннадий Васильев	http://www.livejournal.com/users/gesha_x
Дата:	14.03.12 14:55
Оценка:	10 (2) +7

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	14.03.12 11:45
Оценка:	+8

	От:	anomander
	Дата:	14.03.12 10:24
	Оценка:

	От:	Берсерк
	Дата:	14.03.12 14:59
	Оценка:	9 (4) +1 -1

	От:	De-Bill
	Дата:	14.03.12 10:04
	Оценка:	2 (1) +4

От:	MTD	https://github.com/mtrempoltsev
Дата:	14.03.12 16:37
Оценка:	+4

	От:	Паблик Морозов
	Дата:	14.03.12 20:43
	Оценка:	-4

От:	Qwazar	http://qwazar.ru
Дата:	15.03.12 13:20
Оценка:	2 (1)

	От:	minorlogic
	Дата:	15.03.12 13:32
	Оценка:	2 (1)

От:	мыщъх	http://nezumi-lab.org
Дата:	14.03.12 16:53
Оценка:	1 (1)

	От:	Stanislav V. Zudin
	Дата:	14.03.12 13:05
	Оценка:	+1

От:	redp	redplait.blogspot.com
Дата:	15.03.12 08:52
Оценка:	+1

	От:	Пофигист
	Дата:	14.03.12 09:36
	Оценка:

	От:	Son of Northern Darkness
	Дата:	14.03.12 14:09
	Оценка:

От:	qxWork	http://www.jetbrains.com/company/people/Coox_Sergey.html
Дата:	14.03.12 15:45
Оценка:

От:	_Obelisk_	http://www.ibm.com
Дата:	14.03.12 20:05
Оценка:

	От:	Кондраций
	Дата:	15.03.12 07:38
	Оценка:

	От:	SingleUseAccount
	Дата:	15.03.12 20:25
	Оценка:

	От:	Трололоша
	Дата:	16.03.12 00:19
	Оценка:

От:	okman	https://searchinform.ru/
Дата:	16.03.12 11:54
Оценка: