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

Это не могло быть ошибкой, не так ли?

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

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

Прежде чем я начну клеветать на среднее, давайте поговорим о…

Какие средства подходят для

На приведенной ниже диаграмме представлено распределение с отмеченным средним значением.

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

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

Многие распределения симметричны, поэтому в качестве репрезентативного значения в большинстве случаев хорошим выбором является среднее значение.

Но некоторые распределения несимметричны, например время выполнения функций, и в этих случаях умные деньги не в среднем.

Рассмотрим эту асимметрию подробнее...

Интуиция из постоянно работающей функции

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

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

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

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

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

В этот момент вы можете подумать: «Хорошо, так что минимум — лучший показатель для использования в некоторых случаях, но применим ли он ко всем показателям времени выполнения функции?»

Хороший вопрос, на который ответ - нет, не все, но большинство.

Распределение времени выполнения функций

Если вы запускаете функцию дважды, маловероятно, что каждый раз она будет занимать столько же времени. Но почему бы и нет? Почему функция должна выполняться за 401 мс при одном запуске, а при следующем — 408 мс? Ответ, конечно же: прерывания. У вашего компьютера есть другие дела. Рендерим мышку, проверяем обновления, выносим мусор и тысячу других вещей.

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

Другой способ думать об этом - с точки зрения сигнала и шума. При количественной оценке времени выполнения функции наша задача состоит в том, чтобы собрать некоторые данные и отделить сигнал от шума. Сигнал, который мы ищем, является потенциалом функции. Шум — это прерывания: время, прошедшее во время выполнения функции, но которое мы не должны приписывать репрезентативному времени выполнения функции. На приведенном выше графике плоские линии — это сигнал, который мы хотим извлечь, а горные хребты содержат дополнительный шум; и поскольку шум всегда будет положительным значением, мы можем извлечь сигнал из шума с помощью простой минимальной операции.

Тот факт, что шум всегда положителен, дает нам асимметричное распределение.

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

(Приношу свои извинения читателям-статистикам, которые могут назвать распределение, в котором значения сгруппированы влево, «перекосом вправо». левый.)

На приведенных ниже диаграммах показано по 1000 запусков для каждой из трех различных функций с использованием сочетания вычислений ЦП, чтения с диска и перемещения данных в ГП для некоторых операций CUDA:

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

К этому моменту вы можете подумать: конечно, среднее значение подходит для симметричных распределений, а время выполнения функций имеет тенденцию к отклонению влево, но действительно это имеет значение? Если я возьму среднее значение вместо минимума, приведет ли это когда-нибудь к неправильному решению?

Ответ положительный.

Чтобы исследовать границы этого утверждения, я переключусь на синтетические данные…

Синтетическая установка

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

Я настроил смещение и разброс, чтобы создать два распределения: одно имитирует время выполнения быстрой функции, а другое — функцию, которая на 3% медленнее.

Для последующих экспериментов я выберу 20 значений из распределения быстрой функции и возьму среднее значение. Затем я выберу 20 значений из распределения медленной функции и возьму среднее значение. Если среднее значение для медленной функции выше, чем для быстрой функции, я буду считать это «правильным» результатом. Я повторю все это 500 раз, чтобы мы могли видеть, в каком проценте случаев мы получаем правильный ответ. Тогда я сделаю это снова, взяв минимум вместо среднего.

Хотите рискнуть предположить, в каком проценте случаев среднее значение будет давать правильный ответ (что медленная функция медленнее)? А как же мин?

Я предполагаю, что среднее значение будет правильным в 67,4% случаев, а минимальное значение будет правильным в 94,2% случаев.

Посмотрим, как у нас получилось…

Эта диаграмма может занять некоторое время, чтобы обернуться вокруг... Глядя только на средние значения, каждый из 500 треугольников представляет среднее время выполнения (более 20 запусков) быстрой функции по оси x и среднее время выполнения ( более 20 прогонов) медленной функции по оси y. Если средства для обоих одинаковы, отметка будет на диагональной линии. Если отметка находится над линией, это означает, что среднее значение для медленной функции было больше, что мы считаем правильным (и делаем зеленым). Красные метки под диагональной линией неверны: они представляют сценарий, в котором вы запускали каждую функцию 20 раз, брали средние значения каждой, и сравнение показало, что медленная функция была быстрее.

Я думаю, что это довольно тревожно: у нас есть функция, которая на 3% быстрее, чем альтернатива (неплохое улучшение скорости), и 20 прогонов (приличный размер выборки, особенно для более длительных операций), но использование средств приведет к вы выбираете неправильную функцию почти в трети случаев! Это заставляет меня задаться вопросом, сколько медленных функций было выбрано за эти годы в результате взятия среднего значения.

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

На приведенной ниже диаграмме каждый из 500 экспериментов отмечен синей линией (разница между минимумами 20 запусков каждой из быстрых и медленных функций) и оранжевой линией (то же самое, но с использованием средних). Белая пунктирная линия — это реальная разница во времени работы в 3%.

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

Итак, следует ли выбрасывать среднее значение и всегда использовать минимальное?

О, если бы жизнь была так проста.

Вот еще одна пара смоделированных функций с асимметричными распределениями, но более симметричными, чем предыдущая пара.

Это просто точка пересечения (между левосторонним и симметричным), где среднее и минимальное значения одинаково точны:

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

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

Другой случай, когда среднее значение не вводит в заблуждение (сильно), — это если у вас асимметричное распределение, но довольно большая разница во времени выполнения (ниже медленная функция на 10% медленнее):

В этом случае среднее верно в 95,2% случаев (что приводит к тому, что вы выбираете функцию на 10% медленнее только в 1 случае из 20 — это совершенно нормально, верно?).

Несмотря на менее ужасную производительность среднего значения, min является логичным выбором и здесь удобно правильно в 100% случаев.

Для окончательного синтетического теста давайте посмотрим на влияние размера выборки. Если мы вернемся к первой паре (с разницей в 3%) и смоделируем запуск каждой функции 200 раз вместо 20 (и снова повторим симуляцию 500 раз для каждой функции), мы увидим следующее:

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

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

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

  • fast_function, который делает некоторые вещи, связанные с диском и процессором
  • slow_function, который вызывает fast_function, а затем выполняет другие действия

Я запустил каждую функцию 10 000 раз, затем разделил (перетасованные) времена на 500 пакетов по 20 запусков в каждом, чтобы имитировать среднее значение/мин 20 запусков, 500 раз; та же структура данных, что и в синтетической настройке выше.

Функции довольно быстрые, а распределение не имеет большого перекоса, поэтому оно будет близким:

Это дает результаты, которые не так убедительны, как синтетические данные:

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

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

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

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

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

Представления с потерями и без потерь

Если вы запускаете функцию 10 раз и записываете, сколько времени требуется для выполнения каждый раз, у вас будет 10 чисел и выбор:

  • Сжать эти значения в одно значение (операция с потерями)
  • Посмотрите на все десять значений, чтобы оценить функцию (операция без потерь).

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

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

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

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

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

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

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

(Строго говоря, этот тип диаграммы не всегда без потерь, потому что даже с полупрозрачными линиями 11 линий с одним и тем же значением выглядят так же, как 10 линий. Если вас это не устраивает, другой вариант — полосовой график с дрожанием.)

Другим вариантом без потерь является Эмпирическая функция распределения, которая снова ясно показывает, какая функция способна работать быстрее всего:

Спасибо Бенджамину Скову Каас-Хансену в комментариях, что сообщил мне об их существовании!

По умолчанию я буду использовать гистограмму при общении с другими людьми, поскольку гистограмма требует меньше объяснений. Но когда я хочу принять разумное решение на основе каких-то данных, я использую график событий.

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

Хорошо, теперь мы в конце. Я упоминал, что в конце будет тест?

Заключительный экзамен

Вот небольшой тест, чтобы узнать, поняли ли вы то, что я записываю.

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

Как бы вы объединили 10 измерений в одно значение, чтобы можно было сравнивать конструкции труб?

Если ответ не сразу ясен, возможно, вам поможет график значений для двух труб:

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

Кажется, это хорошее место для вступления…

История этой истории

Около года назад я читал документацию Python, когда наткнулся на этот абзац на странице модуля timeit.

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

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

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

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

Эй, спасибо за чтение! До свидания.