Сравнение итерационных методов: количество итераций и время процессора

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

performance benchmarking srijan
источник

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

Годрик Провидец

@GodricSeer Ваше изменение улучшило мой вопрос. Спасибо

Сриджан

Ответы:

В общем, оба метода сравнения производительности имеют свое место.

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

Так что, да, имеет смысл дать оба числа [1], и я часто видел это в публикациях. Существует также третий вариант:

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

[1] Определенно представить статистику по нескольким прогонам; если вы показываете средства, не забудьте также включить стандартные отклонения.

Кристиан Клэйсон
источник

Не просто берите средства! Если у вас достаточно тестовых точек со случайными входами, постройте распределение.

Билл Барт

@BillBarth - хорошая мысль, хотя это не всегда возможно; но указание стандартных отклонений вместе со средним всегда должно быть возможным. На самом деле, какие статистические данные для представления о производительности звучат как отличный дополнительный вопрос.

Кристиан Клэйсон

@BillBarth Вы сделали хорошую мысль. Но я использую несколько тестовых матриц в порядке возрастания. Для таких случаев не представляется возможным построить распределение с тех пор, как я должен построить распределение для всех других тестовых матриц. Вот почему я хотел их табулировать. Спасибо за ваши комментарии.

Сриджан

@srijan: У вас будут данные, вы должны составлять гистограммы для себя везде, где сможете. Вам не нужно публиковать их все, но я обещаю вам, что график распределения покажет вам больше, чем море цифр или только средние значения.

Билл Барт

Я бы включил время выполнения на одну итерацию. Поскольку каждая матрица отличается, вы можете иметь разное количество итераций с разным временем выполнения. Вместе с тем, что сказал @Cristian, время выполнения на итерацию будет полезным.

jbcolmenares

Я считаю, что количество итераций является ошибочной метрикой, поскольку она предполагает «скорость», когда это не так. Простой пример сравнения нескольких различных предварительных кондиционеров, показывающих эту разницу, см. Здесь: http://www.dealii.org/developer/doxygen/deal.II/step_6.html#Possabilitiesforextensions

Вольфганг Бангерт
источник

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

Сриджан

Я хочу сказать, что мы часто представляем «количество итераций», эквивалентное «используемому времени процессора», подразумевая, что метод, который требует меньше итераций, также быстрее. Но это не так, как показывают цифры, с которыми я связан.

Вольфганг Бангерт

Теперь я полностью понял вашу точку зрения. То же самое я наблюдал с помощью метода Ньютона для аппроксимации обратной квадратной матрицы. Поскольку порядок метода увеличивается, первоначально время процессора, а также количество итераций уменьшаются, но с увеличением порядка время запуска процессора увеличивается, даже если количество итераций уменьшается. Большое спасибо за ваш ответ.

Сриджан

В случае, если в других ответах неясно, какое количество итераций подходит для аргументов big-O.

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

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

ДОБАВЛЕНО: Кроме того, как я уже указывал в другом месте, для каждого вызова метода обычно есть стоимость установки. Тогда, если матрицы, как правило, не очень велики, эта стоимость установки сама по себе может составлять большую долю процессорного времени (например, удаление из нее будет иметь большую разницу в скорости).

Майк Данлавей
источник