Блог пользователя arthurkudaynetov

Как реализуется тут замер времени выполнения решений?
Автор arthurkudaynetov, 14 лет назад, По-русски
Интересно узнать, что-то не разберусь с этим :(
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В каком смысле? Каким образом в Windows производить замер времени работы программы? Или просто какие-то общие сведения о контестере?
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В Windows замер. Схему работы контестера знаю. Просто нужно замерить максимально точно время. И хочется знать, как это делается на acm.sgu.ru и тимусе.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Насколько я знаю, используются так называемые Jobs: CreateJobObject, QueryInformationJobObject. Если нужно просто померять время работы чужого процесса, то думаю тот же результат даст функция GetProcessTimes. Если мы внутри процесса и хотим померять своё время - GetTickCount. По идее, более точный результат должна давать QueryPerformanceCounter.


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


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

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        QueryPerformanceCounter точнее, чем GetTickCount? Мне нужно как раз время работы чужого процесса, запускаемого в новом потоке, пишется всё на C#. Я использовал QueryPerformanceCounter из .NET, но мне его точность не понравилась. Еще поробую узнать, как там на Тимусе.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Не уверен, но вообще говоря должен быть точнее. Когда узнаешь про тимус, здесь тоже напиши, интересно.
          → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можете почитать код http://gitorious.org/contester-runlib/mainline/trees/master/src (by stingray)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Пробежал глазами, напоминает мне DLL Injection
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Dll Injection для другой цели. Time Limit контролируется параметрами Job'а, а считывается через GetProcessTimes.
      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        У меня, если выставить TL и ML для Job, процесс обрубается системой только через несколько секунд (вплоть до 10) после превышения квоты на что-либо. Это так и должно быть?
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, вполне. Job объекты работают не очень точно. Но у меня были аналогичные результаты только при превышении времени - ML они отрубали довольно быстро.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Job'ы мне видятся хорошим объектом только для запрета дочерних процессов - это они умеют :)
            А время/память можно отслеживать и каждые eps времени (+WaitForSingleObject, конечно).

            → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите пожалуйста о времени выполнения, например когда пишут log(n) или n(O), что это значит  и как понять за сколько это решение пройдет.
Не нашел тут блога(тему) об этом, если есть дайте ссылку.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Насколько я понял, ты спрашиваешь об оценке ассимптотики.
    Второе ты неправильно написал, нужно писать O(n). Запись O(n) говорит что у тебя программа работает за линейное время, то есть выполнится l*n действий, где l-константа(грубо говоря l циклов for, записанных друг за другом),O(n*n)-что твое решение будет работать за квадрат(то есть выполнится порядка n^2 операций).
    К примеру, чтение и запись массива занимает O(n) времени, бинарный поиск-O(log(n)). Иногда O не пишут а пишут просто log(n).
    Как понять сколько будет работать твоя программа? По ограничениям. Если ограничения по n до 10000, высока вероятность что решение за квадрат зайдет-если оно с небольшой константой l. Если уже порядка 30000-лучше написать что-то побыстрее (скажем за n*log(n))или пытаться отсечь частные случаи. Все понятно?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      го в Кормена. там есть определение)
      я не буду приводить его тут, оно вполне понятно
      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Когда-то давно писал об этом здесь http://fandes.ru/forbeginner/
    → Ответить