Время выполнения и память

ProgramBox

Время выполнения и память

Post author:admin
Запись опубликована:8 июля, 2022
Post category:Вопросы по программированию

memory #big-o

#память #большая ошибка

Вопрос:

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

1. Если вы можете запустить его, есть много вариантов. Запустите его с помощью callgrind и посмотрите поведение. Передайте различные аргументы и посмотрите, изменится ли поведение функции. Вы не видите код внутри, вы просто меняете внешнюю среду.

2. @Jack: хотя я проголосовал против, посмотрите на мой ответ, почему этот подход не решит проблему (следовательно, он не обрабатывает O (бесконечные) функции)

Ответ №1:

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

 void DoSomething(int x, int y, int z);

Может быть реализовано как O (1) время и память:

 void DoSomething(int x, int y, int z) { }

или как очень, очень дорогая функция, принимающая O (x * y * z):

 void DoSomething(int x, int y, int z)
{
  int a = 0;
  for (int i = 0; i < x; i  ) {
    for (int j = 0; j < y; j  ) {
      for (int k = 0; k < z; k  ) {
        a  ;
      }
    }
  }
  Console.WriteLine(a);
}

И многие другие возможности. Таким образом, невозможно определить, насколько дорогая функция.

1. Это невозможно, только если вы не можете запустить функцию или можете запустить ее только небольшое количество раз.

2. Интересно, это то, что я подумал. Это вопросы для интервью, и я подумал, что это вопрос с подвохом

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

Ответ №2:

Разрешено ли мне вообще запускать функцию? Несколько раз?

Я бы выполнил функцию с диапазоном значений параметров и измерил время выполнения и (если возможно) потребление памяти для каждого запуска. Затем, предполагая, что функция принимает n аргумент, я бы нанес каждую точку данных на n 1 трехмерный график и оттуда искал тенденции.

Ответ №3:

Прежде всего, это вопрос интервью, поэтому вам лучше никогда не говорить «нет».

Если бы я был на собеседовании, вот мой подход.

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

Поскольку я не вижу код, я полагаю, что смогу, по крайней мере, запустить его, надеюсь, несколько раз. Это был бы мой первый вопрос: могу ли я его запустить? (Если я не могу его запустить, я буквально ничего не могу с этим сделать, и я сдаюсь.)

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

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

1. @Dante: дело в том, чтобы посмотреть, можете ли вы уменьшить проблему HP, которая известна как неразрешимая (подробности см. В Моем ответе).

2. @amit, мы не видим код. Таким образом, мы должны сделать несколько предположений. Если он не может быть завершен за пороговое время, я просто рассматриваю его как O (бесконечный). Кстати, это на самом деле рассматривается в моем ответе (если интервьюер расскажет мне что-нибудь о HP, поскольку он интерактивный ). «Для чего используется функция?»

3. @Dante: определите «пороговое время». как бы вы определили, является ли это O (бесконечность) или O (100 ^ n ^ n)?

4. @amit, звучит как жесткий интервьюер? Я бы сказал: согласно моим знаниям до сих пор (я, вероятно, знал, для чего используется функция, и какая машина ее запускает), я бы выбрал пороговое значение. Например, функция используется для поиска 1000-го числа Фибоначчи (примите один аргумент за 1000), я думаю, это займет не более 1 минуты на компьютере с основным потоком. Если он продолжит работать через 1 минуту, я бы (по крайней мере) сказал, что с функцией что-то не так.

5. @Dante: иногда они задают проблемы без решений, моего друга спросили: «Как вы можете найти элемент в несортированном списке с большей сложностью, чем O (n)» — что невозможно. и «невозможно» был правильным ответом.

Ответ №4:

Можете ли вы запустить функцию с помощью кода? что-то вроде этого:

 start = clock();
//call the function;
end = clock();
time = end-start;

Ответ №5:

Будучи вопросом интервью, вы никогда не должны отвечать так: «нет, это невозможно сделать».

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

Для обозначений типа big-O вы также можете следовать тому же подходу и отображать результаты с учетом размера набора данных. Затем попробуйте сопоставить эту кривую с известными кривыми сложности, такими как n, n ^ 2, n ^ 3, n * log (n), (n ^ 2) * log (n) и т. Д., Используя метод наименьших квадратов.

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

1. смотрите мой ответ, почему «нет» является правильным ответом на этот вопрос. кроме того, смотрите Комментарии под ответом @ Dante об обсуждении: «Вы никогда не должны отвечать «нет» на вопрос интервью?»

2. @amit, хотя может быть правдой, что интервьюер искал глубокие концепции CS, такие как HP, я чувствую, что приблизительный ответ всегда лучше, чем сказать «нет». Многие проблемы в CS являются NP-сложными или неразрешимыми, но в реальном мире нам приходится довольствоваться любым ближайшим приближением, с которым мы можем справиться.

3. это не проблема P / NP, это проблема R / RE. Я бы ответил «нет» (по причине проблемы с остановкой), а затем сказал, что если мы знаем, что программа в конечном итоге завершится, возможно, удастся получить эвристику. хотя я почти уверен, что интервьюер хотел услышать о HP в ответе.

Ответ №6:

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

1. Я бы опубликовал комментарий от того, кто проголосовал против меня, чтобы я мог учиться на своих ошибках.

2. Я не отрицал вас, но ваш пример O (infinity) излишне пессимистичен. Если бы я поручил вам задачу оценки сложности какой-либо функции, а вы вернулись, сказав, что это невозможно сделать в общем случае, чтобы вы не пытались выполнить эту конкретную задачу, я бы вообще не был очень доволен…. Важным является практический подход к попытке найти наилучший возможный ответ. Полезно знать, является ли этот подход пуленепробиваемым, но может представлять не больший интерес, чем то, что компьютер может быть поражен молнией до завершения тестирования….

Метки: Время выполнения и память