Любой специалист в области информатики знает, что HeapSort — это O(n log n) наихудший случай в теории, а QuickSort — O(n^2) наихудший случай. Однако на практике хорошо реализованная быстрая сортировка (с хорошей эвристикой) превосходит кучевую сортировку для каждого отдельного набора данных. С одной стороны, мы едва наблюдаем наихудший случай, а с другой стороны, например. Строки кэша ЦП, предварительная выборка и т. д. имеют огромное значение во многих простых задачах. И хотя, например. QuickSort может обрабатывать предварительно отсортированные данные (с хорошей эвристикой) в O(n), HeapSort всегда реорганизует данные в O(n log n), поскольку не использует существующую структуру.
Для моего игрушечного проекта caliper-analyze я недавно искал методы оценки фактическая средняя сложность алгоритмов по результатам сравнительного анализа. В частности, я пробовал подгонку NNLS Лоусона и Хэнсона с различными полиномами.
Однако пока это работает не слишком хорошо. Иногда я получаю полезные результаты, иногда нет. Я полагаю, что это может помочь просто выполнить более крупные тесты, в частности попробовать больше параметров.
Следующие результаты относятся к сортировке объектов Double по шаблону SAW с 10% случайностью. n было только до 500 для этого прогона, так что это не очень репрезентативно для фактического использования... Цифры - это предполагаемая зависимость времени выполнения от размера. Выходные данные редактируются и сортируются вручную, поэтому они не отражают то, что в настоящее время предоставляет инструмент!
BubbleSortTextbook LINEAR: 67.59 NLOG2N: 1.89 QUADRATIC: 2.51
BubbleSort LINEAR: 54.84 QUADRATIC: 1.68
BidirectionalBubbleSort LINEAR: 52.20 QUADRATIC: 1.36
InsertionSort LINEAR: 17.13 NLOG2N: 2.97 QUADRATIC: 0.86
QuickSortTextbook NLOG2N: 18.15
QuickSortBo3 LINEAR: 59.74 QUADRATIC: 0.12
Java LINEAR: 6.81 NLOG2N: 12.33
DualPivotQuickSortBo5 NLOG2N: 11.28
QuickSortBo5 LINEAR: 3.35 NLOG2N: 9.67
Вы можете сказать, что хотя в этой конкретной настройке (часто она работает неудовлетворительно) результаты в значительной степени согласуются с известным поведением: пузырьковая сортировка действительно затратна, а хорошая эвристика на быстрой сортировке намного лучше. Однако, например. Например, быстрая сортировка с эвристикой медианы трех заканчивается оценкой O(n + n^2), в то время как другие быстрые сортировки оцениваются как O(n + n log n).
Итак, теперь к моим актуальным вопросам:
- Знаете ли вы алгоритмы/подходы/инструменты, которые выполняют анализ сложности во время выполнения на основе данных эталонных тестов, чтобы предсказать, какая реализация (как вы можете видеть выше, мне интересно сравнить различные реализации одного и того же алгоритма! ) лучше всего работает на реальных данных?
- Знаете ли вы научные статьи по этому поводу (оценка средней сложности реализации)?
- Знаете ли вы надежные методы подгонки, которые помогут получить здесь более точные оценки? Например. регуляризованная версия NNLS.
- Знаете ли вы эмпирические правила того, сколько образцов нужно, чтобы получить разумную оценку? (в частности, когда инструмент должен воздерживаться от какой-либо оценки, так как она все равно будет неточной?)
И позвольте мне еще раз подчеркнуть, что меня не интересует теоретическая сложность или формальный анализ. Мне интересно посмотреть, как реализации (теоретически даже идентичных алгоритмов) работают с данными тестов на реальных процессорах... Числовые коэффициенты для общего диапазона представляют для меня ключевой интерес, больше чем асимптотическое поведение. (и нет, в долгосрочной перспективе это не только временная сложность и сортировка. Но меня интересуют индексные структуры и другие параметры. А штангенциркуль может, например, также измерять потребление памяти, если я не ошибаюсь) Плюс, я работает в java. Подход, который просто вызывает встроенный Matlab, для меня бесполезен, так как я не живу в мире Matlab.
Если у меня будет время, я попытаюсь повторно запустить некоторые из этих тестов с большим разнообразием размеров, чтобы получить больше точек данных. Может быть, тогда это просто сработает... но я считаю, что есть более надежные методы регрессии, которые я мог бы использовать для получения более точных оценок даже из небольших наборов данных. Кроме того, я хотел бы определить, когда выборка слишком мала, чтобы вообще делать какие-либо прогнозы!
