Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, minorlogic, Вы писали:
M>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается. M>>Но с чего вы взяли что тут все документооборот клепают ?
BFE>А в какой практической области это надо?
Начиная от оптимизации работы с большим к-вом данных, заканчивая 3д графикой. Или это ирония ?
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, MTD, Вы писали:
S>>>На любом этапе тут можно посчитать сложность, только не нужно, потому что это не решит проблему, а значит не нужно MTD>>Жесть! Теперь спрашивать про о-большое буду в обязательном порядке.
BFE>Расскажите, пожалуйста, про практику применения этого знания. В каком контексте и для каких задач вы рассчитывали алгоритмическую сложность?
, например, хороший пример задач.
Алгоритм с O(N) превратить в O(N^3) за счет неправильно выбранных структур данных — легко.
Достаточно использовать "Форыча"(с) не думая.
_____________________
С уважением,
Stanislav V. Zudin
14.03.2012 16:05, Stanislav V. Zudin пишет:
> BFE>Расскажите, пожалуйста, про практику применения этого знания. В > каком контексте и для каких задач вы рассчитывали алгоритмическую сложность? > > Вот <http://rsdn.ru/forum/alg/4659539.1.aspx>
, например, хороший пример > задач. > Алгоритм с O(N) превратить в O(N^3) за счет неправильно выбранных > структур данных — легко.
Это все хорошо, но где ответ на поставленный вопрос: "для каких задач вы
рассчитывали алгоритмическую сложность?"
Ну и по тем задачам, что по ссылке, чтобы рассчитать их сложность в
терминах O в зависимости от алгоритмов нужно очень нехило повозиться,
причем нафиг это никому не надо.
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, minorlogic, Вы писали:
M>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается. M>>Но с чего вы взяли что тут все документооборот клепают ?
BFE>А в какой практической области это надо?
Кто-то, видимо, положил в репозиторий несколько тысяч файлов, TestTrack опять подвис на пол часа. Это не вы с Sorc17 его разрабатывали, случайно?
Здравствуйте, B0FEE664, Вы писали:
BFE>Здравствуйте, minorlogic, Вы писали:
M>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается. M>>Но с чего вы взяли что тут все документооборот клепают ?
BFE>А в какой практической области это надо?
Хм, на мой взгляд почти везде надо, чтобы не написать что-нибудь критичное по скорости со сложностью O(n^3), где достаточно O(nlogn). Но если нужны примеры..
1. Я довольно долго работал в продуктовой компании, выпускающей, например, софт для проектирования дорог или софт для геодезистов. Так там всякое бывало, начиная от нахождения точек пересечения тысяч кривых, до всяких примитивных поисков объектов по различным критериям. Как раз вот приходилось оптимизировать код после людей, зараженных преждевременной пессимизацией. И ведь работало все нормально до поры, до времени, пока проекты у пользователей не набирали достаточной критической массы, когда всякие квадратичные алгоритмы не выстреливали им по конечностям.
2. Сейчас вообще занимаюсь бизнес-приложениями.. У нас тут, например, есть оптимизирующий транслятор из DSL во, в конечном счете, SQL-запросы. Думаешь, там алгоритмики нет? Да что там.. даже, чтобы отчеты со сложными вложенными иерархиями через дурацкий JasperReports строить, пришлось повозиться c оптимизацией.
Здравствуйте, B0FEE664, Вы писали:
S>>>На любом этапе тут можно посчитать сложность, только не нужно, потому что это не решит проблему, а значит не нужно MTD>>Жесть! Теперь спрашивать про о-большое буду в обязательном порядке.
BFE>Расскажите, пожалуйста, про практику применения этого знания. В каком контексте и для каких задач вы рассчитывали алгоритмическую сложность?
Конечной фазой "применения этого знания" является выбор алгоритма из набора имеющихся. Но для того, чтобы этот выбор можно было сделать, нужно знать, в том числе, что такое "оценка алгоритмической сложности".
Имено так и "применяют" такие знания. То есть фокус в том, что будучи хорошо усвоенным, это знание не требует постоянного своего "применения". И тот, кто действительно умеет применять подобные штуки нередко становится в тупик перед вопросом: "а как вы его применяете?" Никак не применяю. Это — контекст, в известном смысле — статичный.
P.S.: Задолбали уже этим своим "применением" по поводу и без.
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Паблик Морозов, Вы писали:
ПМ>Здравствуйте, Sorc17, Вы писали:
S>>Ну ежели вы спрашиваете просто на понимание о чём вообще речь, то ладно.
ПМ>Ну я могу спросить, какая, например, сложность добавления элемента в конец ArrayList-а и в начало, и почему так получается.
Если я правильно помню, то ArrayList это просто список, но с который можно обращаться как будто он массив. Так что добавление и удаление из него — это просто поменять парочку ссылок.
"Спасибо, мы вам перезвоним в ближайшее время?"
Для нас [Thompson, Rob Pike, Robert Griesemer] это было просто исследование. Мы собрались вместе и решили, что ненавидим C++ [смех].
Здравствуйте, kaa.python, Вы писали:
KP>Подсчитать — нет. Подумать какой из алгоритмов/контейнеров будет оптимальным в данный момент или придумать как решить ту или иную алгоритмическую задачу — очень часто. И вот для этого "очень часто" знание, хотя бы приблизительное, того, как устроены контейнеры, или какова сложноть у алоритмов необходимо. Хотя, возможно, это потому, что я вообще не занимаюсь ни бухгалтерией, ни документоообротом.
Истинно так, только пойди, объясни это людям, которые хронически ставят лошадь позади телеги (в данном случае — сначала дожидаются возникновения проблемы, а потом думают, какое "знание" им нужно "приобрести").
Я знаю только две бесконечные вещи — Вселенную и человеческую глупость, и я не совсем уверен насчёт Вселенной. (c) А. Эйнштейн
P.S.: Винодельческие провинции — это есть рулез!
Здравствуйте, Sorc17, Вы писали:
S>Помнится, я на 2 курсе спокойно асилил как считать эту самую сложность и запросто решал на экзаменах и зачётах любые задачи с этим связанные. И с тех пор так и не вспоминаю про это, так за за все эти годы мне это ни разу не понадобилось.
Соглашусь с теми кто говорит что никакая оценка алгоритма не заменит профилирование. Слабость О-теории в том что некоторые моменты из реальной жизни в ней не учитываются. Например при оценке алгоритма обычно считается что доступ к любой ячейке памяти происходит за константное время, а это не так (на большинстве современных процессорах последовательное чтение памяти в разы быстрее). Более того работу кэша описать в терминах О-теории практически не возможно. Дальше вызовы функций и другие накладные расходы которые тоже имеют свою не-константную цену. Сложность настолько велика что практичнее реализовать что то простое и потом при помощи профилировщика допиливать до надлежащей производительности чем пытаться оценить алгоритм на бумажке.
Как пример можно посмотреть реализацию быстрой сортировки в стандартной библиотеке. Быстрая сортировка хороша только до какого то порогового значения, дальше применяют так называемую отсечку и мелкие куски сортируют пузырьком. На мой взгляд голова на плечах и профилировщик гораздо важнее знания О-теории. Ну и не забываем про реализацию, часто проблема именно в ней.
Ну и касаемо темы: спрашивать про О-теорию на собеседовании глупо и в корне не верно на мой взгляд. А спрашивать нужно конкретно по теме — если нужен специалист по работе с базами данных нужно спрашивать какие методы оптимизации конкретно он применял или знает, что лучше или хуже на его взгляд и так далее. Оптимизацию SQL запроса никакой О-теорией нормально не описать.
Здравствуйте, anomander, Вы писали:
A>Если ваши амбиции ограничены фирмами "с бугалтерий@документоообротом", то можете смело забить на алгоритмы, их сложность и нужность. А при упоминании их на собеседовании говорить, что это прошлый век, сейчас все решается волшебным форычем.
Нуу. Если бы вот я пошел на собеседование куда-нибудь в науку или в какой-нибудь яндекс, который оперирует огромными объёмами данных, то я бы потрудился хорошенько повторить всякие супер эффективные алгоритмы, распараллеливание и вообще поискал бы статьи как работают современные поисковые движки. Ну это так, к примеру.
Для нас [Thompson, Rob Pike, Robert Griesemer] это было просто исследование. Мы собрались вместе и решили, что ненавидим C++ [смех].
Здравствуйте, _DAle_, Вы писали:
_DA>2. Сейчас вообще занимаюсь бизнес-приложениями.. У нас тут, например, есть оптимизирующий транслятор из DSL во, в конечном счете, SQL-запросы. Думаешь, там алгоритмики нет? Да что там.. даже, чтобы отчеты со сложными вложенными иерархиями через дурацкий JasperReports строить, пришлось повозиться c оптимизацией.
Ну а вы можете оценить в терминах О-теории сложность вашего оптимизатора? O(n)? O(logn)? Опишите процесс оптимизации алгоритма в вашем случае.
Здравствуйте, minorlogic, Вы писали:
M>>>для "бугалтерий@документоообротом" Это все ен надо , да и ппрограмированием это с натяжкой нызывается. M>>>Но с чего вы взяли что тут все документооборот клепают ? BFE>>А в какой практической области это надо? M>Начиная от оптимизации работы с большим к-вом данных, заканчивая 3д графикой. Или это ирония ?
Нет, не ирония. Я просто никогда не встречал программистов рассуждающих в терминах алгоритмической сложности для практических задач. Например, при большом количестве данных обычно рассуждают не в терминах количества операций, а во временных затратах. Сортировка данных лежащих на диске и сортировка данных находящихся в оперативной памяти — это два разных алгоритма. Рассуждения об о-большом тут мало чем помогут. И как, интересно, может помочь оценка алгоритмической сложности, когда надо отобразить список фамилий размером в 4 миллиарда в листбоксе?
Здравствуйте, 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 миллиарда в листбоксе?
Например пониманием того, что операции с этим самым листбоксом в лучшем случае линейны по количеству элементов (а их дохрена). Как следствие, либо пишется кастомный листбокс, либо делается какая-то надстройка так, чтобы листбокс оперировал парой десятков (сколько там влезет в видимую область) элементов, а прочие ему подсовывались по мере надобности.
Теперь спрашивать про о-большое буду в обязательном порядке.
Вы рассуждаете в терминах временных затрат, а вовсе не в терминах алгоритмической сложности. Вот об этом я и говорю.
