Программное получение эффективности кода Big-O
https://stackoverflow.com/questions/480775
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Интересно, существует ли какой-либо автоматический способ определения (хотя бы грубо) временной сложности Big-O данной функции?
Если бы я построил график зависимости функции O(n) отфункция O(n lg n), я думаю, я смогу визуально определить, что есть что;Я думаю, что должно быть какое-то эвристическое решение, которое позволит делать это автоматически.
Есть идеи?
Редактировать: Я рад найти полуавтоматическое решение, просто интересно, есть ли способ избежать полностью ручного анализа.
Решение
Похоже, то, о чем вы просите, является продолжением проблемы остановки.Я не верю, что такое возможно, даже теоретически.
Просто отвечая на вопрос "Будет ли эта линия кода когда -либо запускаться?" было бы очень сложно, если не невозможно сделать в общем случае.
Отредактировано, чтобы добавить:Хотя общий случай неразрешим, см. здесь частичное решение: http://research.microsoft.com/apps/pubs/default.aspx?id=104919
Кроме того, некоторые заявляют, что проведение анализа вручную — единственный вариант, но я не считаю, что это действительно правильный подход.Неразрешимая проблема остается неразрешимой, даже если в систему/машину добавлен человек.После дальнейшего размышления я предполагаю, что 99%-ное решение может быть выполнимо и даже может работать так же хорошо или даже лучше, чем человек.
Другие советы
Вы можете запустить алгоритм на наборах данных различного размера, а затем использовать аппроксимацию кривой, чтобы получить аппроксимацию.(В большинстве случаев, вероятно, будет достаточно просто взглянуть на созданную вами кривую, но любой статистический пакет имеет возможность подгонки кривой).
Обратите внимание, что некоторые алгоритмы демонстрируют одну форму при небольших наборах данных, а другую при больших...а определение «большого» остается несколько расплывчатым.Это означает, что алгоритм с хорошей кривой производительности может иметь настолько большие накладные расходы в реальном мире, что (для небольших наборов данных) он не будет работать так же хорошо, как теоретически лучший алгоритм.
Насколько проверка кода техники, их не существует.Но настроить код для работы различной длины и вывести простой файл (RunSize RunLength будет достаточно) должно быть легко.Генерация правильных тестовых данных может быть более сложной (некоторые алгоритмы работают лучше/хуже с частично упорядоченными данными, поэтому вам нужно сгенерировать данные, которые представлял ваш обычный вариант использования).
Из-за проблем с определением понятия «что такое большое» и того факта, что производительность зависит от данных, я считаю, что статический анализ часто вводит в заблуждение.При оптимизации производительности и выборе между двумя алгоритмами единственным окончательным арбитром, которому я доверяю, является реальный тест «резина отправляется в путь».
Короткий ответ заключается в том, что это невозможно, потому что константы имеют значение.
Например, я мог бы написать функцию, которая работает в O((n^3/k) + n^2).Это упрощается до O(n^3), потому что когда n приближается к бесконечности, n^3 член будет доминировать над функцией, независимо от константы k.
Однако, если k очень велик в приведенном выше примере функции, функция будет работать почти точно n^2 до некоторой точки пересечения, в которой n^3 термин начнет доминировать.Потому что константа k будет неизвестен ни одному инструменту профилирования, будет невозможно узнать, насколько велик набор данных для тестирования целевой функции.Если k может быть сколь угодно большим, вы не можете создать тестовые данные для определения времени работы «большого ома».
Мне любопытно, почему вы хотите иметь возможность это сделать.По моему опыту, когда кто-то говорит:«Я хочу выяснить сложность этого алгоритма во время выполнения», они не спрашивают то, что, по их мнению, они спрашивают.Скорее всего, вы спрашиваете, какова реальная производительность такого алгоритма для вероятных данных.Вычисление Big-O функции имеет разумную полезность, но существует так много аспектов, которые могут изменить «реальную производительность алгоритма во время выполнения» при реальном использовании, что ничто не сравнится с инструментированием и тестированием.
Например, следующие алгоритмы имеют один и тот же Big-O (дурацкий псевдокод):
пример а:
huge_two_dimensional_array foo
for i = 0, i < foo[i].length, i++
for j = 0; j < foo[j].length, j++
do_something_with foo[i][j]
пример б:
huge_two_dimensional_array foo
for j = 0, j < foo[j].length, j++
for i = 0; i < foo[i].length, i++
do_something_with foo[i][j]
Опять то же самое большое-О...но один из них использует порядковый номер строки, а другой — порядковый номер столбца.Оказывается, из-за локальности ссылок и согласованности кэша у вас может быть два полностью разное фактическое время выполнения, особенно в зависимости от фактического размера массива foo.Это даже не касается реальных характеристик производительности алгоритма, если он является частью программного обеспечения, в котором встроена некоторая параллельная обработка.
Не хочу быть негативным, но «большое О» — это инструмент с узкой сферой применения.Это очень полезно, если вы глубоко разбираетесь в алгоритмическом анализе или пытаетесь доказывать кое-что об алгоритме, но если вы занимаетесь разработкой коммерческого программного обеспечения, доказательство находится в пудинге, и вам понадобятся реальные показатели производительности, чтобы принимать разумные решения.
Ваше здоровье!
Я удивлен, увидев так много попыток заявить, что можно «измерить» сложность с помощью секундомера.Несколько человек дали правильный ответ, но я думаю, что еще есть возможность донести суть вопроса.
Сложность алгоритма — это не вопрос «программирования»;это вопрос «информатики».Ответ на этот вопрос требует анализа кода с точки зрения математика, так что вычисление сложности Big-O является практически формой математического доказательства.Это требует очень глубокого понимания фундаментальных компьютерных операций, алгебры, возможно, исчисления (пределов) и логики.Никакое количество «тестирования» не может заменить этот процесс.
Применяется проблема остановки, поэтому сложность алгоритма принципиально неразрешима для машины.
Применяются ограничения автоматизированных инструментов, поэтому можно было бы написать программу, которая могла бы помочь, но она сможет помочь лишь в той мере, в какой калькулятор помогает при выполнении домашнего задания по физике или в той мере, в какой браузер, осуществляющий рефакторинг, помогает в реорганизации базы кода.
Тем, кто серьезно подумывает о написании такого инструмента, я предлагаю следующее упражнение.В качестве предметного алгоритма выберите достаточно простой алгоритм, например ваш любимый.Получите надежный справочник (книгу, веб-руководство), который поможет вам выполнить процесс расчета сложности алгоритма и, в конечном итоге, «Большого О».Документируйте свои шаги и результаты по мере прохождения процесса с помощью алгоритма вашего предмета.Выполните действия и задокументируйте свой прогресс для нескольких сценариев, таких как наилучший, наихудший и средний вариант.Закончив, просмотрите документацию и спросите себя, что потребуется, чтобы написать программу (инструмент), которая сделает это за вас.Можно ли это сделать?Сколько на самом деле будет автоматизировано, а сколько останется вручную?
С наилучшими пожеланиями.
Это могло бы сработать для простых алгоритмов, но как насчет O(n^2 lg n) или O(n lg^2 n)?
Вас очень легко обмануть визуально.
И если это действительно плохой алгоритм, возможно, он не вернет результат даже при n = 10.
Доказательство того, что это неразрешимо:
Предположим, что у нас есть некоторый алгоритм HALTS_IN_FN(Program, function), который определяет, остановилась ли программа за O(f(n)) для всех n и для некоторой функции f.
Пусть P — следующая программа:
if(HALTS_IN_FN(P,f(n)))
{
while(1);
}
halt;
Поскольку функция и программа фиксированы, HALTS_IN_FN на этом входе имеет постоянное время.Если HALTS_IN_FN возвращает true, программа работает вечно и, конечно, не останавливается в O(f(n)) ни при каком f(n).Если HALTS_IN_FN возвращает false, программа останавливается за время O(1).
Таким образом, мы имеем парадокс, противоречие, а значит, программа неразрешима.
Я думаю, что сделать это автоматически практически невозможно.Помните, что O(g(n)) — это верхняя граница наихудшего случая, и многие функции работают лучше, чем эта граница, для многих наборов данных.Вам придется найти набор данных для наихудшего случая для каждого из них, чтобы сравнить их.Это сложная задача сама по себе для многих алгоритмов.
Джеффри Л. Уитледж прав.Простое сокращение проблемы остановки доказывает, что это неразрешимо...
ТАКЖЕ, если бы я мог написать эту программу, я бы использовал ее для решения P и NP и имел бы 1 миллион долларов...Б-)
Многие люди отметили, что это теоретически неразрешимая проблема.Это справедливо, но помимо этого, даже решение этой задачи для любого, кроме самого тривиального случая, может показаться невероятно трудным.
Предположим, у вас есть программа с набором вложенных циклов, каждый из которых основан на количестве элементов в массиве.О(п^2).Но что, если внутренний цикл запускается только при очень специфическом стечении обстоятельств?Скажем, в среднем он запускается примерно в log(n) случаях.Внезапно наш «очевидно» алгоритм O(n^2) на самом деле стал O(n log n).Написать программу, которая могла бы определить, будет ли выполняться внутренний цикл и как часто, потенциально сложнее, чем исходная задача.
Помните, что O(N) не бог;высокие константы могут и изменят игровое поле.Алгоритмы быстрой сортировки, конечно, являются O(n log n), но когда рекурсия становится достаточно маленькой, скажем, до 20 элементов или около того, многие реализации быстрой сортировки изменят тактику на отдельный алгоритм, поскольку на самом деле быстрее выполнять другой тип сортировки. , скажем, сортировка вставками с худшим O(N), но с гораздо меньшей константой.
Итак, изучите свои данные, сделайте обоснованные предположения и протестируйте.
Что ж, поскольку вы не можете доказать, останавливается ли функция вообще, я думаю, вы требуете слишком многого.
В противном случае он есть у @Godeke.
Вы также должны соблюдать осторожность при выполнении таких тестов.Поведение некоторых алгоритмов сильно зависит от типа входных данных.
Возьмем, к примеру, быструю сортировку.Это наихудший случай O(n²), но обычно O(nlogn).Для двух входов одинакового размера.
Коммивояжер — это (думаю, не уверен) O(n²) (РЕДАКТИРОВАТЬ:правильное значение — 0(n!) для алгоритма грубого перебора.) , но большинство алгоритмов гораздо быстрее получают довольно хорошие приближенные решения.
Это означает, что структуру бенчмаркинга в большинстве случаев приходится адаптировать на разовой основе.Представьте себе, что вы пишете что-то общее для двух упомянутых примеров.Это было бы очень сложно, вероятно, непригодно для использования и, вероятно, в любом случае будет давать неверные результаты.
Я думаю, что это невозможно полностью автоматическим способом, поскольку тип и структура ввода сильно различаются между функциями.
Я не знаю, какова ваша цель, но у нас была похожая проблема на курсе, который я вел.От студентов требовалось реализовать что-то, работающее при определенной сложности.
Чтобы не просматривать их решение вручную и не читать их код, мы использовали метод, предложенный @Godeke.Целью было найти студентов, которые использовали связанный список вместо сбалансированного дерева поиска, или студентов, которые реализовали пузырьковую сортировку вместо пирамидальной сортировки (т.реализации, которые не работают в необходимой сложности — но без фактического чтения их кода).
Удивительно, но результаты не выявили студентов, которые списывали.Возможно, это потому, что наши студенты честны и хотят учиться (или просто знали, что мы это проверим ;-)).Студентов-обманщиков можно не заметить, если входные данные малы или если сами входные данные заказаны или что-то в этом роде.Также можно ошибаться в отношении студентов, которые не списывали, но имеют большие постоянные значения.
Но, несмотря на возможные ошибки, оно того стоит, поскольку экономит много времени на проверку.
Как уже говорили другие, это теоретически невозможно.Но на практике вы может сделать обоснованное предположение о том, является ли функция O(н) или О(н^2), если вы не против иногда ошибаться.
Впервые алгоритм, запускающий его на входе различных н.Нанесите точки на логарифмический график.Проведите через точки наиболее подходящую линию.Если линия хорошо соответствует всем точкам, то данные свидетельствуют о том, что алгоритм имеет вид O(н^к), где к это наклон линии.
Я не статистик.Ко всему этому следует относиться с недоверием.Но на самом деле я сделал это в контексте автоматического тестирования снижения производительности. Патч здесь содержит некоторый JS-код для него.
я использую big_O библиотека (ссылка здесь), который соответствует изменению времени выполнения независимой переменной n вывести порядок классов роста O().
Пакет автоматически предлагает наиболее подходящий класс, измеряя остаток собранных данных от поведения роста каждого класса.
Проверьте код в этот ответ.
Пример вывода,
Measuring .columns[::-1] complexity against rapid increase in # rows
--------------------------------------------------------------------------------
Big O() fits: Cubic: time = -0.017 + 0.00067*n^3
--------------------------------------------------------------------------------
Constant: time = 0.032 (res: 0.021)
Linear: time = -0.051 + 0.024*n (res: 0.011)
Quadratic: time = -0.026 + 0.0038*n^2 (res: 0.0077)
Cubic: time = -0.017 + 0.00067*n^3 (res: 0.0052)
Polynomial: time = -6.3 * x^1.5 (res: 6)
Logarithmic: time = -0.026 + 0.053*log(n) (res: 0.015)
Linearithmic: time = -0.024 + 0.012*n*log(n) (res: 0.0094)
Exponential: time = -7 * 0.66^n (res: 3.6)
--------------------------------------------------------------------------------
Если у вас много однородных вычислительных ресурсов, я бы сопоставил их с несколькими выборками и выполнил линейную регрессию, а затем просто взял бы самый высокий член.
Легко получить указание (например,«является ли функция линейной?сублинейный?полином?экспоненциальный")
Трудно найти точную сложность.
Например, вот решение Python:вы предоставляете функцию и функцию, которая создает для нее параметры размера N.Вы получаете список значений (n, time) для построения графика или выполнения. регрессивный анализ.Он рассчитывает скорость один раз, чтобы получить действительно хорошие показания, ему придется рассчитывать время много раз, чтобы минимизировать влияние факторов окружающей среды (например,с время модуль).
import time
def measure_run_time(func, args):
start = time.time()
func(*args)
return time.time() - start
def plot_times(func, generate_args, plot_sequence):
return [
(n, measure_run_time(func, generate_args(n+1)))
for n in plot_sequence
]
И чтобы использовать его для сортировки пузырьком времени:
def bubble_sort(l):
for i in xrange(len(l)-1):
for j in xrange(len(l)-1-i):
if l[i+1] < l[i]:
l[i],l[i+1] = l[i+1],l[i]
import random
def gen_args_for_sort(list_length):
result = range(list_length) # list of 0..N-1
random.shuffle(result) # randomize order
# should return a tuple of arguments
return (result,)
# timing for N = 1000, 2000, ..., 5000
times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000))
import pprint
pprint.pprint(times)
Это напечатано на моей машине:
[(1000, 0.078000068664550781),
(2000, 0.34400010108947754),
(3000, 0.7649998664855957),
(4000, 1.3440001010894775),
(5000, 2.1410000324249268)]
