Comments 39
Это должно быть здесь. Доклад Андрея Александреску про алгоритмическую сложность и реальность на CppCon 2019.
Лично я на это не смотрю как показатель скорости алгоритма. Это всего лишь примерная оценка, что бы понять как алгоритм будет себя вести при увеличение данных в 10, 100, 1000 раз.
Так же надо не забывать, что есть ещё константа, которая может быть достаточно высокой, что на маленьком количестве входных данных линейный алгоритм будет медленнее квадратного.
Но если входных данных будет на несколько порядков больше, то высокая константа будет не так страшна и линейный победит.
Конечно, если вы работаете с миллионными массивами, то сравнивать алгоритмы O(n) и O(n²), пожалуй, нет смысла, но в целом финальную скорость лучше, конечно, оценивать на практике, потому как даже log2(1048576) = 20 всего лишь :)
Если вы так не делаете, тогда отлично, значит для вас мои речи не столь актуальны.
Тем не менее, что считать «большими числами»? Миллиард – это много? Однако ж log2(1млрд) ≈ 30. Не такой уж и большой коэффициент в некоторых случаях. Я уже начинаю повторяться :))
Ещё нужно учитывать характер входных данных, которые будут использоваться на практике. Например, по логике их требуется сначала отсортировать за какое-то O(), но по факту они всегда приходят почти отсортированными, надо только пару элементов подвинуть.
Я вообще не думаю про O(), пока не получу первый код и не испытаю его на правильном наборе данных. Код решает практические задачи, а как он себя ведёт на N, стремящемся в бесконечность, вопрос чисто теоретический. На практике бесконечности не существует.
И правильно, чего про O() думать? Все базовые алгоритмы описаны (и реализованы в либах), в большинстве случаев выбор подходящего по этой характеристике – как руки перед едой помыть, умственных усилий не требует.
Хотя, конечно, бывают и ошибки с этим.
2: Авторам описанного и особенно реализованного по барабану, в каком виде у тебя исходные данные. Например, хранить граф или 3-мерную сетку можно десятком способов, удобных для одних целей и неудобных для других. Как ты будешь конвертировать свои конкретные данные в удобный алгоритму/его реализации формат и сколько времени это займёт, никого не интересует.
3: Имеющиеся реализации довольно часто ставят себе целью просто решить задачу, а не решить задачу эффективно или хотя бы аккуратно. Последний пример: искал триангуляцию полигонов для .NET. В реализации популярной библиотеки Poly2Tri элементарная сущность «вершина» описана ссылочным типом. И никак его не заменить на value-тип, не переписывая 2/3 библиотеки. Просто отлично ― больше мусора богу мусора.
1: Вообще-то в описании алгоритма в таком случае обычно будет написано "будем хранить данные в двоичной куче".
2-3: обычно пролетим по скорости, но как правило на ту самую константу, а не до уровня O(n²) вместо O(n) на ровном месте. Т.е. думать об оптимизации всё равно придётся (после поиска узких мест, конечно – всё остальное надо оптимизировать на простоту и понятность кода)
Но в целом Вашу риторику одобряю.
Вывод вроде как противоположный тому, что в заголовке. Асимптотика хороша, когда ехать далеко, а при перемещении на близкие расстояния достаточно велосипеда.
Не только квадратичная, но и линейная может выстрельнуть, т.е. нужно снижать линейную до константной (поиск в массиве -> извлечение из словаря). Может сверху где-то и вылезает N * M или квадраты, но пофиксить представляется возможным только внизу.
Кстати, на тему случайной квадратичности даже сайт есть: https://accidentallyquadratic.tumblr.com/
Как вам такое?Да никак, в принципе. Нотация O-большое показывает исключительно характер роста времени выполнения при неограниченном росте выбранных переменных. Больше ничего. И для потребления памяти такая нотация тоже существует.
Может для кого-то это и не очевидно из-за изначально неправильного понимания, но никакого вскрытия покровов теории и противоречия с ней тут нет.
действительно ли «O» – главный показатель скорости алгоритма?Если один алгоритм выигрывает у другого асимптотически, то, грубо говоря, это значит, что всегда найдётся такой объём входных данных, начиная с которого асимптотически выигрышный алгоритм выполняется быстрее. В отдельных случаях, когда практические объёмы невелики, использование алгоритма с лучшей асимптотикой может быть не выгодно. Но общая закономерность такова, и она не зависит от реальных коэффициентов. По этой причине действительно оценка О-большое является главным показателем скорости алгоритма. Никто никогда нигде не утверждал, что она является достаточной для сравнения времени работы всех частных случаев.
Нотация O-большое показывает исключительно характер роста времени выполнения при неограниченном росте выбранных переменныхЭто (выделенное) ключевой момент, пожалуй. Но в жизни такого не бывает (практически) :)
Если один алгоритм выигрывает у другого асимптотически, то, грубо говоря, это значит, что всегда найдётся такой объём входных данных, начиная с которого асимптотически выигрышный алгоритм выполняется быстрее.Любой алгоритм важен не сам по себе, а применительно к какому-то случаю с данным, имеющими определённый характер (тип, объём, разброс значений и т.д). Не всегда та самая величина, при которой начинается выигрыш, достигается. Собственно, как вы и сами написали:
В отдельных случаях, когда практические объёмы невелики, использование алгоритма с лучшей асимптотикой может быть не выгодно.
И в начале, никто ничего не замечает, зато через полгода-год, если бизнес растет, то проблемы вырастают внушительные и разбираться в 100К строчках кода, в поисках, что же не так в спешке бывает мучительно больно.
Однако ехать на одном колесе всегда не очень удобно. Хоть на переднем, хоть на заднем. Лучше на обоих (а ещё лучше – на 4-х).
Как вариант, в случаях, когда объём данных может сильно меняться (что не всегда, конечно, удаётся предусмотреть заранее), и скорость действительно важна, можно динамически выбирать более эффективный алгоритм.
Вы сравниваете немного разные характеристики. Особенно в пунктах про память и количество тактов на операцию сложения или деления.
Несколько моментов:
есть три функции сложности алгоритма (в плане и памяти и количества операций): big-Oh (O), big-omega (Ω), big-theta (Θ); O(f(n)) — верхняя граница (характеристика), Ω(f(n)) — нижняя граница, Θ(f(n)) — строгое "равно"
все три характеристики определяют порядок роста характеристики (потребление памяти либо количество операций); в университете нам объяснили это в плане математической основы: считайте что алгоритм принимает на вход бесконечно большой (ну или просто крайне большой) объем данных; в таком случае какая разница сколько тактов будет выполняться деление, если оно будет выполнено
n^2, гдеn ~= 10^20? зато в сравнении с алгоритмом где будет выполненоnопераций деления, гдеn ~= 10^20— мы говорим о довольно-таки приличном различии
нужно различать (по крайней мере на собеседованиях в фейсбук и гугл) время выполнения и алгоритмическую сложность алгоритма; в первом случае вы считаете грубое количество операций, во втором — порядок роста этого количества операций
ну и не нужно забывать, что сравнение порядка роста количества операций и порядка роста использования памяти — две разные характеристики алгоритма, и часто на тех же собеседованиях в гуглы-фейсбуки вас попросят (может и неявно) принять решение о ускорении алгоритма благодаря большему потреблению памяти либо сокращению количества выполняемых операций (при этом скорее всего может идти речь попросту о разных структурах данных)
К примеру, при бесконечно большом n сортировка подсчётом для дискретных данных – наилучший алгоритм сортировки. Однако в жизни зачастую n оказывается гораздо меньше возможной величины разброса данных, и этот алгоритм, соответственно, становится не самым лучшим выбором. Даже если не брать во внимание кол-во используемой им памяти.
По большому счёту, статья скорее не о сравнении O(n) и O(n²) для больших n, а о сравнении O(n) и O(n) или O(n²) и O(n²), как в примере с сортировкой пузырьком и вставками. И о сравнении O(n) и O(n·log(n)) при относительно умеренных n. Логарифм в этом случае действительно можно считать константой :)
Вы сравниваете немного разные характеристики.Я их не сравниваю, а говорю, что они тоже имеют место быть и тоже влияют на эффективность алгоритма.
К примеру, при бесконечно большом n сортировка подсчётом для дискретных данных – наилучший алгоритм сортировки
Простите?
Так и быть, поддамся… Насколько я понимаю, сортировка подсчетом имеет сложность O(n) и по времени, и по памяти. Тот же mergesort даст O(log(n)). А теперь сравните n ?= log(n) — даже для чисел больше 2 вы получаете заметную разницу.
Не бывает бесконечно большого кол-ва данных. Бывает конкретный случай применения алгоритма
Ну вот вы опять сравниваете рантайм со сложностью. Конкретику с математической моделью.
Асимптотику используют для сравнения алгоритмов, а не конкретных реализаций на конкретных данных.
Я их не сравниваю, а говорю, что они тоже имеют место быть
Таким образом, даже O(1) в разных алгоритмах могут отличаться на порядки.
Судите сами.
Кстати, по этому же параграфу: никто не считает сложные функции как одну операцию, смело заявляя об О(1). Для оценки сложности сложных алгоритмов используется немного другой подход (выбирается наиболее быстро возрастающая функция из всех функций сложности каждой части алгоритма; иными словами — самая сложная часть и будет сложностью всего алгоритма). А вы считаете такты. Но какая разница сколько тактов выполняется пара умножений в умножении матриц, пусть даже их размерность — тысячи на тысячи, если алгоритм будет при этом множить их десятки раз?
О(1) значит всегда то же, для любых алгоритмов, реализованных на любых ЯПах и выполненных на любых машинах. Хотите считать рантайм (как в вашем высказывании о сложности деления против сложения) — учитывайте и процессор(-ы), на которых эти операции выполняются (не только микрооптимизации процессорные, но и компиляторные — SIMD и прочие изголения в зависимости от целевой платформы).
Тот же mergesort даст O(log(n)).Как вы представляете себе какую-либо сортировку со сложностью меньше, чем O(n)? MergeSort имеет сложность O(n·log(n)).
Асимптотику используют для сравнения алгоритмов, а не конкретных реализаций на конкретных данных.Я с этим и не спорю :)
Однако если в алгоритме «А» 30 циклов сложностью O(n) каждый, а в алгоритме «Б» – один сложностью O(n·log(n)), то «А» будет быстрее лишь при n > 2^30 (≈ 1 млдр). Даже без учёта реализаций. При бесконечном объёме данных (т.е. в нереальном случае) «А», конечно, когда-нибудь победит.
Да и основная моя мысль – это рассмотрение алгоритма с практической точки зрения, где сложность – не единственный важный показатель. К тому же, алгоритм тоже определяет реализацию. Если вам нужно делить, вы никак не сделаете это так же быстро, как сложение. Какой смысл рассматривать эффективность алгоритма вообще без какой-либо привязки к возможной реализации?
Судите сами.Я не вижу противоречия. Возможно, мы говорим о разных вещах, имея в виду фразу «разные характеристики» :)
никто не считает сложные функции как одну операцию, смело заявляя об О(1)Смотря какие. Факториал – да, не считают. А сложение или деление обычно считают.
Но какая разница сколько тактов выполняется пара умножений в умножении матриц, пусть даже их размерность — тысячи на тысячи, если алгоритм будет при этом множить их десятки раз?Не понимаю, что вы хотите сказать. Разве не тем важнее скорость каждой операции, чем больше их кол-во?
Хотите считать рантайм (как в вашем высказывании о сложности деления против сложения) — учитывайте и процессор(-ы), на которых эти операции выполняютсяВ идеале, конечно, и это стоило бы учесть, но предусмотреть такое гораздо сложнее (разве что опробовать на desktop и mobile, к примеру). Учитывайте максимум из того, что можете. Понятное дело, что преимущество на 10% на одной системе может оказаться потерей на других. Но если разница в несколько раз…
Смотрите, мы можем ещё долго рассуждать и спорить о каких-то деталях, но суть статьи я дописал сегодня в разделе «Эпилог», а наглядный пример – это сортировка вставками против сортировки пузырьком. Обе эти сортировки везде обозначаются как O(n²), но на деле отличаются по скорости в разы. В моём тесте – в 7-10 раз, вот "здесь" – в 3 раза. Хотя операции примерно одинаковы, сложность одинакова, да и технически они имеют сходства похожи. И вряд ли на каком-либо процессоре будет иначе.
Тот же mergesort даст O(log(n)).
Вот что я забыл поправить перед отправкой с телефона
сортировка вставками против сортировки пузырьком
В том и суть асимптотической нотации — никто не будет выбирать между двумя алгоритмами O(n^2) — это бессмысленно, как ни посмотри. Сравнивать будут в сторону O(log(n)) и O(n).
Да и, скажем, log(n) может означать как log2(n), так и log10(n), разница между которыми примерно в 3.32 раза.
Обычно это log2. (Бинарные деренья, бинарный поиск)
К слову про сортировки. На случайных данных быстрая сортировка дает на 30% больше сравнений, чем сортировка слиянием, хотя асимптотика в среднем случае у обоих O(n*log(n)). Но при этом влияет природа данных — для массива строк быстрее будет сортировка слиянием, так как сравнение занимает значительное время, а для массива целых чисел быстрее будет быстрая сортировка, за счет того, что обращение к данным идет последовательно, и кэширование в процессоре работает лучше.
В математике нет разницы между i и j.
В компьютерах есть максимальная разница между ними: row major и column major. Locality of reference. У Intel ищите и читайте примеры этому.
Другой важной темой являются бенчмарки внутри кэша (малые N) и бенчмарки в RAM и последующих уровнях памяти. Есть ощущение что только десятки понимают их важность либо просто молчат.
Можно даже говорить и на одной математике далеко не уедешь.
На одной асимптотике далеко не уедешь…