Для любого практического применения log(n) можно считать константой. Просто в некоторых компаниях эта константа больше, чем у вас. © народная мудростьПоловину жизни я учу программировать. В том числе учу разработчиков делать быструю оценку вычислительной сложности алгоритма. Зачем?!
На первый взгляд, это довольно академический навык, который не нужен за рамками экзамена по алгоритмам. Однако опытные разработчики используют его ежедневно, не задумываясь, на уровне рефлексов. Делают они это для грубого анализа кода, который читают, пишут или только собираются написать. Обычно быстрого анализа асимптотики достаточно, чтобы исключить случайное появление сильно неэффективного кода.
Сначала разберёмся, как делать оценку сложности, на примере короткой, но нетривиальной задачи. Потом я расскажу, как научится делать экспресс-оценку, и покажу статистику о том, как решали задачу-пример участники конференций Joker и DotNext.
Картинка отсюда.
Задача на Joker 2017 и DotNext 2017 Moscow
Коллеги, которые были прошлой осенью на конференциях Joker в Питере и DotNext в Москве, попросили меня придумать какую-нибудь задачку про сложность для стенда Контура.
Сначала я решил, что сложность — плохая тема, скучная. Но всё таки решил попробовать, и по-моему в результате получилось довольно красиво! Идея родилась легко, по пути домой, а дальше я почти час за клавиатурой пытался оформить её в короткий, но эффектный кусочек кода на C#. Вот что получилось:
private static ISet<string> Compute(int n)
{
var set = new HashSet<string>();
for (int i = 2; i < n; i++)
set.Add(ToBinaryString(i));
for (int step = 2; step < n; step++)
for (int i = 2 * step; i < n; i += step)
set.Remove(ToBinaryString(i));
return set;
}
private static string ToBinaryString(int x)
{
return x == 0 ? "0" : ToBinaryString(x / 2) + x % 2;
}private static Set<String> compute(int n) {
Set<String> set = new HashSet<>();
for (int i = 2; i < n; i++)
set.add(toBinaryString(i));
for (int step = 2; step < n; step++)
for (int i = 2 * step; i < n; i += step)
set.remove(toBinaryString(i));
return set;
}
private static String toBinaryString(int x) {
return x == 0 ? "0" : toBinaryString(x / 2) + x % 2;
}Предлагалось, изучив этот код, ответить на три вопроса:
- Что вообще делает этот странный код?
- Как можно его оптимизировать?
- Какая сложность у функции
Compute(n)?
Наиболее точный ответ на последний вопрос предлагалось выбрать из внушительного списка вариантов:
- O(n)
- O(n?)
- O(n?)
- O(n log(n))
- O(n log?(n))
- O(n log?(n))
- O(n? log(n))
- O(n? log(n))
- O(n? log?(n))
- O(n? log?(n))
- O(n? log?(n))
Здесь самое время налить чашку кофе, прочитать фрагмент кода снова, порассуждать пять минут и выбрать ответ. Дальше будут спойлеры.
Решение
Начнём снизу вверх. Что делает метод ToBinaryString понять несложно — работая рекурсивно, он переводит строку в бинарную запись. Поскольку аргумент уменьшается вдвое на каждом вызове рекурсии, то её глубина — это O(log(x)). Поскольку ветвления рекурсии нет, то тут можно было бы и остановиться, решив, что сложность этой функции O(log(x)).
Но можно проявить чуть больше дотошности и вспомнить про неизменяемость строк в C# и Java. Действительно, конкатенация строк будет приводить к копированию, а значит работать будет за O(длина строки). А значит общая сложность будет чуть хуже логарифма. O(log?(x)) — наш выбор! Конечно, с практической точки зрения разница почти не заметна (см. эпиграф), но для задачки — самое то!
Вернёмся к методу Compute. Сложность первого цикла for — O(n log?(n)). Очевидно, сложность всего метода будет диктоваться более тяжёлыми вложенными for.
Внутренний цикл вложенных for будет делать O(n/step) вызовов ToBinaryString. Значит общая сложность будет O(n/2 + n/3 + n/4 +... n/(n-1)) = O(n(1/2 + 1/3 + ...))
Тут самое время совершить неглубокий нырок из компьютерных наук в матанализ, чтобы вспомнить, что формула в скобках — в точности частичная сумма гармонического ряда. Благо ряд этот изучен вдоль и поперёк. В частности, формула Эйлера сообщает нам, что частичные суммы растут как O(n log(n)). Спасибо, матанализ, пока-пока, до встречи! :)
А значит, вспомнив цену вызова ToBinaryString, оценить сложность нашего алгоритма сверху можно как O(n log?(n)). Это и есть ответ!
Получается, чтобы решить задачу, нужно довольно много:
- знать, что конкатенировать строки плохо
- уметь считать сложность рекурсивных методов
- знать, что remove у HashSet работает эффективно
- уметь сводить оценку сложности вложенных циклов к частичной сумме ряда
- и, наконец, знать про формулу Эйлера для частичной суммы гармонического ряда
Воу! Похоже, довольно круто получилось для такого маленького кусочка кода :)
Что вообще происходит?
Пора понять, что вообще делает этот странный код? Присмотритесь! Это же поиск списка простых чисел — методом недоделанного решета Эратосфена. Действительно, внутренний цикл удаляет каждое второе число, каждое третье и так далее. В итоге останутся только те, которые ни на что не делятся, кроме 1 и себя.
Тут не применены всем известные оптимизации (например, разумный выбор количества итераций циклов), а также добавлена пессимизация в виде ToBinaryString, чтобы совсем запутать. В итоге от исходной сложности O(n log(log(n))) и следа не осталось.
А вот некоторые интересные советы по оптимизации от участников конференций:
- Применить мемоизацию в ToBinaryString. Попросту говоря, кэшировать результат. Очевидно это ускорит работу, но совсем не очевидно, что это улучшит оценку сложности. А действительно улучшит. Как сильно — подумайте сами.
- Использовать не HashSet, а BitArray (C#) / BitSet (Java). Интересное предложение. Чтобы это сделать, придётся хранить в set не строки, а сами числа. А метод ToBinaryString применять только в конце к результату. Но уже один этот рефакторинг улучшит сложность. После этого замена коллекции, наверное, ускорит программу на константу, но на асимптотическую оценку сложности уже не повлияет :)
- Использовать другой алгоритм поиска простых чисел. Например, решето Аткина — за O(n / log(log(n))).
Участники Joker vs. участники DotNext
Статистика!
На Joker задачку решало 86 человек. Из них 8 дали верный ответ O(n log?(n)), а ещё 8 попались на уловку с конкатенацией и ответили O(n log?(n)).
На DotNext задачку решало 69 человек. Из них 10 ответили верно, а ещё 17 человек дали ответ O(n log?(n)). Но далеко идущих холиварных выводов о превосходстве дотнетчиков над джавистами по этой статистике сделать не получится. Мы точно знаем, что на DotNext приехали 49 контуровцев, и у них было преимущество.
Курс по оценке сложности за 2 часа
Вы ещё не забыли, что я учу программировать?
Прошлой осенью я запустил на ulearn.me, «нашей маленькой Курсере», миникурс по экспресс-оценке сложности алгоритмов. Его можно пройти всего за пару часов, он почти не содержит теории, зато придется решить 3 десятка задачек, ведущих вас от простых техник к более сложным. Если разбор этой задачи вам было понять сложновато — курс для вас.
Возможно, этот курс и повлиял на результаты. Тем более, что после Joker я добавил в него разбор элементов этой самой задачки — не пропадать же добру :)
Хотите потратить два часа, чтобы разобраться с экспресс-оценкой и не получить награду в нашей внутренней соцсети? Добро пожаловать на курс.
«Оценка сложности алгоритмов» на ulearn.me
Комментарии (22)
halyavin
12.02.2018 12:18Ответ правильный, но ваше решение неверно. Даже с эффективной ToBinaryString, ответ все равно будет O(nlog3(n)). Метод Remove работает за O(log(n)) сравнений, но каждое сравнение требует O(log(n)) операций, поскольку мы сравниваем строки длины O(log(n)). Прерывание сравнения на первом отличающемся символе не изменяет асимптотики (чем глубже мы в дереве, тем больше совпадающих символов).
halyavin
12.02.2018 12:24Хм. Не заметил, что там HashSet, вместо TreeSet. Тогда не понятно как учитывать хэш-коллизии. Асимптотика может зависеть от хэш-функции.
xoposhiy Автор
12.02.2018 12:27Да, тут этот момент не очень корректен, вы правы. O-оценка подразумевает худший случай, но за сложность операций с HashSet мы взяли их сложность в среднем. Теоретически некорректно, но практически так всегда и делают :)
xoposhiy Автор
12.02.2018 12:34Хотя тут добавляются вполне конкретные числа — подряд. Для них то мы можем быть уверены в амортизированной сложности Add и Remove
green_hippo
12.02.2018 15:11А тут самое время заглянуть в документацию :)
This method is an O(1) operation. — HashSet.Remove() в .NET (https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1.remove?view=netframework-4.7.1)
This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets. — HashSet в JDK (https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html)
Readme
12.02.2018 14:06+1В статье неверно указана ссылка на нужную формулу Эйлера Вообще, этих одноимённых "формул Эйлера" огромное количество в различных областях науки — в экстренной ситуации, если не помнишь название, можно сказать "по формуле Эйлера..." и с ненулевой вероятностью попасть в точку :) Шутка.
Обидно, в этом месте допустил ошибку — и про гармонический ряд знал, и про расходимость, но с асимптотикой частичных сумм промахнулся (почему-то думал, что это
O(n?)).
Вот про конкатенацию строк (и добавочный множитель из-за этого) — интересный момент, действительно, легко проморгать. Хотя это, наверное, больше вопрос к реализации и выбору контейнеров (например, меня, не очень знакомого с C# и Java, даже не сразу триггернуло в этом месте). Как верно заметили выше, можно (и нужно!) тогда копать ещё глубже, и решение становится всё менее очевидным.
xoposhiy Автор
12.02.2018 14:18Спасибо, поправил ссылку на правильную. Слишком плодовитый был этот Эйлер! :)
mayorovp
12.02.2018 16:04Вообще-то конкатенация строк плохо себя ведет в любом языке, не только в C# и Java. Просто потому что конкатенация по определению всегда создает новую строку — и тут уже неважно являются ли строки в языке изменяемыми.
Разве что в случае с Rust есть надежда что компилятор заметит что один из операндов более не используется и подберет более подходящую перегрузку — но для этого надо правильно проставить типы.green_hippo
12.02.2018 16:09Вообще-то конкатенация строк плохо себя ведет в любом языке, не только в C# и Java. Просто потому что конкатенация по определению всегда создает новую строку — и тут уже неважно являются ли строки в языке изменяемыми.
Ох, как хочется заспойлерить содержание одной из следующих статей в блоге Контура — но я пока сдержусь :) Скажу только, что в одном довольно распространённом языке программирования конкатенация строк работает за O(1).
nsinreal
13.02.2018 15:14Только random-access будет работать не за O(1), да? И при выводе строки констата вырастет порядочно.
speshuric
12.02.2018 22:09В теории почти всё так (с упомянутыми оговорками про то, что O — оценка сверху). Но мы же на хабре, тут на слово верят только запустив код :) Я вот решил проверить. Была открыта IDEA, поэтому на Java.
double v = 10; double max = 5000000; double k = 1.1; while (v<max){ long start = System.nanoTime(); Set<String> set = compute((int) v); long elapsed = System.nanoTime() - start; System.out.print((int) v); System.out.print("\t"); System.out.print(set.size()); System.out.print("\t"); System.out.print(elapsed); System.out.println(); v = v * k; }
(Да, я знаю про JMH, да, я знаю что замер не самый удачный)
Ну так вот. Скопировал я результаты в Excel, поигрался. Попробовал найти асимптоту. Оно как бы и находится (у меня коэффициентelapsed/(n*log(n)^3)сходится примерно в 4.5), но погрешность от GC и прочих прелестей делает слабо отличимыми nlog(n)^3 от nlog(n)^2.
А если говорить про решето Эратосфена, то классический список оптимизаций примерно такой:
- Wheel optimization (в простейшем случае проверять только 6n+1, 6n-1 для чисел от 5)
- Конечно перейти к BitArray / BitSet, а скорее всего самим сделать их аналоги, чтобы перейти границу в
maxInt. Это не только улучшит O-оценку, но и позволит на современных машинах легко считать в лоб (в пямяти) решето примерно до 2^37..2^40 (2^33 занимает 1 ГБ). На сладкое — не нужны хеши. - В цикле
for (int step = 2; step < n; step++)не надо идти доn. Достаточно доsqrt(n)(не считая, конечно, его в каждой итерации и аккуратно обработав пограничные случаи). - Этот же цикл должен идти только по простым числам.
- Решето Эратосфена великолепно параллелится. Решето Аткина, кстати, параллелить сложнее. А еще в решете Аткина нужен
flipкоторого нет в .NET BitArray (но мы же решили пилить свой класс) - На десерт можно переписать
toBinaryString()без рекурсии и с более эффективным построением строки.
speshuric
13.02.2018 01:02UPD: dotnet тоже потыкал аналогично:
- Дотнет у меня в тесте слил. Я смотрел на текущем релизном core. JDK какой-то из свежих 1.8
- Картина та же — сходимость "как бы есть", но реально получается что-то между
n*log(n)^3,n*log(n)^2,n*log(n)^2*log(log(n))и прочими подобными вариациями. Если дать голые числа, то зависимость именноn*log(n)^3там найти даже с подсказкой непросто.
(ИМХО) В данном конкретном случае знание оценки в O-нотации не сильно поможет тому, кто оптимизирует этот код:
- Это "решето Эратосфена" не может просчитать и десяток миллионов тупо упираясь в память.
- На алгоритмах "близких к линейным", т.е. все эти
n*log(n)улучшение константного коэффициента даёт существенный эффект. И уж точно даже примитивная wheel optimization выиграет больше (в 3 раза от наивного обхода), чем переход отn*log(n)^3вn*log(n)^2 - Многие алгоритмы перебора или просеивания не имеют красивых и посчитанных O-оценок. Или имею, но именно O — худший случай и это какая-нибудь экспонента от полинома (привет переборщики :) ), но при применении хороших эвристик решение может быть найдено.
IIvana
13.02.2018 01:27Регулярно наблюдаю на самом компетентном математическом форуме рунета очередные темы с предложениями новых авторских алгоритмов, асимптотически превосходящих лучшие существующие аналоги. Где регулярно авторов разочаровывают, что, например, сложение и умножение — это не О(1), а О(n). Вы конечно хитро спрятались за явными интами, но обычно асимптотическую сложность принято оценивать у абстрактного алгоритма без привязки к конкретным деталям реализации убогой конкатенации иммутабельных строк. В том же Хаскеле с его автовыводом типов при автоматическом расширении с интов до интеджеров асимптотика существенно изменится (при одном и том же коде!), но "честная" алгоритмическая останется какой и была. Другое дело, что вы не рассказываете про "честную", а ограничиваетесь кустарной-наколеночной, да еще языко-платформозависимой. Но при этом позиционируете себя как эксперта в этой области, и еще обучаете потенциальных авторов очередных супер-алгоритмов, о которых я писал в начале этого комментария.
olegchir
13.02.2018 13:49+1Но вот в чем проблема — мне вряд ли понадобится Haskell или запись алгоритма на бумажке, а вот на Java нужно писать каждый день.
Atos
13.02.2018 10:52хм, на сабжевом ресурсе как бы есть возможность входа через ВК, но по факту опять же предлагается регистрировать и придумывать пароль. Зачем так?
green_hippo
13.02.2018 14:20Я когда-то спрашивал xoposhiy об этом, причина оказалась довольно юмористическая. Среди пользователей ulearn.me много студентов, а университеты любят внезапно блокировать доступ к поддоменам vk.com из внутренней сети. Тогда студентам не только мемасики не посмотреть, но и курс не пройти. Поэтому сейчас ulearn.me предлагает задать пароль даже при входе через ВК, чтобы был резервный способ входа.
gnkoshelev
13.02.2018 22:47+1Справедливости ради, остаётся недоказанной равносильность перехода от сложности алгоритма for-for-toBinaryString к произведению сложности вложенных циклов for-for и сложности метода toBinaryString, поскольку x в оценке O(log?(x)) метода зависит от состояния цикла.
Выше предлагается эмпирически способ подсчёта вычислительной сложности с засеканием времени. Ещё один альтернативный способ (без необходимости засекать время):
- Заменяем все операции на увеличение счётчика.
- Если количество операций может быть посчитано явно (без необходимости крутить цикл или рекурсию, то прибавляем сразу необходимое количество.
- Делаем для n разного порядка и подбираем подходящую асимптотику.
- Profit!
xoposhiy Автор
15.02.2018 16:58+1Про недоказанность ты заблуждаешься. Некоторых математических упражнений стоит доказательство этого перехода в терминах точной оценки ?. Но в терминах верхней оценки О-большого всё доказывается тривиальным образом: заменяем X на большую величину N. Готово.
ChePeter
Неожиданный взгяд на проблемы сложности алгоритмов.
Обычно оценивается алгоритм, потом только его реализация, котора зависит от железа/системы существенно.
Мне кажется корректно сравнивать реализации одного и того же алгоритма или различные алгоритмы.