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

@LVV · Регистрация: 15.02.2010

Author24 — интернет-сервис помощи студентам

Чем руководствуются авторы задач, устанавливая лимт памяти для программ-решений?
Например, простая задча.
Её решение, сохранённое в текстовом режиме (блокнот) занимает на диске 4 килобайта.

C++

#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
cout << n/10 << " " << n%10 << endl;
return 0;
}

Откомпилированный файл (exe-шник) занимает меньше одного мегабайта (VisualStudio).
Вопрос: Если это не обьём кода и не объём ехе-шника,то что это?
Если это обьём памяти, используемый программой во время работы, то как грамотно установить его для конкретной задачи? И почему он в предложенной задаче аж 16 мегабайт?

@Somebody · 07.02.2013, 11:09

Сообщение от LVV

Если это обьём памяти, используемый программой во время работы, то как грамотно установить его для конкретной задачи?

Так же, как и время работы - исходя из предполагаемого метода решения. Так, чтобы слишком простые и неэффективные решения не прошли тест.

Сообщение от LVV

И почему он в предложенной задаче аж 16 мегабайт?

Думаю, просто так, потому что тут всё равно. Хотя надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет.

@LVV · 07.02.2013, 11:20 **[ТС]**

Сообщение от Somebody

Так же, как и время работы - исходя из предполагаемого метода решения...
... надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет.

Но время вычислений можно измерить, скажем, средствами <time.h> внутри самой программы. А как измерить требуемый размер памяти. Ведь не наугад же он устанавливается авторами задач. К тому же тестирующей системе нужно как-то проверять, укладывается ли решение в лимит памяти...

@alex_x_x · 07.02.2013, 11:58

LVV, ulimit + timeout - вот и все решение по ограничение
Авторами ограничения берутся видимо из существующих решений

@LVV · 07.02.2013, 13:19 **[ТС]**

Сообщение от alex_x_x

LVV, ulimit + timeout - вот и все решение по ограничение
Авторами ограничения берутся видимо из существующих решений

Не забывайте, чт это страничка для начинающих...

Простой вопрос: участник олимпиады решает конкретную задачу. Как ему конкретно узнать, какой обьём памяти использует его конкретное решение? Например, такое:

C++

#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++

#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 · 07.02.2013, 14:34

Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей.

@LVV · 07.02.2013, 14:52 **[ТС]**

Сообщение от Somebody

Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей.

Жаль. Я думал, существуют определённые методы...

@Somebody · 07.02.2013, 16:14

Сообщение от LVV

Жаль. Я думал, существуют определённые методы...

Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае.

@LVV · 07.02.2013, 17:58 **[ТС]**

Сообщение от Somebody

Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае.

Я и не имел в виду только это случай.
Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения.

@diagon · 07.02.2013, 19:07

Сообщение от LVV

Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения.

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

@Venzo · 07.02.2013, 20:11

лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили".
Авторы задач решают свои задания, и исходя от своих решений указывают лимиты.

@LVV · 07.02.2013, 20:49 **[ТС]**

Сообщение от ZoRT

лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили".
Авторы задач решают свои задания, и исходя от своих решений указывают лимиты.

В том то и дело: хотелось бы знать как они определяют лимиты для своих решений? Это делается особым программным обеспечением? Или средствами С++ в самом решении можно определить?

Croessmah · 07.02.2013, 20:56

Сообщение от LVV

Это делается особым программным обеспечением?

Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д.

@LVV · 08.02.2013, 08:48 **[ТС]**

Сообщение от Croessmah

Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д.

То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ???
Это тоже самое, что с секундомером определять, укладывается ли прорамма в лимит времени, или нет.

@diagon · 08.02.2013, 11:51

Сообщение от LVV

То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ???

В подавляющем большинстве случаев нужно посчитать лишь размер самого большого контейнера(массива/списка/дерева/etc), это занимает несколько секунд.
Причем считается это только в том случае, если вы не уверены, что ваша программа пройдет ограничения на память. А это не так уж часто случается.

@LVV · 08.02.2013, 18:51 **[ТС]**

Нашел решение своего же вопроса.

Зацикливаю процесс, запускаю программу и смотрю в диспетчере задач Windows сеолько памяти занято процессом.
Вот только как это сделать средствами самого С++, пока не додумался...

@OhMyGodSoLong · 08.02.2013, 23:46

Сообщение от LVV

Вот только как это сделать средствами самого С++, пока не додумался...

Для винды: GetProcessMemoryInfo(), а там PagefileUsage или PrivateUsage из структурки. У линупсов есть procfs, откуда всё, что надо, можно прочитать.

@alex_x_x · 08.02.2013, 23:46

Сообщение от LVV

Нашел решение своего же вопроса.

Зацикливаю процесс, запускаю программу и смотрю в диспетчере задач Windows сеолько памяти занято процессом.
Вот только как это сделать средствами самого С++, пока не додумался...

С++ живёт на уровне своей библиотеки + libc. Такие вещи как потребление памяти и прочее распределено как правило между сишным менеджером памяти и непосредственно ОС.

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

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

@LVV 155 / 137 / 46 Регистрация: 15.02.2010 Сообщений: 750
	07.02.2013, 20:49 [ТС]	12
	Сообщение от ZoRT лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили". Авторы задач решают свои задания, и исходя от своих решений указывают лимиты. В том то и дело: хотелось бы знать как они определяют лимиты для своих решений? Это делается особым программным обеспечением? Или средствами С++ в самом решении можно определить? 0

@Somebody 2835 / 1644 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	07.02.2013, 11:09	2
	Сообщение от LVV Если это обьём памяти, используемый программой во время работы, то как грамотно установить его для конкретной задачи? Так же, как и время работы - исходя из предполагаемого метода решения. Так, чтобы слишком простые и неэффективные решения не прошли тест. Сообщение от LVV И почему он в предложенной задаче аж 16 мегабайт? Думаю, просто так, потому что тут всё равно. Хотя надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет. 1

@LVV 155 / 137 / 46 Регистрация: 15.02.2010 Сообщений: 750
	07.02.2013, 11:20 [ТС]	3
	Сообщение от Somebody Так же, как и время работы - исходя из предполагаемого метода решения... ... надо учитывать, что в памяти будет exe'шник, несколько dll'ок, ещё стек какой-то размер уже изначально имеет. Но время вычислений можно измерить, скажем, средствами <time.h> внутри самой программы. А как измерить требуемый размер памяти. Ведь не наугад же он устанавливается авторами задач. К тому же тестирующей системе нужно как-то проверять, укладывается ли решение в лимит памяти... 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	07.02.2013, 11:58	4
	LVV, ulimit + timeout - вот и все решение по ограничение Авторами ограничения берутся видимо из существующих решений 0

@Somebody 2835 / 1644 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	07.02.2013, 14:34	6
	Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей. 1

@LVV 155 / 137 / 46 Регистрация: 15.02.2010 Сообщений: 750
	07.02.2013, 14:52 [ТС]	7
	Сообщение от Somebody Так, на глаз... Отдельная переменная - почти ничего, сам код - тоже немного. Так что достаточно посчитать размеры массивов, связных списков, деревьев и прочих крупных вещей. Жаль. Я думал, существуют определённые методы... 0

@Somebody 2835 / 1644 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	07.02.2013, 16:14	8
	Сообщение от LVV Жаль. Я думал, существуют определённые методы... Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае. 0

@LVV 155 / 137 / 46 Регистрация: 15.02.2010 Сообщений: 750
	07.02.2013, 17:58 [ТС]	9
	Сообщение от Somebody Методы, конечно, существуют. Только смысла особого не имеет точно измерять всё в таком случае. Я и не имел в виду только это случай. Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	07.02.2013, 19:07	10
	Сообщение от LVV Прото хотелось знать, если задаётся лимит времени, то как он определяется для каждой конкретной задачи и каждого конкреиного решения. Ну это же от авторов задачи и тестирующей системы зависит. Обычно есть какой-то повседневный лимит, который устанавливается на многие задачи, для некоторых задач он понижается, для некоторых повышается. Ваша задача к некоторым не относится. 0

@Venzo 127 / 125 / 16 Регистрация: 03.07.2011 Сообщений: 354
	07.02.2013, 20:11	11
	лимиты задаются, чтобы задачу не решали "в лоб", а применяли какие-то алгоритмы, которые авторы задачи "заложили". Авторы задач решают свои задания, и исходя от своих решений указывают лимиты. 0

Croessmah Неэпический 17870 / 10635 / 2054 Регистрация: 27.09.2012 Сообщений: 26,736 Записей в блоге: 1
	07.02.2013, 20:56	13
	Сообщение от LVV Это делается особым программным обеспечением? Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д. 0

	08.02.2013, 23:46

@LVV 155 / 137 / 46 Регистрация: 15.02.2010 Сообщений: 750
	08.02.2013, 08:48 [ТС]	14
	Сообщение от Croessmah Если Вы пишите программу, вы же знаете сколько памяти она кушает =) плюс всякие библиотеки и т.д. То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ??? Это тоже самое, что с секундомером определять, укладывается ли прорамма в лимит времени, или нет. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	08.02.2013, 11:51	15
	Сообщение от LVV То есть: мне нужно сидеть с калькулятором и подсчитывать, какой обьём занимает код, какой библиотеки, сколько потребуется на переменные, сколько уйдёт на массивчик... и т.д. и т.п. ??? В подавляющем большинстве случаев нужно посчитать лишь размер самого большого контейнера(массива/списка/дерева/etc), это занимает несколько секунд. Причем считается это только в том случае, если вы не уверены, что ваша программа пройдет ограничения на память. А это не так уж часто случается. 1

@LVV 155 / 137 / 46 Регистрация: 15.02.2010 Сообщений: 750
	08.02.2013, 18:51 [ТС]	16
	Нашел решение своего же вопроса. Зацикливаю процесс, запускаю программу и смотрю в диспетчере задач Windows сеолько памяти занято процессом. Вот только как это сделать средствами самого С++, пока не додумался... 0

@OhMyGodSoLong ~ Эврика! ~ 1256 / 1005 / 74 Регистрация: 24.07.2012 Сообщений: 2,002
	08.02.2013, 23:46	17
	Сообщение от LVV Вот только как это сделать средствами самого С++, пока не додумался... Для винды: GetProcessMemoryInfo(), а там PagefileUsage или PrivateUsage из структурки. У линупсов есть procfs, откуда всё, что надо, можно прочитать. 1

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	08.02.2013, 23:46	18
	Сообщение от LVV Нашел решение своего же вопроса. Зацикливаю процесс, запускаю программу и смотрю в диспетчере задач Windows сеолько памяти занято процессом. Вот только как это сделать средствами самого С++, пока не додумался... С++ живёт на уровне своей библиотеки + libc. Такие вещи как потребление памяти и прочее распределено как правило между сишным менеджером памяти и непосредственно ОС. Эта тема вообще бессмысленна сама по себе, так как вопросы распределения памяти к с++ мало относятся как ни крути. Можно различными системными вызовами попросить ОС (или libc) оценить используемую память (но там уже начнётся множество системных тонкостей: виртуальная память, страницы памяти итд) 1