Работа со временем и памятью
На олимпиадах, перед тем, как начинать писать решение, вам всегда надо сперва ответить себе на вопрос: А зайдёт ли моя программа по памяти и по времени?
У каждой задачи есть свои ограничения, стандартное: 1 секунда, 256Mb памяти. Научимся работать с этим.
Когда вы решаете задачу, удобно полагать, что вы можете делать $2 \cdot 10^8$ простых операций в секунду, если вы пишите на C++. Однако, эта величина зависит от сервера, на котором работает тестирующая система, и поэтому правильнее сделать следующее(желательно, на пробном туре, дабы не тратить попытки): заслать в систему программу, которая делает $10^8$ операций и заведомо укладывается в ограничения по времени и посмотреть, сколько времени она будет работать.
Итак, вы знаете, какое максимальное число операций ваше решение может себе позволить. Как же теперь оценить, сколько операций выполняет ваше решение? Тут нам на помощь приходит асимптотика. Зная асимптотику вашего решения, вы можете прикинуть с точностью до константы, сколько действий совершает ваша программа. Например, решение за $O(n^2)$ при $n$ до $10^4$ $~-$ это ОК, при условии, что вы не повторяете ваше решение $100$ раз. А вот решение, которое выполняет около $n^3$ операций при $n$ до $10^3$ $~-$ это уже TL.
С памятью сложнее. Каждый тип потребляет свое количество байт. Основные типы перечислены ниже:
- bool — 1 байт (обратите внимание, что хоть bool и несёт в себе 1 бит информации, в силу некоторых особенностей архитектуры компьютера, на его хранение всё равно выделяется 1 байт памяти)
- char — 1 байт
- int — 4 байта
- long long — 8 байт
- double — 8 байт
Теперь давайте посмотрим на вашу программу. Допустим вы используете 3 переменные типа bool, 1 int и массив на 1000 long long. Тогда ваша программа использует — $1000 \cdot 8 + 3 + 4 = 8007$ байт, в 1 килобайте — 1024 байт, следовательно наша программа потребляет меньше 8 килобайт, в мегабайте также 1024 килобайт, следовательно наша программа потребляет гораздо меньше 1 мегабайта памяти и точно подходит под ограничения.
Следует также помнить, что если ваше решение использует рекурсию, то это приводит к дополнительным небольшим, но всё же затратам памяти, о чём важно помнить, если вы пишете чувствительное к ограничениям по памяти решение.
Автор конспекта: Глеб Лобанов, Александр Гришутин
По всем вопросам пишите в telegram @glebodin
сколько операций в секунду выполняет современный домашний компьютер
вообще герци это операций в секунду, дальше подсчитаешь?
зы у амд и интела Разные операции.
I7- 270000000000
AMD Athlon X2 Dual-Core 7850- 3800000000
рассчитуй из объема регистров проца и его тактовой частоты
I7- 270000000000
AMD Athlon X2 Dual-Core 7850- 3800000000
Средний здоровый мозг, все равно всегда будет быстрее, любого чипа. Только вдумайтесь 100 миллиардов нейронов и почти в 10 000 раз больше соединений нейронов аксонов – квадриллион вариантов в секунду просчет нашего мозга. Но это теория по настоящему никто не сможет этого просчитать и все что мы знаем о мозге это тоже теории человека, но в расчетах ученных выходит так. А по факту молитесь что бы никто и никогда не узнал как работает величайшая тайна человечества, или настанет его конец.
Сколько операций в секунду выполняет c
Всем привет ! передо мной стоит задача — вычислить сколько операций
( +, -, *, /) произойдет за секунду для каждого типа.
я начал делать и кажется не правильно (покажу на примере int’ов, операции +)
int a = 0; clock_t start1 = clock(); for(int j = 0;j < 1000; j ++) < for (int i = 0; i < 1000;i++) < a = mas1[i] + mas2[i]; >> long double time = 1000 / ( (long double) (clock() - start1) / CLOCKS_PER_SEC ) * 1000000;В этом фрагменте я выполняю 1.000.000 операций, где mas1 и mas2 — массивы из 1000 элементов, потом в переменную time я :
получаю примерно 20 милисекунд. Делю 1000 (милисекунд в секунде) на результат и умножаю на 1.000.000 (кол-во операций), таким образом получая кол-во операций за секунду.
Прекрасно понимаю что мой алгоритм идиотский, по-этому хотел спросить как его улучшить или переделать)
Последний раз редактировалось ACE Valery; 18.03.2012 в 05:13 .
Сколько операций в секунду выполняет c
m aroonrk → ALGO ARTIS Programming Contest 2023 Autumn（AtCoder Regular Contest 168) Announcement
Algorithms_with_Shayan → Interview with Kavi | Friday 17:00 GMT
Guuber → AlphaGeometry by Deepmind solves IMO geometry problems at IMO medalist level
HelloFromMars → My AtCoder Guest
Una_Shem → AlphaCode (DeepMind) Solves Programming Problems on Codeforces
awoo → Educational Codeforces Round 161 [рейтинговый для Div. 2]
sum → Editorial for Codeforces Round #919 (Div. 2)
a rvindf232 → Please restore Kotlin 1.6
businessmemq → HSE studies
frozenblade → Profound sadness.
awoo → Разбор Educational Codeforces Round 159
Kolyanchick → День 41 (Эксперт за 100 дней)
Nickir → Grey Lives Matter!
xcx0902 → About pretests and hacks
Kolyanchick → День 40 (Эксперт за 100 дней)
arpitP → CSES COIN PILES
3zim → Pupil at CodeForces
Plurm → Sore loser
DiMaRiK01 → Что делать, если не проходит задача?
Merazul-Islam → Rate My art
parveen1981 → I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021]
pashka → Editorial for Codeforces Round 920 (Div. 3)
127.0.0.1 → Codeforces Round 907 (Div. 2) Editorial
Arpa → Algoritmi Competitive Programming Academy
scobik → Rate my art!