Генерация идеальных функций шага с использованием фактической функции шага

Question

Я построил график времени выполнения (в секундах) по сравнению с графиком ввода для функции следующим образом:

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

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

КРАСНЫЕ точки = время выполнения, которое больше ожидаемого

В следующем случае КРАСНЫЕ точки отображаются в соответствующие ожидаемые времена выполнения:

Но не всегда легко решить, где должны быть нанесены красные точки. Например:

В вышеуказанном случае, как мы решим сопоставить КРАСНУЮ точку с временами выполнения T1 или T2?

Кроме того, существуют следующие случаи, в которых мы не можем быть уверены в том, как сопоставить КРАСНЫЕ точки вниз с их идеальным или ожидаемым временем выполнения:

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

Наконец, может быть много шума, как в следующем случае:

Таким образом, цель состоит в том, чтобы достичь идеальной пошаговой функции с максимально возможной точностью, сопоставляя КРАСНЫЕ точки вниз с их идеальными ожидаемыми временами выполнения

Будет благодарен за любое предложение.

Answer 1

Если время выполнения действительно линейное, как говорит нам график.

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

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

Совет:
При создании линейной регрессии попробуйте разработать метод игнорирования выбросов, чтобы добиться «чистой» регрессии. .

Редактировать:
Дополнительные пояснения

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