Комментарии 30
Пожалуйста, если вы хотите быть нормальным инженером, никогда не мыслите в терминах big-O, реальные системы это не асимптоматика:
- Вы успускаете из вида самое главное — константу. В некоторых случаях оказывается, что алгоримты O(n^3) производительнее в разы, чем O(n^2.3727) (умножение матриц). В более простых примерах это тоже вполне работает, так как изменение алгоримта приводит к изменению константы.
- Стоит заметить, что некоторые коллекции работают не так, как математические аналоги. Например, получение значения в словаре это не О(1), а O(m), где m — максимальное число коллизий, вставка в массив не O(1) и так далее. (Для наивной реализации словаря с линейным поиском при коллизиции)
Хотя бы бенчмарки проводите параллельно.
Перебор коллекции внутри перебора другой коллекции есть прям везде. Особенно сложные лямбды этим грешат. Почти всегда можно что-нибудь посортировать или вообще в мапу переложить. Код становится быстрее в разы.
Collection.indexof можно в 95% случаев переписать. Аналогично становится быстрее в разы.
Прикрутить дерево для изменяемого сортированного списка уже сложнее, но выигрыш и тут в разы.
И не важно как там реализовано. Все коллизии и прочие n^2.3727 теряются по сравнению с изменением алгоритма.
Реальный код это как раз асимптоматика в большинстве случаев.
А вы точно понимаете, что такое "асимптоматика"? В реальном коде у вас всегда n ограничено сверху. Более того, часто оно ограничено сверху насколько сильно, что превращяется в вырожденный случай. Например, для корзины товаров это вполне может быть n < 3. А в таких случаях все эти оценки очень сильно сбоят, потому что более продвинутые алгоримты, обычно, имеют куда большую константу.
Будет ли оптимальнее менять сортированный список на бинароное дерево в таком случае? Я думаю, что очень сомнительно.
В реальном коде у вас всегда n ограничено сверху.Оно ограничено сверху возможностями железа. Которые, как бы, растут экспоненциально. Если у вас алгоритмы O(N) или O(N log N) — то всё будет нормально, если где-то будет O(N²) или, не дай бог, O(N³) — то, всё, караул.
Кстати, тот самый алгоритм, которым вы всех пугаете, умножение матриц, вовсе не так страшен, как вы говорите. Вот именно классически, в Big O. Потому что да, он O(N³)… вот только N — это не размер матрицы! Размер матрицы (сколько она в памяти занимает) — это N². То есть реально ваш ужасный, кошмарный, ай-ай-ай какой алгоритм — это O(size1½)… не так и много. Когда мы от всех O(N²) избавились — можно уже и константе подумать, да… но это — уже второй этап! Первый — это именно ассимптотика.
P.S. И да, конечно, далеко не всегда нужно от Big O избавляться, тут вы правы. У меня на работе есть программка, где алгоритм работает за время O(N³), где N — это таки реально размер задачи. Вот только это N… оно было равно 8 в 1978м году, 16 в 1985м, но 32 — только в 2012м… и не факт, что в ближайшие лет 20 это число вырастет ибо новые архитектуры с большим числом регистров раждаются нечасто. Но это — скорее исключение из правил.
Оно ограничено сверху возможностями железа
Нет. До железа у вас есть ограничения исходят от бизнес-правил/задачи. Вы же не берете наборы чисел и списки из воздуха. Обычно это список чего-то, вещей в корзине, платежей, задач в таск трекере и так далее. И очень часто оказывается, что ограничение довольно жесткое, иногда доходящее до "не больше 2".
но это — уже второй этап! Первый — это именно ассимптотика.
И снова нет. Я не зря упомянул перемножение матрицы (я думал все знают, что обсуждая сложность перемножение матрицы все подразумевают, что она квадратная, с размерностью n), потому что этот пример как можно лучше демонстрирует то, что константа крайне важна.
Есть как бы три известных алгоримта, наивная реализация со сложностью O(n^3), Алгоритм Штрассена, который имеет сложность O(n^2.81) и Алгоритм Копперсмита — Винограда который имеет сложность O(n^2.3727). Казалось бы, надо брать последний и радоватся, да?
На практике же, последний не используется совсем из-за очень большой константы, а алгоритм Штрассена не используется для матриц размерностью больше 64 в силу той же константы.
Поэтому, когда вы говорите, что "первый этап — это асимптотика", вы ошибаетесь. Первый этап — это нахождение ограничений, которые накладываются задачей. Если вы анализируете алгоритм без этого этапа, вы практически всегда сделаете это неправильно. А вот вторым этапом уже может быть подбор алгоримта с учетом этих ограничений.
Обычно это список чего-то, вещей в корзине, платежей, задач в таск трекере и так далее.Ok, принято.
И очень часто оказывается, что ограничение довольно жесткое, иногда доходящее до «не больше 2».И много вы видели багтрекеров с максимум двумя багами или корзину с не более, чем двумя товарами?
В моей практике как раз наоборот: гораздо чаще люди предполагают, что у них может быть, скажем, 100 человек на избирательном участке, а когда им, в результате того, что где-то данные посчитали вручную, приходит информации о голосовании ста тысяч человек человек (просто руками объединённые данные о нескольких удалённых участках), то это кладёт нафиг всю их систему голосования. Пример вполне из жизни, кстати.
Есть как бы три известных алгоримта, наивная реализация со сложностью O(n^3), Алгоритм Штрассена, который имеет сложность O(n^2.81) и Алгоритм Копперсмита — Винограда который имеет сложность O(n^2.3727). Казалось бы, надо брать последний и радоватся, да?И все три они — ближе к линейному алгоритму, чем к сортировке пузырьком. Но главное даже не в этом.
Вот вы тут рассусоливаете про «количество вещей в корзине, платежей, задач в таск трекере» — а как часто вы всё это засовываете в матрицы, которые затем перемножаете? Ну, в сравнении с кодом, который обнаруживает дубликаты и их объединяет, сортирует там по разному и тому подобными «банальностями», где вы можете получить O(N²) вместо O(N log N), если не подумать?
В моей практике на одно место, где кто-то использует ассимптотически хороший алгоритм с огромной константой приходятся десятки мест, где кто-то сортирует пузырьком или ищет дубликаты двумя вложенными циклами.
Вот когда избавитесь от этих тривиальных проблем — тогда и можно будет говорить об алгоримте Штрассена и перемножении матриц…
Я не рассматривал крайние случаи. Понятно что они есть и встречаются в реальной жизни. Но в среднем более быстрый асимптоматически алгоритм будет лучше. Любой другой случай это скорее исключение и когда его используешь надо четко понимать что делаешь и подробно комментировать и документировать все это. А для этого надо знать сложность алгоритмов, Big O вот это вот все.
Но в среднем более быстрый асимптоматически алгоритм будет лучше
Не будет. "асимптоматически" — это синоним "очень много". Это далеко не всегда 100 или 200, это вполне могуть быть числа, которые вообще не влазят в int32. В этом же примере с корзинами товаров, я могу ткнуть пальцев в небо и сказать, что не существует магазинов для физ. лиц со средней корзиной на 1000 товаров (у меня нет статистики, но я думаю, что на практике число не привышает 30-50).
Возьмем магазин автозапчастей. Внезапно, у нас корзина на сотню товаров становится нормальной. И софт сделанный под корзины в 2-3 товара будет тормозить на очень критичных операциях. Минус клиенты, минус прибыль.
Опять же таки, это входит в оценку алгоритма, определение граничных условий работы.
Однако если программист знает, что такое вообще это большое О, то оно будет для него очень мощным инструментом.
Ну и понятно, что использовать большое О для (N = числу товаров в корзине) — это забивание гвоздей микроскопом. В таком случае оно действительно не даст полезной информации, но это не потому, что большое О — плохой показатель, а просто потому, что ситуация не подходящая для его применения.
Согласитесь, есть большая разница между «Есть ситуации, когда большое О не даёт полезной информации» и «Никогда не используйте большое О!!!»
Мне кажется, что в ситуации, когда кто-то приймет решение о том, что О-большое полезно, он наплюет на некого SirEdvin с хабра, потому что он вполне будет понимать, что это и зачем оно надо.
Проблема в том, что в большинстве случаев O-большое не очень подходит как раз в силу лимитированной природы n, но вместо того, что бы писать об этом большими буквами, люди пропогандируют условный анализ алгоритмов, который в большинстве случаев не особо имеет смысл и вполне замещается бенчмарком и "Ой, тут вместо двух вложенных циклов можно написать один". В итоге люди начинают бегать по комнатам и доказыватьЮ что "тут же можно вместо O(n) переписать O(log n)!!" хотя там n < 3 и не совмем понятно, зачем это исправлять.
Ну и в копилку, так же предлагается оценивать производительность кода на глаз при помощи оценки алгоритма, что безумно вредно.
Проблема в том, что в большинстве случаев O-большое не очень подходит как раз в силу лимитированной природы nВ большинстве случаев? То есть на каждый мой случай, когда кто-то в очередной раз вкрутил маляра Шлемиэля куда-то вы можете привести пример неоптимального кода, в котором кто-то вложился в алгоритм, но забыл про константу?
который в большинстве случаев не особо имеет смысл и вполне замещается бенчмарком и «Ой, тут вместо двух вложенных циклов можно написать один»Но это ведь, извините, как раз и есть исследование на O(n)! Не на константу же: константа при переходе от вложенных циклов к одному, как правило, увеличиается.
Ну и в копилку, так же предлагается оценивать производительность кода на глаз при помощи оценки алгоритма, что безумно вредно.Тем не менее — это гораздо полезнее гораздо часто практикуемого подхода, когда в ответ на вопрос «а какая сложность тобой только что написанного кода» — человек даже не в состоянии ответить. И у него нет ни малейших идей — то ли там N3, то ли вообще NN.
тут же можно вместо O(n) переписать O(log n)!!" хотя там n < 3 и не совмем понятно, зачем это исправлять.Ну вот классический пример: O(1) scheduler — про него аж статью в Wikipedia написали отдельную. Как вы думаете — почему и зачем, если константа от его внедрения только возрасла и n < 3 — это скорее правило, чем исключение?
В большинстве случаев? То есть на каждый мой случай, когда кто-то в очередной раз вкрутил маляра Шлемиэля куда-то вы можете привести пример неоптимального кода, в котором кто-то вложился в алгоритм, но забыл про константу?
Мне интересно, почему вы смешиваете лишние действия с оценкой алгоритмов? Из статьи я понимаю, что вместо того, что бы передвинуть курсор, вам приходится каждый раз пробегать до конца строки — это лишние действия. А оценка алгоритмов — это сравнение сортировки пузыркем с быстрой сортировкой.
Ну вот классический пример: O(1) scheduler — про него аж статью в Wikipedia написали отдельную. Как вы думаете — почему и зачем, если константа от его внедрения только возрасла и n < 3 — это скорее правило, чем исключение?
Пожалуйста, помните про то, что у вас n возникает из бизнес-требований.
Разумеется, если мы говорим про ядро и количество процессов, то разумеется их там будет очень много. С другой стороны, если мы будем говорить про количество потоков в одном приложении, окажется, что их вряд ли больше 100.
Мне интересно, почему вы смешиваете лишние действия с оценкой алгоритмов?Мне более интересно как вы их отличаете.
Вот есть функция:
char* list_to_string(char* strings[]) {
char* res = strdup("");
while (*strings) {
res = realloc(res, strlen(res) + strlen(*strings) + 1);
strcat(res, *strings++)
}
return res;
}Что-что? Вы можете её переделать? И изменить алгоритм? Ну дык — это и есть в 99% случаев то, что люди имеют в виду, когда говорят о «более быстром асимптоматически алгоритме».
А оценка алгоритмов — это сравнение сортировки пузыркем с быстрой сортировкой.Да, но не только. Превращение того ужаса, который я там написал в нормальный код — это тоже оценка алгоритма. Да, тривиальная. Да, дающая отдачу примерно при N == 2, а не при N = 10100.
Но от этого не становящейся исследованием проблемы на Big O.
Разумеется, если мы говорим про ядро и количество процессов, то разумеется их там будет очень много.Вообще-то в те времена, когда шла битва за этот шедулер среднее число процессов в очереди было меньше трёх. Почти на всех системах. И даже сегодня это так, если речь идёт, скажем, про сотовые телефоны. Так что аналогия с вашей корзиной — весьма точная.
В этом же примере с корзинами товаров, я могу ткнуть пальцев в небо и сказать, что не существует магазинов для физ. лиц со средней корзиной на 1000 товаров (у меня нет статистики, но я думаю, что на практике число не привышает 30-50).А в этом случае средняя корзина как раз не так важна. Если вы не позволяете человеку положить в корзину сотню наименований каких-нибудь болтиков или шурупчиков — то вы отправляете к конкуренту как раз людей, которые могли бы вам принести больше всего дохода.
Кроме того вы мешаете в кучу две вещи:
1. Полезность Bog O для написания качественного кода.
2. Полезность написания качественного кода, вместо дурно пахнущего тормозного дерьма.
Если вам вообще интересен качественный код — то Big O ваш лучший друг. Если вам нужно что-то сделать «тяп-ляп и в продакшн», то вам ни ассмптотика, ни константа не важны, важна скорость разработки.
А в этом случае средняя корзина как раз не так важна. Если вы не позволяете человеку положить в корзину сотню наименований каких-нибудь болтиков или шурупчиков — то вы отправляете к конкуренту как раз людей, которые могли бы вам принести больше всего дохода.
Ну да. У всех будет тупить понемногу, зато равномерно. И плевать, что этот один человек у вас возникает раз в год и приносит 0.00001% дохода, но вот его мы обеспечим по полной. А так будет сайт тупить, тратить больше памяти, потому что для оптимизации отображения вместо массива будет вхреначено бинарное дерево для упрощенной навигации среди кучи товаров (которая, тем не менее, оказывается нужна одногому человеку в год), и так далее. Положил болт на UX, UI, пользовательсткий опыт — зато блеснем знанием работы алгоримтов.
Если вам вообще интересен качественный код — то Big O ваш лучший друг.
Если вам интересен качественный код — ваш лучший друг это всякие метрики кода, правильное абстрагирование, анализ и проектирование. Как раз с целью того, что бы в дальнейшем узкие или кривые места было довольно легко оптимизировать проведя анализ. И как уже обсуждалось ниже, да Big O вполне может вам помочь выбрать алгоритм или модель данных, если в таких местах реально есть проблема. Потому что довольно часто решения в лоб оказывается достаточно и дальнешие трюки с перформансом оказывают противоположный эффект.
А так будет сайт тупить, тратить больше памяти, потому что для оптимизации отображения вместо массива будет вхреначено бинарное дерево для упрощенной навигации среди кучи товаров (которая, тем не менее, оказывается нужна одногому человеку в год), и так далее.Серьёзно? У вас бинарное дерево будет тупить, когда у вас будет три товара в корзине?
Я боюсь, что если вы так пишите бинарное дерево — то вам уже ничего не поможет.
Если вам интересен качественный код — ваш лучший друг это всякие метрики кода, правильное абстрагирование, анализ и проектирование. Как раз с целью того, что бы в дальнейшем узкие или кривые места было довольно легко оптимизировать проведя анализ.Не видел. Не скажу, что там не бывает, но… не видел. Видел совсем другое: когда люди обнаруживают, что то, что они «напроектировали» с целью «легко оптимизировать проведя анализ» «в дальнейшем» работает медленнее и потребляет ресурсов больше, чем когда вы сразу всё делаете так, чтобы узких мест не было.
Как правило мне удаётся добиться ускорения в 3-5 раз после того, как «специально обученные люди» проводили анализ и «улучшали код».
Исключение — это как раз примерно библиотеки типа Eigen или видеокодеки. Потому что как раз там требования к скорости — максимальны и потому как раз там, почему-то, люди не делают «гибких решений», за которые вы так топите.
Потому что довольно часто решения в лоб оказывается достаточно и дальнешие трюки с перформансом оказывают противоположный эффект.А нет никаких трюков. Нужно просто помнить слова Линуса:
Trust me: every problem in computer science may be solved by an indirection, but those indirections are *expensive*. Pointer chasing is just about the most expensive thing you can do on modern CPU's.
В 9 случаях из 10 именно это даёт результат… после того, как вы учли проблемы, решаемые через Big O, конечно.
Ведь бинарный поиск мы можем осуществлять только если элементы уже отсортированы — но в этом случае поиск дубликатов вообще осуществляется одним проходом и никакой бинарный поиск никому и даром не нужен…
Так-то если данные не отсортированы мы можем отсортировать их (уже потратив минимум O(n log₂n), но потом найдя все дубликаты линейным проходом…
Там просто пример некорректный. А так-то, осуществляя сортировку можно параллельно выкидывать дубликаты, т.е. сложность будет такая же, как от сортировки — потому что для нахождения дубликата нужно лишь посмотреть на соседа, что O(1).
Вот кстати, к слову о нормальных инженерах: хотите быть нормальным инженером — прежде, чем применить алгоритм, проверьте его область применимости.
Кстати подсчет суммы короче можно записать
const sumContiguousArray = function(ary){
//Gauss's trick
return ary.length * (ary.length + 1) / 2;
}
const nums = [1,2,3,4,5];
const sumOfArray = sumContiguousArray(nums);
для последовательности в 8 чисел получится 4+2+1 = 7 операций
в общем случае для подсчета суммы 2^n чисел потребуется 2^n-1 операций сложения
Тут автор не ищет лучшее решение — его цель объяснить сложность алгоритмов «на пальцах». Думаю у него получилось.У него получилось сделать бяку. Как в анекдоте «а о том, как выйти из штопора, смотрите в следующем номере».
Импринтинг — он не только у причек бывает. Человек — тоже склонен использовать то, что он когда-то увидел первый раз. И если человек про Big O не знает — то этот пример легко может запасть ему в душу. И он потом будет вкручивать этот бинарный поиск где нужно и где не нужно.
Разделяй и властвуй (Divide and Conquer) всегда O(log n)
Итерации которые использую Divide and Conquer это O(n log n)
Серьёзно??
Зачем переводить дилентантские высказывания о теории сложности?
Декомпозиция (Divide and Conquer) — это одна из общих парадигм разработки алгоритмов. Логарифм при её использовании действительно появляется часто, но отнюдь не всегда, вообще говоря, вычислительная сложность может быть любой, от O(logN) и выше (как, скажем, в примере с умножением матриц за O(N^(2+ε)), который тут приводили). См. Основную теорему о рекуррентных соотношениях
Я прям порадовался: это ж кем надо быть, чтобы такое породить-то? И да, создатели этого идиотизма — тогда потом отнекивались, что они не хотели показать читателям ничего плохого, хотели просто показать как Prolog может «обратную задачу» решать.
Автор, если ты переводишь на русский, то хотя бы изучи русскоязычную терминологию.
https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
Big O