Требуется новая программа, которая принимает в качестве входных данных один или несколько критериев, а затем выводит оценку времени работы или использования памяти.Это проблема машинного обучения.
Ваши входные данные могут быть перечислены как вектор чисел, например:
input = [ A, B, C, D, E ]
Одним из самых простых алгоритмов для этого будет K-алгоритм ближайшего соседа ,Идея заключается в том, что вы берете свой входной вектор чисел и находите в своей базе данных вектор чисел, который наиболее похож на ваш входной вектор.Например, учитывая этот вектор входных данных:
input = [ 11, 1.8, 3557, 29, 10 ]
Вы можете предположить, что время работы и память должны быть очень похожи на значения из этого прогона (первоначально в вашей таблице, указанной выше):
R0001 12 2 3556 27 9
Существует несколько алгоритмов для вычисления подобия между этими двумя векторами, один простой и интуитивно понятный такой алгоритм - это евклидово расстояние .Например, евклидово расстояние между входным вектором и вектором из таблицы выглядит следующим образом:
dist = sqrt( (11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2 )
dist = 2.6533
Интуитивно понятно, что точки с меньшим расстоянием должны быть лучшими оценками для времени выполнения и использования памяти,В качестве расстояния следует описывать сходство между двумя наборами критериев.Предполагая, что ваши критерии информативны и правильно выбраны, точки с аналогичными критериями должны иметь одинаковое время работы и использование памяти.
Вот пример кода того, как это сделать в R:
r1 = c(11,1.8,3557,29,10)
r2 = c(12,2.0,3556,27, 9)
print(r1)
print(r2)
dist_r1_r2 = sqrt( (11-12)^2 + (1.8-2)^2 + (3557-3556)^2 + (27-29)^2 + (9-10)^2 )
print(dist_r1_r2)
smarter_dist_r1_r2 = sqrt( sum( (r1 - r2)^2 ) )
print(smarter_dist_r1_r2)
Взятие времени работы и использования памяти ближайшей строки является алгоритмом KNN для K = 1.Этот подход можно расширить, включив в него данные из нескольких строк, взяв взвешенную комбинацию из нескольких строк из базы данных, причем строки с меньшим расстоянием до входного вектора вносят больший вклад в оценки.Прочтите страницу Википедии в KNN для получения дополнительной информации, особенно в отношении нормализации данных, включая вклады из нескольких точек и вычислительные расстояния.
При расчете разницы между этими списками входных векторов следует подумать о нормализации ваших данных,Основанием для этого является то, что разница в 1 единицу между 3557 и 3556 для критериев C может быть не эквивалентна разнице в 1 между 11 и 12 для критериев A. Если ваши данные обычно распределяются, вы можете преобразовать их все в стандартные баллы (или Z-баллы) с использованием этой формулы:
N_trans = (N - mean(N)) / sdev(N)
Не существует общего решения о "правильном" способе нормализации данных, поскольку он зависит от типа и диапазона данных.что у вас есть, но Z-показатели легко рассчитать и хороший способ попробовать в первую очередь.
Существует много более сложных методов построения оценок, таких как эта, включая линейную регрессию, регрессию опорных векторов и нелинейное моделирование.Идея, лежащая в основе некоторых более сложных методов, заключается в том, что вы пытаетесь разработать уравнение, которое описывает отношение ваших переменных к времени выполнения или памяти.Например, простое приложение может иметь только один критерий, и вы можете попытаться различить такие модели, как:
running_time = s1 * A + s0
running_time = s2 * A^2 + s1 * A + s0
running_time = s3 * log(A) + s2 * A^2 + s1 * A + s0
Идея состоит в том, что A - это ваши фиксированные критерии, а sN - список свободных параметров, которыеВы можете настроить, пока не получите модель, которая работает хорошо.
Одна из проблем этого подхода заключается в том, что существует много разных возможных моделей, которые имеют разное количество параметров.Различение моделей с разным количеством параметров - сложная проблема в статистике, и я не рекомендую заниматься ею во время вашего первого знакомства с машинным обучением.
Некоторые вопросы, которые вы должны задать себе:
- Все ли мои критерии влияют как на время работы, так и на использование памяти?Некоторые из них влияют только на одно или другое, а некоторые бесполезны с точки зрения прогнозирования?Ответ на этот вопрос называется Выбор функции , и является серьезной проблемой в Машинное обучение .
- Есть ли у вас априорные оценки того, как ваши переменные должны влиять на время работы или использование памяти? Например, вы можете знать, что ваше приложение использует алгоритм сортировки по времени N * log (N), что означает, что вы явно знаете связь между одним критерием и временем выполнения.
- Охватывают ли ваши строки измеренных критериев ввода в сочетании со временем выполнения и использованием памяти все возможные варианты использования для вашего приложения? Если это так, то ваши оценки будут намного лучше, так как машинное обучение может испытывать трудности с данными, с которыми оно не знакомо.
- Зависит ли время выполнения и память вашей программы от критериев, которые вы не вводите в свою стратегию оценки? Например, если вы зависите от внешнего ресурса, такого как веб-паук, проблемы с вашей сетью могут повлиять на время работы и использование памяти способами, которые трудно предсказать. Если это так, ваши оценки будут иметь гораздо большее расхождение.