Комментарии 24
Обычно оценивается алгоритм, потом только его реализация, котора зависит от железа/системы существенно.
Мне кажется корректно сравнивать реализации одного и того же алгоритма или различные алгоритмы.
А тут самое время заглянуть в документацию :)
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)
В статье неверно указана ссылка на нужную формулу Эйлера Вообще, этих одноимённых "формул Эйлера" огромное количество в различных областях науки — в экстренной ситуации, если не помнишь название, можно сказать "по формуле Эйлера..." и с ненулевой вероятностью попасть в точку :) Шутка.
Обидно, в этом месте допустил ошибку — и про гармонический ряд знал, и про расходимость, но с асимптотикой частичных сумм промахнулся (почему-то думал, что это O(n²)
).
Вот про конкатенацию строк (и добавочный множитель из-за этого) — интересный момент, действительно, легко проморгать. Хотя это, наверное, больше вопрос к реализации и выбору контейнеров (например, меня, не очень знакомого с C# и Java, даже не сразу триггернуло в этом месте). Как верно заметили выше, можно (и нужно!) тогда копать ещё глубже, и решение становится всё менее очевидным.
Разве что в случае с Rust есть надежда что компилятор заметит что один из операндов более не используется и подберет более подходящую перегрузку — но для этого надо правильно проставить типы.
Вообще-то конкатенация строк плохо себя ведет в любом языке, не только в C# и Java. Просто потому что конкатенация по определению всегда создает новую строку — и тут уже неважно являются ли строки в языке изменяемыми.
Ох, как хочется заспойлерить содержание одной из следующих статей в блоге Контура — но я пока сдержусь :) Скажу только, что в одном довольно распространённом языке программирования конкатенация строк работает за O(1).
В теории почти всё так (с упомянутыми оговорками про то, что 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()
без рекурсии и с более эффективным построением строки.
UPD: 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 — худший случай и это какая-нибудь экспонента от полинома (привет переборщики :) ), но при применении хороших эвристик решение может быть найдено.
Регулярно наблюдаю на самом компетентном математическом форуме рунета очередные темы с предложениями новых авторских алгоритмов, асимптотически превосходящих лучшие существующие аналоги. Где регулярно авторов разочаровывают, что, например, сложение и умножение — это не О(1), а О(n). Вы конечно хитро спрятались за явными интами, но обычно асимптотическую сложность принято оценивать у абстрактного алгоритма без привязки к конкретным деталям реализации убогой конкатенации иммутабельных строк. В том же Хаскеле с его автовыводом типов при автоматическом расширении с интов до интеджеров асимптотика существенно изменится (при одном и том же коде!), но "честная" алгоритмическая останется какой и была. Другое дело, что вы не рассказываете про "честную", а ограничиваетесь кустарной-наколеночной, да еще языко-платформозависимой. Но при этом позиционируете себя как эксперта в этой области, и еще обучаете потенциальных авторов очередных супер-алгоритмов, о которых я писал в начале этого комментария.
Выше предлагается эмпирически способ подсчёта вычислительной сложности с засеканием времени. Ещё один альтернативный способ (без необходимости засекать время):
- Заменяем все операции на увеличение счётчика.
- Если количество операций может быть посчитано явно (без необходимости крутить цикл или рекурсию, то прибавляем сразу необходимое количество.
- Делаем для n разного порядка и подбираем подходящую асимптотику.
- Profit!
Наиболее точный ответ на последний вопрос предлагалось выбрать из внушительного списка вариантов.
Экспресс-оценка сложности алгоритма (+разбор задачи c Joker 2017 и DotNext 2017 Moscow)