Форум программистов, компьютерный форум CyberForum.ru

Лимит памяти для решений задач - C++

Восстановить пароль Регистрация
 
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
07.02.2013, 04:47     Лимит памяти для решений задач #1
Чем руководствуются авторы задач, устанавливая лимт памяти для программ-решений?
Например, простая задча.
Её решение, сохранённое в текстовом режиме (блокнот) занимает на диске 4 килобайта.
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
cout << n/10 << " " << n%10 << endl;
return 0;
}
Откомпилированный файл (exe-шник) занимает меньше одного мегабайта (VisualStudio).
Вопрос: Если это не обьём кода и не объём ехе-шника,то что это?
Если это обьём памяти, используемый программой во время работы, то как грамотно установить его для конкретной задачи? И почему он в предложенной задаче аж 16 мегабайт?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.02.2013, 04:47     Лимит памяти для решений задач
Посмотрите здесь:

C++ Как увеличить лимит на количество символов в консоли
Как задать свои иконки для панели задач и для программы в папке? C++
Система для решений уравнений методом простых итераций. C++
C++ Нужна рекомендация для задач по с++
C++ Лимит
C++ Просрочен лимит времени
C++ Составить программу для вычисления решений системы неравенств
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2775 / 1588 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
07.02.2013, 11:09     Лимит памяти для решений задач #2
Цитата Сообщение от LVV Посмотреть сообщение
Если это обьём памяти, используемый программой во время работы, то как грамотно установить его для конкретной задачи?
Так же, как и время работы - исходя из предполагаемого метода решения. Так, чтобы слишком простые и неэффективные решения не прошли тест.
Цитата Сообщение от LVV Посмотреть сообщение
И почему он в предложенной задаче аж 16 мегабайт?
Думаю, просто так, потому что тут всё равно. Хотя надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
07.02.2013, 11:20  [ТС]     Лимит памяти для решений задач #3
Цитата Сообщение от Somebody Посмотреть сообщение
Так же, как и время работы - исходя из предполагаемого метода решения...
... надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет.
Но время вычислений можно измерить, скажем, средствами <time.h> внутри самой программы. А как измерить требуемый размер памяти. Ведь не наугад же он устанавливается авторами задач. К тому же тестирующей системе нужно как-то проверять, укладывается ли решение в лимит памяти...
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
07.02.2013, 11:58     Лимит памяти для решений задач #4
LVV, ulimit + timeout - вот и все решение по ограничение
Авторами ограничения берутся видимо из существующих решений
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
07.02.2013, 13:19  [ТС]     Лимит памяти для решений задач #5
Цитата Сообщение от alex_x_x Посмотреть сообщение
LVV, ulimit + timeout - вот и все решение по ограничение
Авторами ограничения берутся видимо из существующих решений
Не забывайте, чт это страничка для начинающих...
Простой вопрос: участник олимпиады решает конкретную задачу. Как ему конкретно узнать, какой обьём памяти использует его конкретное решение? Например, такое:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main()
{
long long s=0;
for(int i=1; i<10000; i++)
for(int j=i; j<10000; j++)
s+=(i*j);
cout << s << endl;
return 0;
}
Может я по своей малограмотности что-то не так формулирую, тогда извините.
Но для большинства олимпиадых задач кроме тайм-лимита устанавливается ещё и лимит памяти.
Вот меня и интересует, как его вычислить (определить).
Что касается лимитов времени, то здесь нет проблем, потому что его можно определить, скажем, так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <ctime>
using namespace std;
int main()
{
long long s=0;
clock_t start,finish;
start = clock();
for(int i=1; i<10000; i++)
for(int j=i; j<10000; j++)
s+=(i*j);
finish = clock();
cout << s << endl
<< finish-start;
return 0;
}
А каким образом я могу определить обьём памяти, используемый данным решением?
Somebody
2775 / 1588 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
07.02.2013, 14:34     Лимит памяти для решений задач #6
Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
07.02.2013, 14:52  [ТС]     Лимит памяти для решений задач #7
Цитата Сообщение от Somebody Посмотреть сообщение
Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей.
Жаль. Я думал, существуют определённые методы...
Somebody
2775 / 1588 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
07.02.2013, 16:14     Лимит памяти для решений задач #8
Цитата Сообщение от LVV Посмотреть сообщение
Жаль. Я думал, существуют определённые методы...
Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
07.02.2013, 17:58  [ТС]     Лимит памяти для решений задач #9
Цитата Сообщение от Somebody Посмотреть сообщение
Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае.
Я и не имел в виду только это случай.
Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.02.2013, 19:07     Лимит памяти для решений задач #10
Цитата Сообщение от LVV Посмотреть сообщение
Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения.
Ну это же от авторов задачи и тестирующей системы зависит. Обычно есть какой-то повседневный лимит, который устанавливается на многие задачи, для некоторых задач он понижается, для некоторых повышается. Ваша задача к некоторым не относится.
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
07.02.2013, 20:11     Лимит памяти для решений задач #11
лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили".
Авторы задач решают свои задания, и исходя от своих решений указывают лимиты.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
07.02.2013, 20:49  [ТС]     Лимит памяти для решений задач #12
Цитата Сообщение от ZoRT Посмотреть сообщение
лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили".
Авторы задач решают свои задания, и исходя от своих решений указывают лимиты.
В том то и дело: хотелось бы знать как они определяют лимиты для своих решений? Это делается особым программным обеспечением? Или средствами С++ в самом решении можно определить?
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
12283 / 6970 / 784
Регистрация: 27.09.2012
Сообщений: 17,282
Записей в блоге: 2
Завершенные тесты: 1
07.02.2013, 20:56     Лимит памяти для решений задач #13
Цитата Сообщение от LVV Посмотреть сообщение
Это делается особым программным обеспечением?
Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
08.02.2013, 08:48  [ТС]     Лимит памяти для решений задач #14
Цитата Сообщение от Croessmah Посмотреть сообщение
Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д.
То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ???
Это тоже самое, что с секундомером определять, укладывается ли прорамма в лимит времени, или нет.
diagon
Higher
 Аватар для diagon
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.02.2013, 11:51     Лимит памяти для решений задач #15
Цитата Сообщение от LVV Посмотреть сообщение
То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ???
В подавляющем большинстве случаев нужно посчитать лишь размер самого большого контейнера(массива/списка/дерева/etc), это занимает несколько секунд.
Причем считается это только в том случае, если вы не уверены, что ваша программа пройдет ограничения на память. А это не так уж часто случается.
LVV
56 / 56 / 3
Регистрация: 15.02.2010
Сообщений: 239
08.02.2013, 18:51  [ТС]     Лимит памяти для решений задач #16
Нашел решение своего же вопроса.
Зацикливаю процесс, запускаю программу и смотрю в диспетчере задач Windows сеолько памяти занято процессом.
Вот только как это сделать средствами самого С++, пока не додумался...
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1238 / 987 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
08.02.2013, 23:46     Лимит памяти для решений задач #17
Цитата Сообщение от LVV Посмотреть сообщение
Вот только как это сделать средствами самого С++, пока не додумался...
Для винды: GetProcessMemoryInfo(), а там PagefileUsage или PrivateUsage из структурки. У линупсов есть procfs, откуда всё, что надо, можно прочитать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.02.2013, 23:46     Лимит памяти для решений задач
Еще ссылки по теме:

Лимит по времени C++
C++ Выделение памяти в куче для строки для реализации длинной арифметики
C++ Лимит char в msvc
Счастливый билет (Лимит Времени) C++
C++ Сборник задач для C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
08.02.2013, 23:46     Лимит памяти для решений задач #18
Цитата Сообщение от LVV Посмотреть сообщение
Нашел решение своего же вопроса.
Зацикливаю процесс, запускаю программу и смотрю в диспетчере задач Windows сеолько памяти занято процессом.
Вот только как это сделать средствами самого С++, пока не додумался...
С++ живёт на уровне своей библиотеки + libc. Такие вещи как потребление памяти и прочее распределено как правило между сишным менеджером памяти и непосредственно ОС.

Эта тема вообще бессмысленна сама по себе, так как вопросы распределения памяти к с++ мало относятся как ни крути.

Можно различными системными вызовами попросить ОС (или libc) оценить используемую память (но там уже начнётся множество системных тонкостей: виртуальная память, страницы памяти итд)
Yandex
Объявления
08.02.2013, 23:46     Лимит памяти для решений задач
Ответ Создать тему
Опции темы

Текущее время: 10:00. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru