Сравнительный анализ: когда я могу прекратить измерения?

Вы задаете два вопроса:

1. Как выполнить проверку статистической значимости того, что среднее время функции A больше, чем среднее время функции B?
2. Если вы хотите быть уверенным в своем ответе, сколько образцов вы должны взять?

Наиболее распространенный ответ на первый вопрос заключается в том, что вы либо хотите вычислить доверительный интервал, либо выполнить t-test. Это ничем не отличается от любого другого научного эксперимента со случайными вариациями. Чтобы вычислить 95-процентный доверительный интервал среднего времени отклика для функции A, просто возьмите среднее значение и добавьте 1,96-кратную стандартную ошибку к любой стороне. Стандартная ошибка — это квадратный корень из дисперсии, деленный на N. То есть

95% CI = mean +/- 1.96 * sqrt(sigma2/N))

где sigma2 — это дисперсия скорости для функции A, а N — это количество прогонов, которые вы использовали для расчета среднего значения и дисперсии.

Ваш второй вопрос касается статистического анализа мощности и планирования экспериментов. Вы описываете последовательную настройку, в которой вы спрашиваете, продолжать ли выборку. Планирование последовательных экспериментов на самом деле представляет собой очень сложную проблему в статистике, поскольку в целом вам не разрешается вычислять доверительные интервалы или p-значения, а затем брать дополнительные выборки при условии, что вы не достигнете желаемой значимости. Если вы хотите сделать это, было бы разумнее настроить байесовскую модель и рассчитать апостериорную вероятность того, что скорость A больше, чем скорость B. Это, однако, огромное излишество.

В вычислительной среде, как правило, довольно тривиально получить очень маленький доверительный интервал как потому, что легко рисовать большие N, так и потому, что дисперсия, как правило, мала — одна функция явно выигрывает.

Учитывая, что Википедия и большинство онлайн-источников по-прежнему ужасны, когда речь идет о статистике, я рекомендую купить Вводная статистика с R. Вы изучите как статистику, так и инструменты для применения того, что вы узнали.

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

Для упрощения: сравните, запуская свой код огромное количество раз, и не беспокойтесь о статистических измерениях.

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

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

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

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

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

Как только вы достигнете диапазона менее миллисекунды — десятков наносекунд — вам понадобятся миллионы итераций.

Не совсем научно, но и не тестирование «в реальном мире» на современной вычислительной системе.

Сравнивая результаты, учитывайте разницу в скорости выполнения в процентах, а не в абсолютном выражении. Все, что меньше 5% разницы, довольно близко к шуму.

Вас действительно волнует статистическая значимость или простая старая значимость? В конечном итоге вам, вероятно, придется составить мнение о читабельности и производительности, и статистическая значимость на самом деле вам не поможет.

Несколько эмпирических правил, которые я использую:

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

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

Фундаментальный вопрос, на который вы пытаетесь ответить, заключается в том, насколько вероятно, что то, что вы наблюдаете, могло произойти случайно? Честна ли эта монета? Бросьте один раз: ГОЛОВЫ. Нет, это несправедливо, это всегда падает орлом. Плохой вывод! Бросьте его 10 раз и получите 7 орлов, что вы теперь сделаете? 1000 раз и 700 голов?

Для простых случаев мы можем представить, как выяснить, когда прекратить тестирование. А у вас немного другая ситуация - вы действительно проводите статистический анализ?

Насколько вы контролируете свои тесты? Добавляет ли их повторение какую-либо ценность? Ваш компьютер детерминирован (возможно). Определение безумия, данное Эйнштейном, состоит в том, чтобы повторять что-то и ожидать другого результата. Итак, когда вы запускаете свои тесты, вы получаете повторяющиеся ответы? Я не уверен, что статистический анализ поможет, если вы делаете достаточно хорошие тесты.

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

У вас есть две основные переменные: сколько итераций вашего метода нужно выполнить в одном тесте? Сколько тестов запустить?

Википедия говорит об этом

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

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

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