Как смоделировать время выполнения алгоритмов?

Question

Какие модели времени работы алгоритма существуют?

Мы все ожидаем, что сортировка слиянием будет быстрее, чем сортировка с сортировкой, и отметим, что сортировка слиянием делает O (n log n) сравнений с O (n ² ) для пузырьковой сортировки.

Для других алгоритмов вы учитываете другие операции (кроме сравнения и замены), такие как разыменование указателя, поиск в массиве, арифметика целых чисел фиксированного размера и т. Д.

Какие есть другие способы моделирования времени выполнения?

Один из тех, кого я знаю о себе, считает количество блоков, прочитанных и записанных на диск; см. мой ответ на Когда запись Big-O терпит неудачу? для подробного описания.

Еще один счетчик подсчитывает количество пропущенных кешей. Это расширяет модель ввода-вывода, рассматривая все уровни иерархии памяти.

Третье, для распределенных алгоритмов (например, в безопасных многопартийных вычислениях), заключается в подсчете объема данных, передаваемых по сети (обычно измеряется в раундах связи или количестве сообщений).

Какие еще интересные вещи нужно учитывать (а не считать!), Чтобы предсказать производительность алгоритма?

Кроме того, Насколько хороши эти модели? Насколько я слышал, не обращающие внимания на кэш алгоритмы конкурируют с эффективными алгоритмами ввода / вывода для данных на диске, но не для алгоритмов в памяти.

В частности: в каких конкретных случаях эти модели неверно предсказывают относительную производительность? Согласно моим собственным экспериментам, кучи Фибоначчи не ускоряют кратчайший путь Диджстры (по сравнению с двоичными кучами), когда данные достаточно малы, чтобы поместиться в памяти.

Answer 1

Вы должны определить вычислительную модель, дать оценку стоимости каждой операции, а затем проанализировать свой алгоритм с точки зрения этих затрат; Конечно, затраты определяются конкретной средой и характеристиками базовой машины, на которой вы хотите развернуть свой алгоритм, поэтому вопрос действительно слишком общий.

В курсе алгоритма мы просто предполагаем, что каждая операция стоит 1, поэтому мы просто посчитаем, сколько раз мы выполняем цикл; в алгоритмах, которые работают с основной памятью, мы предполагаем, что каждая операция, кроме чтения / записи из ввода-вывода, стоит 0 (и чтение / запись 1) и т. д.

Эти модели тесно связаны с реальностью? Это зависит от реальности: вашей среды и вашей машины.

Ваш расчет с пропусками в кеше может быть правильным для основного дуэта, но неверным для сотового процессора, где вы должны вручную передать содержимое памяти SPE, например.

Answer 2

Для платформ реального времени, на которых я работаю, в последнее время я обнаружил, что копирование больших объемов данных (например, в диапазоне КБ, а не в диапазоне МБ) на самом деле намного быстрее, чем я ожидал. Возможно, это связано с большими кешами, которые используются сегодня, или, возможно, просто с невероятно высокой скоростью процессора. Но эффект в том, что на самом деле больше не нужно слишком сильно извращать свой код, чтобы избежать копирования данных.

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

Дни, когда драйверы устройств с нулевым буфером были синонимичны со скоростью, прошли.

Answer 3

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

Итак, O (n) моделирует типичную производительность в нормированной среде на входе n.

По расширению можно сказать, что чтения с диска имеют порядок O (n) или что выделения памяти имеют порядок O (n) и так далее. Внешние события, которые создают давление (например, планирование), не должны играть роль в модели типичного времени / пространства / возникновения чего-либо.

Или, может быть, я скучаю по вашей точке (что я подозреваю, что может быть).