Работа со временем и памятью
На олимпиадах, перед тем, как начинать писать решение, вам всегда надо сперва ответить себе на вопрос: А зайдёт ли моя программа по памяти и по времени?
У каждой задачи есть свои ограничения, стандартное: 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
Количество операций в секунду
Количество импульсов в секунду
Доброго времени суток! Помогите, кто чем может )) На цифровой вход некоторого оборудования.
Написать программу, определяющую, какое количество операций умножения выполняется за 1 секунду
Написать программу, определяющую, какое количество операций умножения выполняется за 1 секунду.
сколько операций в секунду?
доброго времени суток подскажите сколько операций считывания из регистра в секунду может сделать.
Определение числа операций в секунду
Требуется определить, какое число операций выполнит программа за одну секунду. Например, чему.
1856 / 713 / 55
Регистрация: 11.12.2008
Сообщений: 1,019
Сделать «чистый» тест довольно сложно, так как на него будут давать влияния проверок условия цикла, «перепрыги», всяческие оптимизации компилятора(их нужно было бы удалить), да и одни прибавления начнут обрабатываться процессором совершенно не так, как если бы они были в составе других операций.
Обычный таймер слишком малоточный, чтобы им измерять. Воспользуйся высокоточным таймером, и выполни много много операций, и замерь время их выполнения, а потом зная частоту таймера и количество операций, можно посчитать, сколько же операций было за одну секунду.
Вот тебе примерчик(я надеюсь я не затупил с вычислением количества операций на основе полученных данных):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
void __fastcall TForm1::Button1Click(TObject *Sender) { int x=0; LARGE_INTEGER start; QueryPerformanceCounter(&start); for(int i=0;i100000000;i++) { x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; x++; } LARGE_INTEGER end; QueryPerformanceCounter(&end); __int64 diff=end.QuadPart-start.QuadPart; LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); __int64 count=(freq.QuadPart*10000000000)/diff; Label1->Caption=IntToStr(count); }
Большое количество операций x++(их, вроде как, 100) сделано для того, чтобы сгладить влияния обработки служебных операций самого оператора цикла.
О лживых постах в ВК или сколько операций в секунду выполняет мозг человека
На написание этой статьи меня побудил пост одного из популярных пабликов ВКонтакте, в котором дословно было следующее: «Человеческий мозг в состоянии выполнять 1016 операций в секунду. Это значит, что его мощность до сих пор выше, чем мощность любого существующего на сегодняшний день компьютера.». Я разобрался кто круче, мозг, или компьютер.
Для начала разберемся, что это за операции в секунду, какова мощность вашего настольного компьютера, и какова мощность самого супермегапапского компа на планете.
Для измерения вычислительной мощности компьютеров используется единица измерения, называемая флопс (flops, flop/s). Флопс показывает, сколько операций с плавающей запятой выполняет компьютер за одну секунду. Кроме того, для измерения вычислительной мощности используется такое понятие, как тактовая частота. Тактовая частота процессора показывает, какое количество основных операций выполняет процессор в секунду, и измеряется в герцах. Основная операция, выполняемая процессором, может включать в себя множество операций с плавающей запятой, поэтому результаты измерения в флопсах и герцах различаются. Если вы найдете у себя на рабочем столе иконку «Мой компьютер», кликните по ней правой копкой мыши, в выпадающем меню откроете свойства, то истина для вас откроется. Найдите в открывшемся окне заголовок «Ситема», и там, напротив слова «процессор» будет указана тактовая частота вашего процессора. Скорее всего она будет иметь такой вид: «2.10 GHz». Число может незначительно отличаться. Так вот, 1 GHz — это 1000000000 герц, или один миллиард операций в секунду. Из этого следует, что при тактовой частоте 2.10 гигагерца проц выполняет 2100000000 операций в секунду. Это конечно побольше, чем 1016. При измерении в флопсах число возрастет в несколько раз.
Идем дальше. Суперкомпьютер Titan компании Cray inc. имеет приблизительную вычислительную мощность 20 петафлопс. 1 петафлопс равен 10^15 флопс. Можете сами подсчитать, какое получится число и сколько у него нулей. Как сказал один поэт: «Это ж долбануться. »
Теперь о головном мозге. Тут все не так просто, как с компьютерами. На современном этапе развития нейробиологии довольно трудно подсчитать вычислительную мощность мозга, и сравнить его с компьютером. Однако и так понятно, что мы не можем выполнять те же операции, что выполняет наш ноутбук с такой же скоростью и в таких же объемах. Очевидно, что комп мощнее, да? А вот и нет.
Давайте разберемся подробнее, как он работает.
Мозг — это биологическая нейронная сеть. Нейронная сеть состоит из нейронов, (в случае с мозгом — это клетки мозга), каждый из которых связан с другими нейронами. Место связи нейронов называется синапсом. Через синапс от одного нейрона передается химический или электрический импульс другому нейрону. Количество нейронов в головном мозге человека примерно равно 100000000000 (ста миллиардам). Данные в из разных источников немного различаются, но в целом картина схожа. Каждый из этих нейронов имеет от 7000 до 10000 синапсов. В среднем, через один синапс проходит 10 импульсов в секунду, т.е. мы имеем тактовую частоту 10 герц на одну синоптическую связь. А теперь занимательная математика: 100000000000 нейронов мы умножаем на 10000 их синоптических связей и умножаем все это на 10 герц. Мы получаем число с шестнадцатью нолями после единицы, а иначе 10^16. Так вот откуда взялось загадочное число 1016. Видимо оно просто трансформировалось в ходе бесконечного перепоста из паблика в паблик. И оказывается, что наш мозг имеет бОльшую вычислительную мощность, чем суперкомпьютер Titan. В конечном итоге автор поста о 1016 операциях в секунду был прав.
Сколько операций в секунду выполняет c
HedayatYamin → Problems Testcases
rui_er → Codeforces Round 942 (Div. 1, Div. 2)
MateoCV → Codeforces Round 856 (Div. 2) Editorial
awoo → Educational Codeforces Round 165 [рейтинговый для Div. 2]
Tourist_but_newbie → IZhO 2023 help
Termodinamico → We say thank you to MikeMirzayanov
Black_Panda → ATCODER account issue
maomao90 → Simple and flexible base change algorithm for communication problems
MikeMirzayanov → Часто задаваемые вопросы
violentdoc → Who is rainboy?
akzytr → Pleasant pairs -> O(n log n)
sberens → Daily Codeforces Problem Email
EnDeRBeaT → [Tool] Graph Debugger
sdyakonov → Make proofs
atcoder_official → AtCoder Beginner Contest 351 Announcement
vovuh → Разбор Codeforces Round #640 (Div. 4)
ooaa → Codeforces Round #922 (Div. 2) Разбор
ICPCNews → The 2023 ICPC World Finals Luxor
jdurie → Codeforces Round #941 (Div. 1, Div. 2) Editorial
D0OMoP → Hidden Edge cases
BluoCaroot → problem with testlib.h readDouble
Kolyanchick → До скорых встреч
FedeNQ → Teams going to ICPC WF 2022 (Egypt 2023) — WIP List
FedeNQ → Teams going to ICPC WF 2023 (Egypt 2023, 2nd final) — WIP List
h ehezhou → 2024-The 6th Turing Cup Tournament