Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
#1

Быстрый стек, с малым обьемом памяти - C++

10.01.2010, 15:23. Просмотров 2249. Ответов 36
Метки нет (Все метки)

C++
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
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
 
#define FOR(i,a,b) for (int i(a), _b(b); i < _b; ++i)
#define ABS(a) ( (a) < 0 ? -(a) : a )
 
using namespace std;
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    cin >> n;
    stack a[1000];
    while (n--)
    {
        int d;
        string s;
        cin >> s >> d;
        if (s == "PUSH")
        {
            int dd;
            cin >> dd;
            a[d-1].push(dd);
        }
        else
            cout << a[d-1].pop() << endl;
    }
    return 0;
}
http://acm.timus.ru/problem.aspx?space=1&num=1220
нужно за 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 минуты
немного доработал ввод, на сишный, т.к. он быстрее, но ошибка с выделением памяти осталась, вот
код
C++
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
#include <iostream>
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char* s;
        scanf("%s",&s);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1].push(dd);
        }
        else
            printf("%d",a[d-1].pop());
    }
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2010, 15:23
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Быстрый стек, с малым обьемом памяти (C++):

Memory shift или самый быстрый способ перемещения блока памяти - C++
int* dataField = new int{0}; for (int i = 0; i &lt; 50; i++) dataField = 777; //тут должен быть memory shift delete dataField;...

Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти - C++
Привет! Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на каждой строчке), размером в 1...

Стек и освобождение памяти - C++
Пишу класс стека, реслизую в виде односвязного списка. stack.h #ifndef STACK_H_INCLUDED #define STACK_H_INCLUDED template &lt;class...

Стек. Нехватка памяти. Числа в тексте - C++
Здравствуйте, у меня возникла проблема, и как я понял, именно в нехватке памяти. Программа должна выводить число и второе число, ближайшее...

Используя стек, описать функцию проверяющую, является ли стек пустым - C++
Используя стек, описать функцию проверяющую, является ли стек пустым

Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами - C++
Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами #include &lt;iostream&gt; #include &lt;stdlib.h&gt; ...

36
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 16:14 #2
C++
1
2
3
4
void *realloc(
   void *memblock,
   size_t size 
);
Parameters
memblock
Pointer to previously allocated memory block.

size
New size in bytes.

Посмотри на входные параметры. В частности параметр 1

Требуется тип void* , a ты ему суешь sz, что int. Вот он и противится тебе.

Добавлено через 18 минут
Надо подумать... 100000 вызовов функций по работе с паматью... Не уверен, что программа уложится в секунду...
1
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 17:02  [ТС] #3
Цитата Сообщение от GRANDEATH Посмотреть сообщение
Надо подумать... 100000 вызовов функций по работе с паматью... Не уверен, что программа уложится в секунду...
есть предложения? пямяти тоже нет..

Добавлено через 17 минут
scanf("%s",&s);
if (s == "PUSH")
эти строки, они коректны?
0
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 17:52 #4
Я решил сделать так:
1. Не использовать string (едять память)
2. Не делать сравнение строк, а сравнивать только одну букву
3. Выделать память блоками
4. Убрать cout, cin

Я приложу код. Но он работает плохо. Я не знаю откуда он есть столько памяти!!!
Даже на этапе ИНИЦИАЛИЗАЦИИ
C++
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
#include <stdio.h>
#include <malloc.h>
 
//#include <iostream>
//#include <sstream>
//#include <string>
//#include <algorithm>
 
#define BLOCK_SIZE 20
const int BLOCK_INT_SIZE = BLOCK_SIZE * sizeof(int);
 
//using namespace std;
 
class stack
{
public:
        stack()
        {
                pos = 0;
                length = 1; //ÎäèГ* áëîê âûäåëåГ*
                a = (int *) calloc (BLOCK_SIZE, sizeof(int));
        }
        ~stack(){}
        void push(int n)
        {
                if (pos == BLOCK_SIZE - 1)
                {
                     length ++; //ÄîáГ*âèëè ГҐГ№Вё îäèГ* áëîê
                     a = (int*)realloc( (void*)a, BLOCK_INT_SIZE*length); // Âûäåëèëè ГЇГ*ìÿòü
                     pos = 0; //Ïîçèöèÿ Г*Г* Г*Г*Г·Г*ëî
                }
                a[(length - 1)*BLOCK_SIZE + pos] = n;
                pos++; //Óâåëè÷èëè ïîçèöèþ Г*Г* 1
        }
        int pop()
        {
                if (pos == -1)
                {
                     length --; //ÓäГ*Г«Г*ГҐГ¬ áëîê
                     a = (int*)realloc( (void*)a, BLOCK_INT_SIZE*length); // ГђГ*ñïðåäåëèòü ГЇГ*ìÿòü
                     pos = BLOCK_SIZE - 1; //Ïîçèöèÿ Г*Г* Г*Г*Г·Г*ëî
                }
                pos--; //ÓìåГ*ГјГёГ*ГҐГ¬ ïîçèöèþ Г*Г* 1
                
                return a[(length - 1)*BLOCK_SIZE + pos];
        }
private:
        int* a; //ГЌГ*Г·Г*ëî Г¬Г*Г±Г±ГЁГўГ*
        int pos; //Г’ГҐГЄГіГ№Г*Гї ïîçèöèÿ
        int length; // ÄëèГ*Г*
};
 
int main()
{
        int n;
        scanf("%d",&n);
        stack a[1000];
        
        char temp[20]; // ÂðåìåГ*Г*Г*Гї ïåðåìåГ*Г*Г*Гї
        while (n--)
        {
                int d;
                scanf("%s",temp);
                scanf("%d",&d);
                if (temp[1] == 'U') // temp[1] ñîäåðæèò 'U' äëÿ pUsh èëè 'O' äëÿ pOp
                {
                        int dd;
                        scanf("%d",&dd);
                        a[d-1].push(dd);
                }
                else
                        //cout << a[d-1].pop() << endl;
                        printf("%d\n",a[d-1].pop());
        }
        
        
        system("pause"); //Error
        return 0;
}
Добавлено через 3 минуты
Говоря блоками я имею ввиду выделение на 20 чисел. Это уменьшит частоту вызова функций где-то на 1000 процентов. (Так она вызывалась на 20 чисел 10 раз (в среднем), теперь она вызывается один раз). Согласен, идет не очень удачный расход памяти.
По идее, я теряю максимум 20 чисел * 4 байта на число * 1000 кол-во стеков. Это 80 килобайт.
но откуда у меня такие потери памяти - не знаю((

Добавлено через 1 минуту
Как вообще отследить сколько памяти жрет прога?? Кроме диспетчера задач, котрый ахинею несет.
1
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 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
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:09 #6
Мне приходила в голову такая идея. Но надо рассмотреть операции ограничения. То есть мы попытаемся сами смоделировать realloc. То есть разбить наш массив на части и отслеживать их. Я вот только понять не могу
realloc returns a void pointer to the reallocated (and possibly moved) memory block.

If there is not enough available memory to expand the block to the given size, the original block is left unchanged, and NULL is returned.

If size is zero, then the block pointed to by memblock is freed; the return value is NULL, and memblock is left pointing at a freed block.

The return value points to a storage space that is guaranteed to be suitably aligned for storage of any type of object. To get a pointer to a type other than void, use a type cast on the return value.
по идее он должен возвращать память куче.
1
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:13 #7
по идее он должен возвращать память куче.
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.

Добавлено через 58 секунд
То есть разбить наш массив на части и отслеживать их.
Либо разбить на части.

Но мне больше нравится идея - не разбивать на части.
То есть один большой массив
2
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:16 #8
Если же они будут делать половину PUSH, а половину POP
тогда памяти потребуется всего 0.2Mb.
Вот я и подумал, а почему бы не выделять блоками. Есть алгорит передвижение блоков. Но я не очень уверен, что он окажется удачным. Хотя с другой стороны почему бы не разбить массив на "страницы". Нам придется создать массив указателей на эти блоки, что не очень хорошо. И представь, сколько ошибок памяти у нас будет .
Нет. Надо усовершенствоавать realloc, я верю в команду разработчков этой функции

Добавлено через 2 минуты
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.

Значит придется массив.
1
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:16 #9
Нам придется создать массив указателей на эти блоки, что не очень хорошо.
Нормально будет.
И представь, сколько ошибок памяти у нас будет
Ни одной не будет
2
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 18:23  [ТС] #10
проблему предоставляет то что стеков 1000 и в каждом максимум 100000 элементов, сколько у нас теперь памяти получится? (можно вести отдельный масив top[i], который указывает на верхний элемент стека i, он размером 1000 интов) и того 1000*100000+1000 = 1000001000 интов ~ 100*1000*1000 = 10 млн интов
0
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:24 #11
По скольку будет разбивать?
Предлагаю по 50 чисел.
То есть max размер = 100 000 * 4 байта + 1000* 200 байт = 400 + 200 = 600 килов. Это много
+ нам потребуется массив указателей.

Добавлено через 37 секунд
Цитата Сообщение от outoftime Посмотреть сообщение
1000 и в каждом максимум 100000 элементов
Нет. В общем случае 100 000 элементов
1
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:25 #12
Нет. В общем случае 100 000 элементов
Ну так я о чем говорю уже полчаса !
Там в худшем случае 100000 элементов ВСЕГО.
1
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:27 #13
Мы разобъем весь массив на блоки. И будем выделять из них. То есть сначала у кажного 50 чисел. Если какой-то становится больше - находим свободный блок и пишем туда. А к указателям в этом стеке добавляем указатель на еще один блок.

Добавлено через 1 минуту
Цитата Сообщение от odip Посмотреть сообщение
Ну так я о чем говорю уже полчаса !
Там в худшем случае 100000 элементов ВСЕГО.
Я согласен с тобой. Надо уже взять и написать эту задачу!!!
1
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 18:38  [ТС] #14
код вышел типа:
C++
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
#include <iostream>
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
int main()
{
    int n;
    scanf("%d",&n);
    stack** a = (int **) malloc (1000 * sizeof(int *)),
        * top = (int *) calloc (1000, sizeof(int));
    FOR(i,0,1000)
        a[i] = (int *) malloc (100*1000 * sizeof(int));
    while (n--)
    {
        int d;
        char s[10];
        scanf("%s%d",&s,&d);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1][top[d-1]++] = dd;
        }
        else
            printf("%d",a[d-1][top[d-1]--]);
    }
    return 0;
}
Добавлено через 7 минут
можно попутно вопрос: что если сделать 1000 стеков вручную, на указателях?
1
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:44 #15
Идея то неплохая. Вот только вопрос? Чем память рубить будешь? alloc или new? Но вот главный вопрос - как освобождать будешь - free? И ответ - почему мы не можем использовать функцию realloc?
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.
Результат будет тот же
1
10.01.2010, 18:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2010, 18:44
Привет! Вот еще темы с ответами:

Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? - C++
Есть у меня пробелы в познаниях, хотел бы их устранить. 1. Что такое стек в самом языке С++ ? 2. В какой памяти он хранится и почему...

при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"? - C++
Сабж g++ 4.5.0

исчезла папка обьемом 13Гб. нет и ее и в скрытых файлах. - Носители информации
Здравствуйте! Может поможете в решении проблемы: После использования программы SAFE1.8(прячет файлы в сейф ), на переносном жестком...

Прочитать последовательность из файла и создать стек в памяти - Pascal
В файл записывается последовательность целых чисел. Прочитать последовательность из файла и создать стек в памяти из этих чисел таким...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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