Зачем использовать сравнения вместо времени выполнения для сравнения двух алгоритмов?

Я заметил, что в нескольких исследовательских работах по CS, для сравнения эффективности двух алгоритмов, используется общее число ключевых сравнений в алгоритмах, а не реальное время вычислений. Почему мы не можем сравнить, какая из них лучше, запустив обе программы и посчитав общее время, необходимое для запуска алгоритмов?

Это на самом деле глубокая проблема, которая имеет некоторые методические и некоторые прагматические ответы. Я предполагаю, что вы хотите знать кое-что об алгоритме (-ах) под рукой. Если вы хотите знать, какой алгоритм лучше работает на данном компьютере с заданными входами, продолжайте и измерьте время выполнения. Если вы хотите сравнить качество компилятора для данного алгоритма, продолжайте измерять время выполнения. Чтобы узнать что-то об алгоритме, не делайте этого.

Позвольте мне сначала привести несколько причин, по которым использование среды выполнения не очень хорошая идея.

1. всеобщность
   Runtimes измеряется с помощью одного языка и один компилятор на одной машине , имеют мало смысла , если вы изменить какой - либо компонент. Даже немного отличающиеся реализации одного и того же алгоритма могут работать по-разному, потому что вы запускаете некоторую оптимизацию компилятора в одном случае, но не в другом.
2. прогнозирование
   Итак, у вас есть пара времени выполнения для некоторых входных данных. Что это говорит о времени выполнения какого-либо другого ввода? В общем ничего.
3. Значение
   Обычно вы не будете сравнивать все входные данные (некоторого размера), так что это сразу же ограничивает вашу способность сравнивать алгоритмы: может быть, ваш тестовый набор вызвал наихудший случай в одном и лучший случай в другом алгоритме? Или, возможно, ваши входные данные были слишком малы, чтобы продемонстрировать поведение во время выполнения .
4. Замер
   Измерительные автономной работы хорошо не тривиально. Есть ли JIT? Был ли спор, то есть вы считаете время, когда алгоритм даже не запускался? Можете ли вы воспроизвести точно такое же состояние машины для другого прогона (другого алгоритма), в частности параллельных процессов и кэшей? Как бороться с задержкой памяти?

Я надеюсь, что это убедило вас, что время выполнения - ужасная мера для сравнения алгоритмов, и что нужен какой-то общий, абстрактный метод исследования времени выполнения алгоритма.

На второй части вопроса. Почему мы используем сравнения или подобные элементарные операции?

1. Аналитическая управляемость
   Предполагая, что вы хотите сделать формальный анализ, вы должны быть в состоянии сделать это. Подсчет отдельных утверждений очень технический, иногда даже сложный; тем не менее, некоторые люди делают это (например, Кнут). Подсчет только некоторых операторов - тех, которые доминируют во время выполнения - проще. По той же причине мы часто "только" исследуем (верхние границы) время выполнения в худшем случае.

2. Доминирование Выбранная
   операция доминирует во время выполнения. Это не означает, что он вносит большую часть времени выполнения - сравнения явно нет, например, в быстрой сортировке при сортировке целочисленных по размеру слов. Но они выполняются чаще всего , поэтому, подсчитав их, вы посчитаете, как часто выполняются самые исполняемые части алгоритма. Следовательно, ваша асимптотическая среда выполнения пропорциональна числу доминирующих элементарных операций. Вот почему нам удобно использовать нотацию Ландау и слово «время выполнения», хотя мы учитываем только сравнения.

Обратите внимание, что может быть полезно сосчитать более одной операции. Например, некоторые варианты быстрой сортировки требуют больше сравнений, но меньше свопов, чем другие (в среднем).

Что бы это ни стоило, после того, как вы сделали всю теорию, вы, возможно, захотите пересмотреть время выполнения, чтобы убедиться, что предсказания, которые делает ваша теория, являются правильными. Если это не так, ваша теория бесполезна (на практике) и должна быть расширена. Иерархия памяти - это одна из первых вещей, которые, как вы понимаете, важны, но отсутствуют в базовом анализе.

Это связано с тем, что общее время выполнения алгоритмов зависит от оборудования, на котором он работает, а также от других факторов. Ненадежно сравнивать два алгоритма, если один работает на Pentium 4, а другой работает, скажем, на Core i7. Не только это, но допустим, что вы работали на одном компьютере. Что сказать, что они оба имеют одинаковое количество процессорного времени? Что произойдет, если какой-то другой процесс имеет более высокий приоритет, чем процесс одного из алгоритмов?

Чтобы обойти это, мы отделяем это общее время до завершения и вместо этого сравниваем, основываясь на том, насколько хорошо масштабируется алгоритм. Возможно, вы заметили обозначения, такие как O (1) или O (n ^ 2) в исследовательских работах. Для этого может потребоваться немного больше читать, если вы заинтересованы посмотреть Big O нотации .

Поскольку другие ответы объясняют, почему мы анализируем время выполнения с точки зрения количества элементарных операций, позвольте мне предложить несколько причин, почему сравнения являются правильной метрикой многих (не всех) алгоритмов сортировки:

• для многих алгоритмов сортировки число сравнений преобладает во время выполнения, то есть, по крайней мере, столько же сравнений выполняется, сколько и любой другой элементарной операции.
• сравнения дорогие операция; Подумайте, как в библиотеке реализована процедура сортировки: функции сортировки передается массив элементов и указатель на функцию, которая сравнивает два элемента; в общем случае вызов и ожидание выполнения функции сравнения обходятся дороже, чем «внутренние» операции; так как эта функция предоставляется пользователем, ее сложнее оптимизировать
• (это может или не может быть хорошей причиной для некоторых), мы можем сказать что-то интересное о количестве сравнений, которые являются достаточными и необходимыми для сортировки последовательности; мы знаем, как сделать это в наихудшем случае и в среднем для различных распределений, даже как разработать алгоритм, который сходится к оптимальному, поскольку он запускается на элементах, выбранных из неизвестного распределения ( само совершенствующиеся алгоритмы ); мы знаем, как это сделать, когда некоторые сравнения даются бесплатно ( сортировка с частичной информацией )