Работа со временем и памятью: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
 
(не показаны 4 промежуточные версии 2 участников)
Строка 1: Строка 1:
На олимпиадах вам часто требуется решить : зайдет ли ваша программа по памяти или по времени. Мы уже рассказали про асимптотику, как же ей пользоваться?  
+
На олимпиадах, перед тем, как начинать писать решение, вам всегда надо сперва ответить себе на вопрос: А зайдёт ли моя программа по памяти и по времени?
  
  
У каждой задачи есть свои ограничения, стандартное : 1 секунда, 128Mb памяти.
+
У каждой задачи есть свои ограничения, стандартное: '''1 секунда, 256Mb памяти'''. Научимся работать с этим.
  
 +
==Время==
  
Научимся работать с этим : Когда вы решаете задачу, удобно полагать, что вы можете делать $2 \cdot 10^8$ простых операций в секунду, если вы пишите на c++, но более правильных подход - честно заслать в систему программу, которая делает $10^8$ операций и посмотреть за сколько она будет работать.  
+
Когда вы решаете задачу, удобно полагать, что вы можете делать $2 \cdot 10^8$ простых операций в секунду, если вы пишите на C++. Однако, эта величина зависит от сервера, на котором работает тестирующая система, и поэтому правильнее сделать следующее(желательно, на пробном туре, дабы не тратить попытки): заслать в систему программу, которая делает $10^8$ операций и заведомо укладывается в ограничения по времени и посмотреть, сколько времени она будет работать.  
  
 +
Итак, вы знаете, какое максимальное число операций ваше решение может себе позволить. Как же теперь оценить, сколько операций выполняет ваше решение? Тут нам на помощь приходит [https://wiki.algocode.ru/index.php?title=O-%D0%BD%D0%BE%D1%82%D0%B0%D1%86%D0%B8%D1%8F_light_version асимптотика]. Зная асимптотику вашего решения, вы можете прикинуть с точностью до константы, сколько действий совершает ваша программа. Например, решение за $O(n^2)$ при $n$ до $10^4$ $~-$ это '''ОК''', при условии, что вы не повторяете ваше решение $100$ раз. А вот решение, которое выполняет около $n^3$ операций при $n$ до $10^3$ $~-$ это уже '''TL'''. 
  
С памятью сложнее. Каждый тип потребляет свое количество байт. Основные типы перечислены ниже :
+
==Память==
  
1) bool - 1 байт
+
С памятью сложнее. Каждый тип потребляет свое количество байт. Основные типы перечислены ниже:
  
2) int - 4 байта
+
# bool - 1 байт (обратите внимание, что хоть bool и несёт в себе 1 бит информации, [https://stackoverflow.com/questions/4626815/why-is-a-boolean-1-byte-and-not-1-bit-of-size в силу некоторых особенностей архитектуры компьютера], на его хранение всё равно выделяется 1 байт памяти)
 
+
# char - 1 байт
3) long long - 8 байт
+
# int - 4 байта
 
+
# long long - 8 байт
4) double - 8 байт
+
# double - 8 байт
  
 +
Теперь давайте посмотрим на вашу программу. Допустим вы используете 3 переменные типа bool, 1 int и массив на 1000 long long. Тогда ваша программа использует - $1000 \cdot 8 + 3 + 4 = 8007$ байт, в 1 килобайте - 1024 байт, следовательно наша программа потребляет меньше 8 килобайт, в мегабайте также 1024 килобайт, следовательно наша программа потребляет гораздо меньше 1 мегабайта памяти и точно подходит под ограничения.
  
Теперь давайте посмотрим на вашу программу. Допустим вы используете 3 переменные типа bool, 1 int и массив на 1000 long long. Тогда ваша программа использует - $1000 \cdot 8 + 3 + 4 = 8007$ байт, в 1 килобайте - 1024 байт, следовательно наша программа потребляет меньше 8 килобайт, в мегабайте также 1024 килобайт, следовательно наша программа потребляет гораздо меньше 1 мегабайта памяти и точно подходит под ограничения.  
+
Следует также помнить, что если ваше решение использует рекурсию, то это приводит к дополнительным небольшим, но всё же затратам памяти, о чём важно помнить, если вы пишете чувствительное к ограничениям по памяти решение.
  
  
{{Автор|Глеб Лобанов|glebodin}}
+
{{Автор|Глеб Лобанов, Александр Гришутин|glebodin}}
 
[[Категория:Анализ времени и памяти]]
 
[[Категория:Анализ времени и памяти]]
 
[[Категория:Работа со временем и памятью]]
 
[[Категория:Работа со временем и памятью]]

Текущая версия на 13:42, 14 сентября 2019

На олимпиадах, перед тем, как начинать писать решение, вам всегда надо сперва ответить себе на вопрос: А зайдёт ли моя программа по памяти и по времени?


У каждой задачи есть свои ограничения, стандартное: 1 секунда, 256Mb памяти. Научимся работать с этим.

Время

Когда вы решаете задачу, удобно полагать, что вы можете делать $2 \cdot 10^8$ простых операций в секунду, если вы пишите на C++. Однако, эта величина зависит от сервера, на котором работает тестирующая система, и поэтому правильнее сделать следующее(желательно, на пробном туре, дабы не тратить попытки): заслать в систему программу, которая делает $10^8$ операций и заведомо укладывается в ограничения по времени и посмотреть, сколько времени она будет работать.

Итак, вы знаете, какое максимальное число операций ваше решение может себе позволить. Как же теперь оценить, сколько операций выполняет ваше решение? Тут нам на помощь приходит асимптотика. Зная асимптотику вашего решения, вы можете прикинуть с точностью до константы, сколько действий совершает ваша программа. Например, решение за $O(n^2)$ при $n$ до $10^4$ $~-$ это ОК, при условии, что вы не повторяете ваше решение $100$ раз. А вот решение, которое выполняет около $n^3$ операций при $n$ до $10^3$ $~-$ это уже TL.

Память

С памятью сложнее. Каждый тип потребляет свое количество байт. Основные типы перечислены ниже:

  1. bool - 1 байт (обратите внимание, что хоть bool и несёт в себе 1 бит информации, в силу некоторых особенностей архитектуры компьютера, на его хранение всё равно выделяется 1 байт памяти)
  2. char - 1 байт
  3. int - 4 байта
  4. long long - 8 байт
  5. double - 8 байт

Теперь давайте посмотрим на вашу программу. Допустим вы используете 3 переменные типа bool, 1 int и массив на 1000 long long. Тогда ваша программа использует - $1000 \cdot 8 + 3 + 4 = 8007$ байт, в 1 килобайте - 1024 байт, следовательно наша программа потребляет меньше 8 килобайт, в мегабайте также 1024 килобайт, следовательно наша программа потребляет гораздо меньше 1 мегабайта памяти и точно подходит под ограничения.

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




Автор конспекта: Глеб Лобанов, Александр Гришутин

По всем вопросам пишите в telegram @glebodin