║XLR8║
|
|||||||||||
1 | |||||||||||
Быстрый стек, с малым обьемом памяти10.01.2010, 15:23. Показов 3623. Ответов 36
Метки нет Все метки)
(
нужно за 1 секунду и 0,75Мб памяти обработать 0 < N ≤ 100000 запросов к 1 ≤ A ≤ 1000 разным стекам, гарантируется что все запросы коректны, т.е. вывод елемента со стека не может быть раньше чем ввод. Вроде написал, но компилятор упорно говорит что cannot convert parameter 1 from 'int' to 'void *', как видно a = (int *) realloc(--sz, sizeof(int)); я (int *) дописал, т.е. все верно, может я чего-то непонял, в чем ошибка, подскажите пожалуйста.. Добавлено через 3 минуты немного доработал ввод, на сишный, т.к. он быстрее, но ошибка с выделением памяти осталась, вот код
0
|
|
10.01.2010, 15:23 | |
Ответы с готовыми решениями:
36
Стек и освобождение памяти |
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
||||||
10.01.2010, 16:14 | 2 | |||||
memblock Pointer to previously allocated memory block. size New size in bytes. Посмотри на входные параметры. В частности параметр 1 Требуется тип void* , a ты ему суешь sz, что int. Вот он и противится тебе. Добавлено через 18 минут Надо подумать... 100000 вызовов функций по работе с паматью... Не уверен, что программа уложится в секунду...
1
|
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
||||||
10.01.2010, 17:52 | 4 | |||||
Я решил сделать так:
1. Не использовать string (едять память) 2. Не делать сравнение строк, а сравнивать только одну букву 3. Выделать память блоками 4. Убрать cout, cin Я приложу код. Но он работает плохо. Я не знаю откуда он есть столько памяти!!! Даже на этапе ИНИЦИАЛИЗАЦИИ
Говоря блоками я имею ввиду выделение на 20 чисел. Это уменьшит частоту вызова функций где-то на 1000 процентов. (Так она вызывалась на 20 чисел 10 раз (в среднем), теперь она вызывается один раз). Согласен, идет не очень удачный расход памяти. По идее, я теряю максимум 20 чисел * 4 байта на число * 1000 кол-во стеков. Это 80 килобайт. но откуда у меня такие потери памяти - не знаю(( Добавлено через 1 минуту Как вообще отследить сколько памяти жрет прога?? Кроме диспетчера задач, котрый ахинею несет.
1
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
10.01.2010, 18:03 | 5 |
А что - N<=100000.
Даже если все операции будут PUSH, то памяти потребуется 100000*4 байт, то есть 0.4Mb Скорее всего в данной задаче realloc() вообще нельзя использовать. Потому что realloc() может тупо выделять память из системы и не возвращать ее обратно системе никогда (только по завершении программы ). То есть программа использует скажем 0.5Mb памяти, но сам размер кучи давно превысил 1Mb. Я думаю хранить данные нужно не в 1000 отдельных стеках, а в одном большом массиве. Причем массив можно сразу выделить весь ![]() Осталось продумать как записывать/извлекать быстро ![]() Если же они будут делать половину PUSH, а половину POP тогда памяти потребуется всего 0.2Mb.
1
|
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
|
10.01.2010, 18:09 | 6 |
Мне приходила в голову такая идея. Но надо рассмотреть операции ограничения. То есть мы попытаемся сами смоделировать realloc. То есть разбить наш массив на части и отслеживать их. Я вот только понять не могу
1
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
10.01.2010, 18:13 | 7 |
Только куча это что ? Это кусок памяти выделенный системой для программы. А вот его уже никто системе возвращать не собирается ![]() А именно этот размер памяти и проверяется системой как занятая память. То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу. И что ? У меня все равно будет написано - занято 1000000 байт. Добавлено через 58 секунд Но мне больше нравится идея - не разбивать на части. То есть один большой массив ![]()
2
|
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
|
10.01.2010, 18:16 | 8 |
![]() Нет. Надо усовершенствоавать realloc, я верю в команду разработчков этой функции ![]() Добавлено через 2 минуты ![]() ![]() ![]() Значит придется массив.
1
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
10.01.2010, 18:16 | 9 |
![]()
2
|
║XLR8║
|
|
10.01.2010, 18:23 [ТС] | 10 |
проблему предоставляет то что стеков 1000 и в каждом максимум 100000 элементов, сколько у нас теперь памяти получится? (можно вести отдельный масив top[i], который указывает на верхний элемент стека i, он размером 1000 интов) и того 1000*100000+1000 = 1000001000 интов ~ 100*1000*1000 = 10 млн интов
0
|
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
|
10.01.2010, 18:24 | 11 |
По скольку будет разбивать?
Предлагаю по 50 чисел. То есть max размер = 100 000 * 4 байта + 1000* 200 байт = 400 + 200 = 600 килов. Это много + нам потребуется массив указателей. Добавлено через 37 секунд Нет. В общем случае 100 000 элементов
1
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
10.01.2010, 18:25 | 12 |
Там в худшем случае 100000 элементов ВСЕГО.
1
|
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
|
10.01.2010, 18:27 | 13 |
Мы разобъем весь массив на блоки. И будем выделять из них. То есть сначала у кажного 50 чисел. Если какой-то становится больше - находим свободный блок и пишем туда. А к указателям в этом стеке добавляем указатель на еще один блок.
Добавлено через 1 минуту ![]() ![]()
1
|
║XLR8║
|
||||||
10.01.2010, 18:38 [ТС] | 14 | |||||
код вышел типа:
можно попутно вопрос: что если сделать 1000 стеков вручную, на указателях?
1
|
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
|
10.01.2010, 18:44 | 15 |
Идея то неплохая. Вот только вопрос? Чем память рубить будешь? alloc или new? Но вот главный вопрос - как освобождать будешь - free? И ответ - почему мы не можем использовать функцию realloc?
![]()
1
|
║XLR8║
|
|||||||||||
10.01.2010, 19:00 [ТС] | 16 | ||||||||||
Добавлено через 2 минуты GRANDEATH, я просто не могу понять как делать линковку, какому стеку отвечает какой элемент + нам нужет top.. Добавлено через 6 минут вот пашет на малых:
кто знает сколько мугут потянуть указатели между элементами стека? Добавлено через 2 минуты этот код не канает, 10-ий тест - выделено пямяти: 1 653 КБ
0
|
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
|
|
10.01.2010, 19:01 | 17 |
Дай 20 мин подумать
1
|
║XLR8║
|
|
10.01.2010, 19:24 [ТС] | 18 |
я думал так: если вы говорите, что для програмы выделяется куча, и даже если мы освобождаем память в систем она не возвращается, тогда нет другого пути как сделать все элементы статическими, что со стороны полный бред, но..
если мы запишем все 100000 операций в масив, после записи будем идти по нему, соответственно давая ответы на запросы? Добавлено через 12 минут и еще один вопрос: можно каким-то образом сново заполнять память которую мы освободили?
0
|
![]() 7175 / 3234 / 80
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
10.01.2010, 21:03 | 19 |
Вообщем сдал я эту задачу.
Блок состоит из 19 чисел и одного указателя на предыдущий блок. Для прикола сделал еще список свободных блоков. Блок, когда освобождается, не отдается в систему, а записывается в список свободных блоков. Когда нужен блок, то он сначала берется из этого списка, а если список пуст, тогда уже берется из системы. Я думаю что вообщем освобождение блоков не нужно, но проверять это уже лень. Добавлено через 1 минуту Да - блоки выделяются обычным malloc(). Добавлено через 3 минуты Еще вариант - вообще без блоков. Выделяем 100000*7 байт 4 байта - число 3 байта - ссылка на предыдущий элемент ( 2-ух байт на 100000 не хватит ) Если 50 Kбайт хватит для работы программы то влезем ![]() Но похоже накладные расходы больше. У меня при сдаче получилось 725Kb А я выделял блоками по 19+1 значение. То есть там еще дофига должно было остаться. Хитрая задача. Добавлено через 39 секунд Еще - не делайте на C++. У С++ накладные расходы по памяти сильно большие !
1
|
║XLR8║
|
|
10.01.2010, 21:23 [ТС] | 20 |
0
|
10.01.2010, 21:23 | |
Помогаю со студенческими работами здесь
20
Стек. Нехватка памяти. Числа в тексте Ошибка сегментирования (стек памяти сброшен на диск) Прочитать последовательность из файла и создать стек в памяти Ошибка сегментирования (стек памяти сброшен на диск) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |